10254 - The Priest Mathematician

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10254 - The Priest Mathematician

Post by little joey » Sat Aug 09, 2003 3:40 pm

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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Sat Aug 09, 2003 4:20 pm

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

Code: Select all

202100503361683772220167446845875776147947521

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Aug 09, 2003 4:32 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Aug 09, 2003 4:48 pm

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

PJYelton
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 pm

10254 The Priest Mathematician TLE??

Post by PJYelton » Mon Aug 25, 2003 7:03 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Aug 25, 2003 7:22 pm

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
New poster
Posts: 20
Joined: Fri May 30, 2003 6:56 pm

Post by PJYelton » Tue Aug 26, 2003 5:54 pm

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! :oops:

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Aug 27, 2003 5:40 am

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

drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

Post by drewsome » Tue Dec 23, 2003 4:09 pm

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]

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

input output

Post by Riyad » Sat Oct 16, 2004 7:09 am

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Sun Nov 20, 2005 8:38 pm

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

Post Reply

Return to “Volume 102 (10200-10299)”