10889 - The Lost Gift

[Jan]

I have solved the problem but I am getting WA.

Can anyone post some test cases.

Thanks in advance.

[kai]

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]

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.

[mf]

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

[Jan]

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.

[kai]

Looks like your problem is floating point error.

Input:
17925078 17931067

Output:
No. of black balls invalid

[Jan]

Finally Got Accepted!!!

Thanks Kai.

It was actually floating point error. Thank u again for pointing that.

[bijon]

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

Thanks in advance .[/b]

[Cho]

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]

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.

[Cho]

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.

[bijon]

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.

[Cho]

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

[shamim]

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]

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.