TITLE: Problem C. Candy Splitting
#contents
#br
* 問題 [#vb8039f6]
兄弟であるショーン (Sean) とパトリック (Patrick) は、両親から飴の入った素敵なカバンをもらった。
飴にはいくつかの種類があり、それぞれ複数個ある。
彼らは、同じ飴の種類を一つの塊として、二人で分けたいと思っている。
まず、ショーンは飴を2つの山に分け、パトリックに与えるだろう。
しかし、パトリックは自分の分の飴の数と、ショーンの飴の数を比べ、もし二等分されていないと判断すると泣いてしまう。
残念ながら、パトリックは非常に幼いので、正しく足し算する方法を知らない。
パトリックは2進数の足し算ができるが、それは不正確である。
繰り上がりをいつも忘れてしまうのだ。
たとえば、12 (2進数では 1100) と 5 (2進数では 101) を足す場合を考える。
パトリックは、右から2つのビットは正しく計算することができるが、3つめのビットで繰り上がりを忘れてしまう。
| |1|1|0|0|
|+|0|1|0|1|
| |1|0|0|1|f
右から3ビット目で繰り上がりを忘れた場合、計算結果は 9 (2進数で 1001) になってしまう。
他に、パトリックが行った足し算の例を挙げる。
#pre{{
5 + 4 = 1
7 + 9 = 14
50 + 10 = 56
}}
ショーンは非常にいい子なので、なるべくパトリックを泣かせたくないと思っている。
もしそれができるなら、ショーンはパトリックが二等分されていると考える値で分割するだろう。
あなたには、バッグの飴の個数が与えられた時、パトリックが泣かないような分割ができるかどうか調べて欲しい。
もしそれができるのであれば、ショーンの飴の個数が一番多くなるような分割方法を求めよ。
なお、分割する際に、同じ種類の飴が両者に分かれてしまってはいけない。
* 入力 [#l1eb9688]
#pre{{
T
N
C1 C2 ... CN
...
}}
1行目はデータセットの個数 T が与えられる。
2行目以降は、データセットのデータである。
1つのデータセットは2行で構成される。
データセットの1行目は、飴の種類の数 N である。
データセットの2行目は、飴の種類別の個数 Ci が N 個与えられる。
* 出力 [#heb0c1c8]
#pre{{
Case #x: y
...
}}
データセットごとに、データセットの番号 x (1 から始める) と、パトリックが泣かないように分割した際のショーンの飴の個数 y を出力せよ。
ただし、どのように分割してもショーンが泣いてしまう場合は、y として「NO」という文字列を出力せよ。
* 制限 [#s6eb4ef8]
1 ≦ T ≦ 100
1 ≦ Ci ≦ 106
** データセット(小) [#ube727af]
2 ≦ N ≦ 15
** データセット(大) [#na0cf0b1]
2 ≦ N ≦ 1000
* サンプル入出力) [#lc37ea7a]
** 入力 [#r51a9059]
#pre{{
2
5
1 2 3 4 5
3
3 5 6
}}
** 出力 [#g097ad23]
#pre{{
Case #1: NO
Case #2: 11
}}
* ヒント [#v490d182]
#region
繰り上がりがない足し算は XOR と考えることができます。
#endregion
* 提出・原文 [#ydeada87]
http://code.google.com/codejam/contest/dashboard?c=975485#s=p2
* 回答例 [#r7dfaa25]
|作成者|ソースコード|
|&areaedit(){pine};|&attachref(./GCJ_2011QRC_CandySplitting.cpp);|
[&addline(file,above){入力欄を追加};]