時間制限:1000ミリ秒
メモリ制限:10000KB
分割
問題
マーシャとビルはビー玉のコレクションを持っている。彼らはコレクションを等しい割合になるように分割したい。これは、ビー玉が全て同じ価値であれば、単純にコレクションを2つに分ければいいだけなので簡単である。しかし不幸なことに、いくつかのビー玉は他より大きいか、他より美しい。そこで、マーシャとビルはそれぞれのビー玉に1以上6以下の自然数を割りあてることにした。今、彼らはビー玉をそれぞれの価値の合計が等しくなるように分割したい。しかし、彼らはビー玉をこの方法で分割することはできないかもしれない(もしビー玉の価値の合計が偶数だったとしても。)例えば、価値1のビー玉1つと、価値3のビー玉1つの、価値4のビー玉2つがある場合、彼らはこれを価値の合計が等しい2つの集合に分割することはできない。そこで、彼らはあなたに、このようなビー玉の公平な分割が可能かどうかを調べるプログラムを書くよう頼みにきた。
入力
入力の各行は分割したいビー玉のコレクションを記述している。各行は、価値iのビー玉の個数をあらわす6つの非負整数n1, ... , n6が空白を区切りとして書かれている。例えば、前述の例は「1 0 1 2 0 0」という行で表現される。ビー玉の総数は最大で20000である。
出力
各コレクションについて、テストケースの番号kを用いて「Collection #k:」という行を出力したのち、「Can be divided.」または「Can't be divided.」という行を出力せよ。
各テストケースの後には空行を出力せよ。
入力例
1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0
出力例
Collection #1: Can't be divided.
Collection #2: Can be divided.
出典
Mid-Central European Regional Contest 1999