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;
    }
  }