ビーカー

問題 パソコン甲子園2008 10



いろいろな容量のビーカーがあります。はじめに、その中の一番容量が大きなビーカーに水を満タンに注ぎます。次に、以下のルールに従いビーカーの水を他のビーカーに写し変えていきます：

• ビーカーに入っている水は、残さずに全て他のビーカーに移さなければならない。ただし、一個のビーカーに水を全部移せない場合は、複数のビーカーに分けて移すことができる



• ビーカーに水を入れるとき、満タンになるまで水を注がなければならない。また、水をこぼしてはならない。



• 複数のビーカーから同じビーカーに一度に水を注いではならない。


• 同じビーカーには一度しか水を注いではならない。

このルールに従ったとき、すべてのビーカーに水を注ぐことができるかどうかを判定して下さい。ビーカーの数 n は 1 以上 50 以下です。

解説

問題が分かりづらいですが、「すべてのビーカーに水を注ぐことができるか」というのは「水を移し変える一連の操作の過程で、すべてのビーカーが使われたか」を意味します。

うまく枝を刈りながらバックトラックを行います。

再帰関数の構造

pour() は注ぐビーカー（source）を選び searchTarget() で注がれるビーカー（target）を決定します。searchTarget() が成功したら、さらに pour() を呼び出します。

サンプルプログラム

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 #define MAX 50
005 #define NOT_USED 0
006 #define USED 1
007 #define ISFULL 2
008 
009 bool searchTarget(int, int, int, int );
010 bool pour(int, int);
011 
012 int size, C[MAX], state[MAX];
013 
014 bool searchTarget( int volume, int source, int startt, int nfilled, int remain ){
015     if ( volume == 0 ){
016         state[source] = USED;
017         if( pour(nfilled, remain) ) return true;
018         state[source] = ISFULL;
019         return false;
020     } else if ( volume < 0 || startt < 0 || remain < volume ) return false;
021     
022     for ( int i = source - 1; i >= 0; i-- ){
023         if ( state[i] == ISFULL ) break;
024         if ( state[i] == NOT_USED && C[i] > volume ) return false;
025     }
026     
027     int pre = -1;
028     for ( int target = startt; target >= 0; target-- ){
029         if ( state[target] >= 1 || C[target] > volume ) continue;
030         if ( pre == C[target] ) continue; // pre 彫髏ｵｯ椎ﾀ彫ﾈ彫ｷ彫ｿ彫竰､ﾎ彫ﾏ彫ｹ彫ﾇ彫ﾋ懲・・勅ﾇ綴､長､槌､彫､k
031         state[target] = ISFULL;
032         if ( searchTarget( volume - C[target], source, target-1, nfilled+1, remain-C[target] ) ) return true;
033         state[target] = NOT_USED;
034         pre = C[target];
035     }
036     return false;
037 }
038 
039 bool pour( int nfilled, int remain ){
040     if ( nfilled == size ) return true;
041     
042     for ( int source = size-1; source >= 1; source-- ){
043         if ( state[source] == ISFULL ) {
044             if ( searchTarget( C[source], source, source-1, nfilled, remain )) return true;
045         }
046     }
047     
048     return false;
049 }
050 
051 bool judge(){
052     sort( C, C + size );
053     int remain = 0;
054     for ( int i = 0; i < size; i++ ) {
055         state[i] = NOT_USED;
056         remain += C[i];
057     }
058     state[size-1] = ISFULL;
059     remain -= C[size-1];
060     return pour( 1 , remain );
061 }
062 
063 int main(){
064     while ( cin >> size && size ) {
065         for ( int i = 0; i < size; i++ ) cin >> C[i];
066         if ( judge() ) cout << "YES" << endl;
067         else cout << "NO" << endl;
068     }
069     return 0;
070 }