Problem C. Candy Splitting

問題

兄弟であるショーン (Sean) とパトリック (Patrick) は、両親から飴の入った素敵なカバンをもらった。

飴にはいくつかの種類があり、それぞれ複数個ある。
彼らは、同じ飴の種類を一つの塊として、二人で分けたいと思っている。

まず、ショーンは飴を2つの山に分け、パトリックに与えるだろう。
しかし、パトリックは自分の分の飴の数と、ショーンの飴の数を比べ、もし二等分されていないと判断すると泣いてしまう。

残念ながら、パトリックは非常に幼いので、正しく足し算する方法を知らない。

パトリックは2進数の足し算ができるが、それは不正確である。
繰り上がりをいつも忘れてしまうのだ。

たとえば、12 (2進数では 1100) と 5 (2進数では 101) を足す場合を考える。
パトリックは、右から2つのビットは正しく計算することができるが、3つめのビットで繰り上がりを忘れてしまう。

右から3ビット目で繰り上がりを忘れた場合、計算結果は 9 (2進数で 1001) になってしまう。

他に、パトリックが行った足し算の例を挙げる。

5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

ショーンは非常にいい子なので、なるべくパトリックを泣かせたくないと思っている。

もしそれができるなら、ショーンはパトリックが二等分されていると考える値で分割するだろう。

あなたには、バッグの飴の個数が与えられた時、パトリックが泣かないような分割ができるかどうか調べて欲しい。
もしそれができるのであれば、ショーンの飴の個数が一番多くなるような分割方法を求めよ。

なお、分割する際に、同じ種類の飴が両者に分かれてしまってはいけない。

入力

T
N
C1 C2 ... CN
...

1行目はデータセットの個数 T が与えられる。
2行目以降は、データセットのデータである。

1つのデータセットは2行で構成される。
データセットの1行目は、飴の種類の数 N である。
データセットの2行目は、飴の種類別の個数 Ci が N 個与えられる。

出力

Case #x: y
...

データセットごとに、データセットの番号 x (1 から始める) と、パトリックが泣かないように分割した際のショーンの飴の個数 y を出力せよ。

ただし、どのように分割してもショーンが泣いてしまう場合は、y として「NO」という文字列を出力せよ。

制限

1 ≦ T ≦ 100
1 ≦ Ci ≦ 106

データセット(小)

2 ≦ N ≦ 15

データセット(大)

2 ≦ N ≦ 1000

サンプル入出力)

入力

2
5
1 2 3 4 5
3
3 5 6

出力

Case #1: NO
Case #2: 11

ヒント

提出・原文

http://code.google.com/codejam/contest/dashboard?c=975485#s=p2

回答例

作成者	ソースコード
pine[e]	GCJ_2011QRC_CandySplitting.cpp

[入力欄を追加]