ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1091. Tmutarakan Exams

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.
Posted by [RSU_Tash]Nodirbek_Kuklamov 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