TopCoder SRM 420 Div1 Easy
カードが何枚か与えられる。いくつかの山に分かれている。例えば3枚、2枚、3枚。これから1枚ずつ取って新しい山を作る2, 1, 2, 3。さらに1枚ずつとる。1, 1, 2, 4。1, 3, 4。そして 2, 3, 3。ループしました。このループの周期を返せという問題。ただし、スタート状態に戻ってくるとは限らない。
まぁカードが50枚しかないので、全部保存しておいて比較する方針で。
int periodLength(vector <int> heaps) { int result = 0; sort(heaps.begin(), heaps.end()); vector<vector<int> > cache; cache += heaps; while(true){ result++; size_t N = heaps.size(); vector<int> new_heaps; for(size_t i=0; i<N; i++){ int v = heaps[i] - 1; if(v > 0){ new_heaps += v; } } new_heaps += N; heaps = new_heaps; sort(heaps.begin(), heaps.end()); size_t M = cache.size(); for(size_t i=0; i<M; i++){ if(cache[i] == heaps){ return result - i; } } cache += heaps; } }