UVa 440 - Eeny Meeny Moo

uva-440.cpp

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <list>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
#include <math.h>

//using namespace std;

#define FIND 2

int n;

bool solve(int* v, int pos, int m, int r) {  
   if(r == 1) return v[pos] == FIND;
   if(v[pos] == FIND) return r == 1;
   
   v[pos] = 0;
   
   int t = m;
   while(t--) {
       ++pos; 
       pos %= n;
       if(v[pos] == 0) ++t;
   }
   
   return solve(v, pos, m, --r);
}

int ret[150];

int main(void) {
   for(n=3; n<150; ++n) {
       int i = 0;
       while(++i) {
           int v[n];
           for(int j=1; j<=n; ++j) v[j] = j + 1;
           
           if(solve(v, 0, i, n)) {
               ret[n] = i;
               break;
           }
       }
    }
   
   while(true) {
       scanf("%d", &n);
       if(n == 0) break;
       
       printf("%d\n", ret[n]);
   }  
   
   return EXIT_SUCCESS;
}