|
|
back to boardwhy my logic is wrong! help please!!! i've got WA#4. Posted by Bobur 27 Apr 2008 22:22 here is code const a : array [1..9] of integer=(2, 3, 5, 7, 11, 13, 17, 19, 23); var k, s, ans, x, k1 : integer; i, j : integer; p, q : int64; begin read(k, s); ans := 0; for i := 1 to 9 do if (s div a[i]) >= k then begin k1 := k; x := s div a[i]; if k1 > x-k1 then k1 := x-k1; q := 1; p := 1; for j := 1 to k1 do p := p * j; for j := x-k1+1 to x do q := q * j; ans := ans + q div p; end; if ans > 10000 then ans := 10000; writeLn(ans); end. where is wrong! this code give wrong answers for example: 2 26 3 45 3 29 2 25 .... thanks. Re: why my logic is wrong! help please!!! i've got WA#4. Posted by Bobur 28 Apr 2008 19:31 don't worry, i found my bug Re: why my logic is wrong! help please!!! i've got WA#4. Posted by Hrayr 21 Jun 2011 14:02 Hi,I use the same logic but wa#4 too,can you help me? Edited by author 21.06.2011 14:02 Re: why my logic is wrong! help please!!! i've got WA#4. If there is s = 50 and a[i] = 2 then the program tries to calculate 25! into integer type (var p) and may occur error. And this idea is wrong, for example: Let k=3 and s=25 you count the set 6 18 24 for prime 2 in cnk(25/2, 3) and also for 3 in cnk(25/3, 3). That is why your answer always exceeds the right one. you must subtract these set in each iteration. This will be: for (int i=2; res<10000; i++){ if (prime(i)){ n = s/i; if (n<k) break; else res += cnk(n,k); for (int j = 0; j<p_cnt; j++) if (n/prime[j]<k) break; else res -= cnk(n/prime[j],k); prime[p_cnt++] = i; } } I get AC with it. Edited by author 18.11.2011 23:37 |
|
|