why 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*