OJ Board

Got the right answer for input 64, which makes me think I'm on the right track, but still got WA.
Can anybody verfy the output for 9876? I got: Since no exact output specification is given, I assume it's bigint.
There are no tricky input cases AFIK, or did I overlook something?

Help appreciated,
-little joey

Yeah, bigint is necessary to solve this problem. However my accepted solution for input 9876 produces this answer:

Thanks man!
Looks like I made a mistake in my semi-automaticly typed in bigint code, since the last 18 digits are the same. Stupid me. Trying to invent the wheel again and again and again, and always making silly mistakes....

Yep, forgot to add the carry in my double_bigint() function. AC now. Thanks again Ivan.

I don't understand why this problem gives me time limit exceeded, since on my not-so-fast computer it solves the highest limit 10000 in only half a second. It must be something stupid, yet I don't see what. I'm not sure how others solved it, but I noticed that I can figure out the answer without mimicking the disk movements. Basically you add 2^2 3 times, then 2^3 4 times, then 2^4 5 times etc and it gets the correct answer up to 10000 no problem. Here is the code, minus my BigNum class to save space which I know is correct and fast. Anyone see how this could possible get TLE while my comp runs in less than a second?
[cpp]
int main()
{
int num;

while (cin>>num)
{
if (num==0)
{
cout<<"0"<<endl;
continue;
}
if (num==1)
{
cout<<"1"<<endl;
continue;
}
if (num==2)
{
cout<<"3"<<endl;
continue;
}
if (num==3)
{
cout<<"5"<<endl;
continue;
}

BigNum n(num);
BigNum count(3);
BigNum numadd(3);
BigNum total(5);
BigNum power(4);
while (count<n || count==n)
{
if (count+numadd>n)
{
BigNum d=n-count;
d*=power;
total+=d;
}
else
{
BigNum d=numadd*power;
total+=d;
}

power*=2;
count+=numadd;
++numadd;

}

cout<<total<<endl;

}


return 0;
}
[/cpp]

If the input was like:
I suggest you use Dynamic Programming. Find a recurrence for it.

Thanks, yeah I simplified it a little and used dynamic programming and got AC on it. For some reason I thought that you had 10 seconds for each single input like over at topcoder.com, instead of 10 seconds for the entire file input. My bad!

=) Ya, but the problems here are more "fun" most of the time.. but maybe that's just me..

Hi,

I get the right answer for n = 64 and n = 28, but when I type in n = 9876 I get:
6964824117983874234650500427748868209542865000190576981818345
9167875096365227972472038355305206881965379346125792003500964
48775287769802767937463111146298807126530166456649252977

Some other test values I tried:
n = 100: 172033
n = 200: 14680065
n = 256: 100663297
n = 400: 6442450945
n = 1000: 253642731468772868177

I've checked my recurrence a couple times, and I'm pretty confident in it. Here the heart of my dp table generation:
[cpp] table[0] = 1; table[1] = 3; table[2] = 5;

for (int i = 3; i < 10000; i++) {
BigInt a = table * 2 + 1;
BigInt b = table * 2 + 3;
int n = 2;

while (b < a) {
n++;
a = b;
b = table * 2 + (exp(2, n) - 1);
}

table = a;

}
[/cpp]
Any thoughts? Any help would be much appreciated Thx.[/b]

can u tell me what is the output for 10000 is ....
i am having output limit exceeded .... may be i am doing something wrong..any help will appreciated...
Regards
Riyad

output for 10000 is

374931278650296101567069263458900577819295745

some more inputs:

input:

1
2
3
4
5
6
7
8
9
10
12
213
12
123
1000
129
10000
2138
2388
9982
2923
3789
1248

output:

1
3
5
9
13
17
25
33
41
49
81
23068673
81
557057
932385860354049
753665
374931278650296101567069263458900577819295745
2232056032918855745537
32171121664549458018305
349842940301949150532841580402171171125067777
5553502983854702771306497
10290376576559723535098970113
39969446692913153

good luck