ビーカー
2008.09.16 21:55 パソコン甲子園 2008
問題 パソコン甲子園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 }
スポンサーサイト
| コメント(1) | トラックバック(0) | ↑ページトップ |
