10254 - The Priest Mathematician

[little joey]

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:

Code: Select all

152044948844121230332399992845875776147947521

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

[Ivan Golubev]

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

Code: Select all

202100503361683772220167446845875776147947521

[little joey]

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....

[little joey]

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

[PJYelton]

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]

[Larry]

If the input was like:

Code: Select all

1
2
3
4
5
...
9999
10000

I suggest you use Dynamic Programming. Find a recurrence for it.

[PJYelton]

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!

[Larry]

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

[drewsome]

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]

[Riyad]

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

[sidky]

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