10294 - Arif in Dhaka (First Love Part 2)

Ivan Golubev · Post by **Ivan Golubev** » Wed Aug 07, 2002 9:56 am

What is the real limit for input numbers?

I've used such construction and get assertion failed.
[c]int main(void)
{
int n, k;
UINT64 nk;

while (scanf("%d %d\n", &n, &k) == 2) {
assert(n > 1 && n < 51);
assert(k > 0 && k < 11);
nk = getneck(n, k);
printf(I64D" "I64D"\n", nk, getbrac(nk, n, k));
}
return 0;
}[/c]

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Aug 08, 2002 7:51 am

I have similiar problem - calculating numbers isn't difficult ...
I think, that in input exist numbers like 1 for N and 0 for t .... upper limit is probably good, because I didn't get RTE

I haven't time to check it now, but maybe afternoon I try to resilve it

)

Dominik Michniewski · Post by **Dominik Michniewski** » Thu Apr 17, 2003 8:22 am

I've got Accepted now ....
They are (I found this two only) two common problems with this problem:
1. Exist (probably) test with N=1
2. It's possible to get overflow when we calculate values from formula ...

Best luck in hunt
DM

Moha · Post by **Moha** » Wed Dec 14, 2005 4:55 pm

I use long double, and when i want to print the result, i cast it to long long,
But i got WA!
can anybody post some testcases for this problem?
my prgram find two negative value for n=50,k=10.

daveon · Post by **daveon** » Mon Jan 02, 2006 10:54 pm

Hi,

Code: Select all

20 2
20 3
20 4

Code: Select all

52488 27012
174342216 87230157
54975633976 27489127708

I don't think there is a need for doubles.

Moha · Post by **Moha** » Thu Jan 05, 2006 1:31 am

Hi daveon,
My output is same as your ouput.
can you send some other testcases?
what is your output for N=50, t =10?
thanks

daveon · Post by **daveon** » Thu Jan 05, 2006 11:18 pm

N=50 T=10 results in output greater than 11 digits. Which means it is invalid input.

Your problem might lie in your totient function. I hardcoded my 51 values for euler_phi(x) for 1<=x<=51.

Moha · Post by **Moha** » Mon Jan 09, 2006 2:48 am

Hi daveon,
Would you please test these testcases? I generate all the samples which their results is less than 12digit.
input:

1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12 9
12 10
13 1
13 2
13 3
13 4
13 5
13 6
13 7
13 8
14 1
14 2
14 3
14 4
14 5
14 6
14 7
15 1
15 2
15 3
15 4
15 5
15 6
16 1
16 2
16 3
16 4
16 5
17 1
17 2
17 3
17 4
17 5
18 1
18 2
18 3
18 4
19 1
19 2
19 3
19 4
20 1
20 2
20 3
20 4
21 1
21 2
21 3
22 1
22 2
22 3
23 1
23 2
23 3
24 1
24 2
24 3
25 1
25 2
25 3
26 1
26 2
26 3
27 1
27 2
28 1
28 2
29 1
29 2
30 1
30 2
31 1
31 2
32 1
32 2
33 1
33 2
34 1
34 2
35 1
35 2
36 1
36 2
37 1
37 2
38 1
38 2
39 1
39 2
40 1
40 2
41 1
41 2
42 1
43 1
44 1
45 1
46 1
47 1
48 1
49 1
50 1

output:

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
1 1
3 3
6 6
10 10
15 15
21 21
28 28
36 36
45 45
55 55
1 1
4 4
11 10
24 20
45 35
76 56
119 84
176 120
249 165
340 220
1 1
6 6
24 21
70 55
165 120
336 231
616 406
1044 666
1665 1035
2530 1540
1 1
8 8
51 39
208 136
629 377
1560 888
3367 1855
6560 3536
11817 6273
20008 10504
1 1
14 13
130 92
700 430
2635 1505
7826 4291
19684 10528
43800 23052
88725 46185
166870 86185
1 1
20 18
315 198
2344 1300
11165 5895
39996 20646
117655 60028
299600 151848
683289 344925
1428580 719290
1 1
36 30
834 498
8230 4435
48915 25395
210126 107331
720916 365260
2097684 1058058
5381685 2707245
12501280 6278140
1 1
60 46
2195 1219
29144 15084
217045 110085
1119796 563786
4483815 2250311
14913200 7472984
43046889 21552969
111111340 55605670
1 1
108 78
5934 3210
104968 53764
976887 493131
6047412 3037314
28249228 14158228
107377488 53762472
348684381 174489813
1000010044 500280022
1 1
188 126
16107 8418
381304 192700
4438925 2227275
32981556 16514106
179756983 89937316
780903152 390582648
2852823609 1426677525
9090909100 4545954550
1 1
352 224
44368 22913
1398500 704370
20346485 10196680
181402676 90782986
1153450872 576960734
5726645688 2863912668
23535840225 11769248715
83333418520 41669459260
1 1
632 380
122643 62415
5162224 2589304
93900245 46989185
1004668776 502474356
7453000807 3726912175
42288908768 21145502960
1 1
1182 687
341802 173088
19175140 9608050
435970995 218102685
5597460306 2799220041
48444564052 24223929112
1 1
2192 1224
956635 481598
71582944 35824240
2034505661 1017448143
31345666736 15673673176
1 1
4116 2250
2690844 1351983
268439590 134301715
9536767665 4768969770
1 1
7712 4112
7596483 3808083
1010580544 505421344
44878791365 22440372245
1 1
14602 7685
21524542 10781954
3817763740 1909209550
1 1
27596 14310
61171659 30615354
14467258264 7234153420
1 1
52488 27012
174342216 87230157
54975633976 27489127708
1 1
99880 50964
498112275 249144711
1 1
190746 96909
1426419858 713387076
1 1
364724 184410
4093181691 2046856566
1 1
699252 352698
11767920118 5884491500
1 1
1342184 675188
33891544419 16946569371
1 1
2581428 1296858
97764131646 48883660146
1 1
4971068 2493726
1 1
9587580 4806078
1 1
18512792 9272780
1 1
35792568 17920860
1 1
69273668 34669602
1 1
134219796 67159050
1 1
260301176 130216124
1 1
505294128 252745368
1 1
981706832 490984488
1 1
1908881900 954637558
1 1
3714566312 1857545300
1 1
7233642930 3617214681
1 1
14096303344 7048675960
1 1
27487816992 13744694928
1 1
53634713552 26818405352
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

I really don't know where is my problem, but i know My code should has problem, otherwise it got accepted!

daveon · Post by **daveon** » Tue Jan 10, 2006 3:51 am

Your output is correct.

You could also email me your code if you like.

Moha · Post by **Moha** » Wed Jan 11, 2006 12:01 am

I finaly got Accepted!
I did a mistake.
Thanks daveon!

Solaris · Post by **Solaris** » Mon Nov 06, 2006 8:27 pm

I have solved the problem using the Formula provided in http://mathworld.wolfram.com
I wanted to know whether there is any recurrance or DP solution for this problem ...