読者です 読者をやめる 読者になる 読者になる

Google Code Jam Qualification Round - C問題「Candy Splitting」

Dashboard - Qualification Round 2011 - Google Code Jam

問題

ショーンとパトリックは兄弟で、親からバッグ一杯のキャンディをもらった。
それぞれのキャンディは正の整数値を有し、彼らはキャンディを分けようとしている。
まず、ショーンがキャンディの山を2つに分け、片方をパトリックに与える。。
そしてパトリックがキャンディの山の価値を計算する。
キャンディの山の価値とは、それぞれのキャンディの整数値の和のことである。
もし2つの山の価値が異なると、パトリックは泣き出す。

不幸なことに、パトリックは幼すぎて足し算が正しくできない。
彼は2進数で足し算をすることをほぼ知っているのだが、
2つの1を足したときにその繰り上がりを無視してしまうのだ。
例えば、12(2進数で1100)と5(2進数で101)を足すとき、
彼は右から2桁までは正しく計算できるが、3桁目の計算の繰り上がりを忘れてしまう。

  1100
+ 0101
------
  1001

つまり、彼による足し算の結果は9(2進法で1001)となってしまう。
パトリックによる足し算の例を他にも下記に例示する。

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

ショーンは足し算が得意なので、弟のパトリックを泣かせないようにしつつ
なるべく多くの価値を得るようにキャンディを分けようと考えた。
今、彼はバッグ一杯のキャンディを2つの山(いずれも1個以上のキャンディを含む)に分け、
パトリックが両方の山を同じ価値だと計算するようにしたい。

全てのキャンディの価値が与えられたとき、
ショーンがこのような分け方をすることが可能かを判定し、
また可能であればその時のショーンの取り分の最大値を計算せよ。

入力

最初の行にテストケース数Tがあり、T個のテストケースが続く。
それぞれのテストケースは2行から成り、
最初の1行には整数Nが記され、これはバッグの中のキャンディの個数を表す。
次の1行にはN個の整数Ciが半角スペースで区切られて記される。
Ciはそれぞれのキャンディの価値の値である。

出力

それぞれのテストケースにおいて、"Case #x: y" の形式で出力する。
xはテストケース番号(1から始まる)で、
yはもしパトリックが泣くのを避けられなければ"NO"の文字列、
そうでなければショーンが得ることのできる価値の最大値とする。

制限

1 ≦ T ≦ 100.
1 ≦ Ci ≦ 1000000.

Small dataset

2 ≦ N ≦ 15.

Large dataset

2 ≦ N ≦ 1000.

サンプル

入力

2
5
1 2 3 4 5
3
3 5 6

出力 	
 
Case #1: NO
Case #2: 11


所感
今回のQualification Roundの4問の中で一番好きな問題です。好きな理由は言うまでもありませんが、キャンディの量が不平等であるという些細な理由で泣いてしまうような幼い子がxor演算をマスターしているという境遇があまりにもシュールだからです。でも好きなこととは裏腹に、全然ダメダメなコードを提出してしまいました。あまりにも恥ずかしいので今度解き直してみます。


ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

  • 作者: ジュニア,ヘンリー・S.ウォーレン,Jr.,Henry S. Warren,滝沢徹,玉井浩,鈴木貢,赤池英夫,葛毅,藤波順久
  • 出版社/メーカー: エスアイビーアクセス
  • 発売日: 2004/09
  • メディア: 単行本
  • 購入: 35人 クリック: 732回
  • この商品を含むブログ (127件) を見る