Discussion @ 1091. Tmutarakan Exams @ Timus Online Judge

Bobur why my logic is wrong! help please!!! i've got WA#4. [3] // Problem 1091. Tmutarakan Exams 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.

Bobur Re: why my logic is wrong! help please!!! i've got WA#4. [2] // Problem 1091. Tmutarakan Exams 28 Apr 2008 19:31

don't worry, i found my bug

Hrayr Re: why my logic is wrong! help please!!! i've got WA#4. [1] // Problem 1091. Tmutarakan Exams 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

[RSU_Tash]Nodirbek_Kuklamov Re: why my logic is wrong! help please!!! i've got WA#4. // Problem 1091. Tmutarakan Exams 18 Nov 2011 23:01

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

Discussion of Problem 1091. Tmutarakan Exams