10207 - The Unreal Tournament

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

sERbU
New poster
Posts: 6
Joined: Thu Apr 08, 2004 10:06 am
Location: Barcelona

10207 WA Could anybody give me more input/output tests ?

Post by sERbU »

Hi. I'm getting WA for problem 10207, but I don't know why. I tested my program against a reasonably large (and in my opinion complete) input/output combination, and my program gets everything right (newlines and so too).

I'd like to ask whether anybody minds giving me some sample input/output to test my program against, help is appreciated a lot, thanks!
:P

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

Post by marian »

You do not need to use DP to compute Numberofcalls(i,j). There is explicit formula, which you are asked to find in this problem. Hint: Binomial coefficients.

skinnyguy
New poster
Posts: 17
Joined: Fri Oct 22, 2004 3:41 pm

10207... please help

Post by skinnyguy »

well the question says "if P(i,j) is undefined print -1 with similer formatting
but for every input we output two lines right?
the first one will be -1... but what do we put in the second line?
i was able to work out the "mathematics" behind the question and am getting the outputs correct for the sample provided, but the online judge reports wrong answer... maybe because i print
-1
0
for invalid inputs?
finally, how large can the inputs be? i mean for large values of i and j... the number of recursive calls(even though i used a formula which i am certain is correct) will overflow an integer
please help

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

For invalid input, output this

-1.00000
0

The range of i, j are given clearly, and you require BigInt to solve this problem. This problem is not that trivial, beside finding the maths. logic behind, you have to fight with time limit and memory limit too.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

skinnyguy
New poster
Posts: 17
Joined: Fri Oct 22, 2004 3:41 pm

thank you

Post by skinnyguy »

i'm kind of a newbie(this was like the 20th problem i cracked)...
yes i got something like accepted-actually it says a presentation error
this was the first problem for me that would require lond double and big integer... but i worked it out
thank you for the help...

liuchangacm
New poster
Posts: 3
Joined: Wed Mar 09, 2005 1:28 pm

10207 help

Post by liuchangacm »

What may the undefined P(i,j) be?

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen »

I am wandering the output of

Code: Select all

0.5 1
1000 0
Can someone help?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Wei-Ming Chen wrote:I am wandering the output of
Input:

Code: Select all

0.5 1
1000 0
0.5 0
Can someone help?
My accepted code returns

Output:

Code: Select all

0.00000
1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10207 - The Unreal Tournament

Post by brianfry713 »

A straight forward DP in JAVA using BigInteger got me AC in just over 2sec. i=0 and j=0 is the only special case. For this input:

Code: Select all

0.5 3
0 0
452 0
0 251
.1 0
AC output is:

Code: Select all

-1.00000
0
0.00000
0
1.00000
0
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 102 (10200-10299)”