ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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
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