UVA online 00151_PowerCrisis

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s