10777 - God! Save me

All about problems in Volume 107. 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
kathmolla
New poster
Posts: 6
Joined: Tue Nov 30, 2004 2:27 am

10777 - God! Save me

Post by kathmolla »

Can anyone help me solving this problem. I used the following formula
ans = sum of ( pi*|xi|) for all i / sum of pi for all i where xi is positive.

I suppose this formula is correct . If it is then is there any special input
that can make this ans wrong.

thanks in advance.
hey why doing this

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll »

Your approach is the same as in my AC code, so you should get accepted also. Except you didn't mention that you should print "God! Save me" (without quotes) if all xi are negative, make sure you do that :D.

Actually, there are potential floating point problems. I rearranged my code a bit to closer resemble yours and ran it on 1000 random generated test cases, and got some results that were different by 0.01. Try moving the divisions in your code and see if you get a different result.

The trickiest input I could figure out was this:

Code: Select all

2

3
3 0.0
-3 0.5
-3 0.5

3
2 1.0
3 -1.0
-3 1.0
output:

Code: Select all

Case 1: God! Save me
Case 2: God! Save me
The last one is sneaky, and I'm not sure it occurs in the input. The problem description only says that the sum of all pi equals 1...

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz »

Thanks kathmolla. I got accepted by one submission using your formula.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

I used the correct formula, but forgot to print the case number for the "God! Save me" case and got many WA.

Post Reply

Return to “Volume 107 (10700-10799)”