I took a really long time to get this out. I am researching a method to get the solution with some elegant mathematical formula, but it looks like it is took hard to accomplish. So, I used the brute force method that I have, and here it is:

#include <cstdio> #include <queue> #include <map> using namespace std; bool isValid(int m, int key, int total){ queue a; int rmv=0, c=0; for(int i=0; i<key-1; i++){ a.push(0); } a.push(1); for(int i=0; i<total-key; i++){ a.push(0); } a.pop(); while(a.size()>1 && !rmv){ if(c<(m-1)){ a.push(a.front()); a.pop(); c++; }else{ rmv = a.front(); a.pop(); c=0; } } return !rmv; } int main(){ char line[1024]; gets(line); int t; sscanf(line, "%d", &t); map<int, int> mem; while(t){ int m=mem[t]; if(!m){ m = 1; while(!isValid(m, 13, t)){ m++; } mem[t] = m; } printf("%d\n", m); gets(line); sscanf(line, "%d", &t); } return 0; }

Advertisements