#DP #JousephProblem #Adhoc #UVa #NotSolved

180 - Eeny Meeny-NOT-AC.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=116
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int cache[(int)1e6+5];
bool mask[(int)1e6+5];
int l, h;

int calcM(int n, int cycle) {
    cache[0] = cache[1] = 0;
    mask[0] =1;
    for(int i = 2; i <= n; i++) {
        cache[i] = (cache[i-1] + cycle) % i;
        if(i>=l)mask[cache[i]] = 1;
    }
    return cache[n];
}
int cache2[(int)1e6+5];
int calcMAntiClockWise(int n, int cycle) {
    cache2[0] = cache2[1] = 0;
    for(int i = 2; i <= n; i++) {
        if(cache2[i-1] - cycle < 0) {
            cache2[i] = i - ((cycle - (cache2[i-1]+1) )%i);
        } else {
            cache2[i] = (cache2[i-1] - cycle);
        }
        if(i>=l)mask[cache2[i]] = 1;
    }

    return cache2[n];
}

int main() {
    int n, m;
    while(cin>>n && cin>>m && n!=0 && m!=0) {
        h = max(n, m);
        l = min(n, m);
        clr(mask, 0);
        calcM(h, 2);
        calcMAntiClockWise(h, 2);
        lp(i, h) cout << mask[i] << " ";
        cout << endl;
        bool found = 0;
        for(int i = 1;i <=h;i++) {
            if(mask[i] == 0) {
                cout << i << endl; found = 1; break;
            }

            /*if(mask[h-i] == 0) {
                cout << h-i << endl; found = 1; break;
            }*/
        }
        if(!found ) cout << "Better estimate needed\n";






        /*
        bool found = false, isChife = false;
        for(int i = 1; i <= ceil(h/2); i++) {
            for(int j = l; j <= h; j++) {
               if(cache[j] == i-1 || cache2[j] == i-1) {
                    isChife = 1;break;
               }
               if(cache[j] == j-i-1 || cache2[j] == j-i-1) {
                    isChife = 1;break;
               }
            }
            if(!isChife) {cout << i << endl; found = 1; break;}
        }
        if(!found ) cout << "Better estimate needed\n";*/
    }
    return 0;
}