問題
http://community.topcoder.com/stat?c=problem_statement&pm=9917&rd=13511
カードが数枚ずつ山になって積まれている。
各ターン、すべての山から１枚ずつカードをとって、そのカードで
一つ山を追加する操作を繰り返す。
この操作を繰り返したとき必ずもとの配列にもどる周期が必ず存在し、
そのような周期はいくつであるか求める。
解き方
問題の通り実装する。
各操作ごとにカードの配列を保存し、最初に同じ配列が
改めて出現した時にそのターン数の差分を飼えしてあげればよい。
コード
class SolitaireSimulation {
public: int periodLength(vector<int> heaps) {
map<vector<int>,int> m;
sort(all(heaps));
m[heaps]=0;
int turn=0;
while(1){
turn++;
vector<int> tmp;
for(int i=0;i<heaps.size();i++){
if(heaps[i]-1>0)tmp.push_back(heaps[i]-1);
}
tmp.push_back(heaps.size());
sort(all(tmp));
heaps=tmp;
if(m.find(heaps)==m.end())m[heaps]=turn;
else return turn-m[heaps];
}
return -1;
}
};
public: int periodLength(vector<int> heaps) {
map<vector<int>,int> m;
sort(all(heaps));
m[heaps]=0;
int turn=0;
while(1){
turn++;
vector<int> tmp;
for(int i=0;i<heaps.size();i++){
if(heaps[i]-1>0)tmp.push_back(heaps[i]-1);
}
tmp.push_back(heaps.size());
sort(all(tmp));
heaps=tmp;
if(m.find(heaps)==m.end())m[heaps]=turn;
else return turn-m[heaps];
}
return -1;
}
};