10889 - The Lost Gift

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

Moderator: Board moderators

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

10889 - The Lost Gift

Post by Jan » Tue Aug 09, 2005 11:32 am

I have solved the problem but I am getting WA. :-?

Can anyone post some test cases.

Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

kai
New poster
Posts: 5
Joined: Mon Aug 08, 2005 2:36 pm
Location: Japan

Post by kai » Tue Aug 09, 2005 12:05 pm

Hope it helps...

Input:

Code: Select all

3 4
6 2
66 55
0 0
Output of my AC program:

Code: Select all

No. of black balls invalid
No. of black balls invalid
0 23

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

Post by Jan » Tue Aug 09, 2005 12:28 pm

Thanks, but My code returns same output.

Here is my code

Code: Select all

..........................
..........................
Cut After Accepted........
..........................
..........................
Can anyone tell me why I m getting WA?

Thanks.
Last edited by Jan on Tue Aug 09, 2005 1:58 pm, edited 2 times in total.
Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Aug 09, 2005 12:49 pm

For "1 0", the output should be "0".

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

Post by Jan » Tue Aug 09, 2005 1:14 pm

Thanks mf, but I think there are no cases like this in the input file.

And another thing... for 1 0 I think the result should be "Black ball invalid". Beacuse

1 Red ball
0 black ball

So if u take a ball it must be red. So the probability is 1 not 1/2.
Last edited by Jan on Tue Aug 09, 2005 1:32 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

kai
New poster
Posts: 5
Joined: Mon Aug 08, 2005 2:36 pm
Location: Japan

Post by kai » Tue Aug 09, 2005 1:28 pm

Looks like your problem is floating point error.

Input:
17925078 17931067

Output:
No. of black balls invalid

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

Post by Jan » Tue Aug 09, 2005 1:48 pm

Finally Got Accepted!!! :D

Thanks Kai.

It was actually floating point error. Thank u again for pointing that. :wink:
Ami ekhono shopno dekhi...
HomePage

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Wed Aug 24, 2005 11:47 am

Can some one give me some test cases for this problem?
i can't find bug in my code.

Thanks in advance .[/b]

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Aug 24, 2005 1:19 pm

Try this input:

Code: Select all

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
3 5
3 6
3 7
4 1
4 2
4 3
4 3
4 5
5 1
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 11
5050 3500
5050 4000
5050 4500
5050 4950
5050 5000
5050 5151
5050 5500
0 0
Output:

Code: Select all

No. of black balls invalid
No. of black balls invalid
0
No. of black balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
0
No. of black balls invalid
No. of black balls invalid
No. of black balls invalid
1
0
No. of black balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
No. of black balls invalid
No. of black balls invalid
0
No. of black balls invalid
No. of black balls invalid
No. of black balls invalid
3
2
1
No. of black balls invalid
1450
950 1151
450 651
0 201
151
0
No. of black balls invalid

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Fri Aug 26, 2005 7:44 pm

Thanks Cho for your reply.
My prog gives same output but still wrong answer.
is there any spacial case?
if possible please give some more input data.

thnaks again.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Aug 26, 2005 8:09 pm

Some more input:

Code: Select all

15470 15792
18336 18036
588070 589307
8552 237
954271 955459
96580 95930
720600 719146
700336 701929
2446 31948
8515 8348
909226 909657
652653 654892
222778 221541
802011 801099
63546 63462
55611 55378
59340 59607
1081185 1083000
11778 29254
161596 161030
14198 12456
318003 317434
12246 12324
85491 85840
105 88
458403 457943
19701 19533
25679 19927
24962 14802
26364 20856
0 0
My output:

Code: Select all

No. of red balls invalid
109 492
No. of black balls invalid
No. of red balls invalid
194
211 1090
254 2655
No. of black balls invalid
No. of red balls invalid
37 298
918
No. of black balls invalid
570 1905
2179
441
567
78
No. of black balls invalid
No. of red balls invalid
1135
No. of red balls invalid
1367
79
65
3 32
1418
367
No. of red balls invalid
No. of red balls invalid
No. of red balls invalid
My input are not critical at all. Just some random cases. Since there is no input range specification, the input integers may be quite large. Beware of overflow if you square anything. My code only works if the input integer is less than 200000000, so there should be no input larger than that.
I code, therefore I am.

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Sat Aug 27, 2005 5:36 am

Again same output.why wrong answer ? My procedure is :

1. First I solve the equation to find the roots.
2.if the roots are fractional then R false.
3.Otherwise . if they are not less than .7 or negetive B false.
4.if not,print the root / roots by checking them.

Here is the parts of my code:

Code: Select all

works now.
Do the calculation in integer data type.
Am i wrong ?

Thanks again.
Last edited by bijon on Sun Aug 28, 2005 9:45 am, edited 1 time in total.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Aug 27, 2005 6:31 am

Then it's probably because of the floating point error. Try to revisit your formula. It's possible to solve everything without any floating point operation. Maybe your code will fail on some of the following cases:

Code: Select all

202566 141351
1617301 1133370
230181 161602
626640 439432
1581531 1108317
428275 299145
1383616 969696
922761 646884
1842240 1290912
291466 204561
1488675 1040865
1711 1239
1794565 1257522
182106 127897
546535 381843
220116 154546
334971 235053
560211 392889
920046 643083
668746 467313
521731 364497
601156 420042
1376970 965041
1549680 1083544
113526 79135
1006071 705243
289180 201894
436645 306306
1217580 851214
182106 127897
1128 1081
67896 68265
798216 799480
1174278 1175811
601156 602253
1499046 1497315
976503 975106
153 136
509545 510555
362526 363378
154290 154846
1840321 1838403
43956 44253
1133265 1134771
1646205 1644391
1082656 1084128
357435 358281
1755001 1756875
1608321 1606528
626640 627760
360825 359976
1092981 1091503
1544403 1546161
741153 739936
79003 79401
1396956 1398628
343206 342378
10296 10153
296065 295296
1383616 1385280
0 0
Output:

Code: Select all

60579
482133 485730
67901 69258
186089 188328
471436 474993
128205
412257 415584
274519 277236
549409 553248
86142 87669
446085
414 531
535149 538938
53606 54813
163647
64907 66234
99100 100737
166264 168381
275607
200277
156213
180018
410270 413589
464376
33915
299410 302247
86526
129405 131274
364806
53606 54813
0 95
0
0
0
0
0 3463
0 2795
0 35
0
0
0
0 3837
0
0
0 3629
0
0
0
0 3587
0
0 1699
0 2957
0
0 2435
0
0
0 1657
0 287
0 1539
0
I code, therefore I am.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Aug 27, 2005 7:08 am

Are you considering the case, where the number of black balls found is more than the calculated value of original number of black balls.

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Post by bijon » Sat Aug 27, 2005 10:59 pm

Thanks again Cho. same output again without any modify. its may be floating point error. Ok, i'll try to solve without floating point oparetion. but i can't understand without floating point calculation how do i know that red balls are invalid?

To Shamim

when the roots become negetive then this case is cheked autometically.
is it ?

Thanks for reply.

Post Reply

Return to “Volume 108 (10800-10899)”