Solution UVA: 679 - Dropping Balls

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss679 - Dropping Balls	Accepted	C++11	0.270	0.000	4922	36 secs ago

Suggest:

The first, we create branch from ball 1 (we will have 1, 2, 4, 8, ...) and save result F[deapth(i)] [1] =node(i). 

Then continue create branch ball 2 (we will have 1, 3, 6, 12, ...) and save result F[deapth(i)] [2] =node(i).

So on ...

Finally, we have a tree and result dynamic programming top down ! 

Happy Coding :)

#include<bits/stdc++.h>

#define FOR(i, a, b) for(int i=a; i<=b; i++)

using namespace std;

const int maxNode= (int)pow(2, 20) - 1;

const int maxBall= 524288;

int F[21][maxBall+1];

bool state[maxNode+1];

int t, n, depth, ball;

   

void f(int node, int depth, int ball){

    if (node > maxNode) return;

    if (state[node]) f(node*2+1, depth+1, ball);

    else f(node*2, depth+1, ball);

   

    if (F[depth][ball] == 0) F[depth][ball]= node;

    state[node] = (state[node] ? false : true);

}

void init(){

   

    FOR(i, 1, maxBall) f(1, 1, i);

}

void solve(){

   

    cin >> depth; if (depth == -1) exit(0);

    cin >> ball;

   

    cout << F[depth][ball]<<"\n";

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    init();

   

    cin >> t;

    while(t--){ solve();}

}