ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1091. Tmutarakan Exams

why my logic is wrong! help please!!! i've got WA#4.
Послано Bobur 27 апр 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!
for example:
2 26
3 45
3 29
2 25 ....
thanks.
Re: why my logic is wrong! help please!!! i've got WA#4.
Послано Bobur 28 апр 2008 19:31
don't worry, i found my bug
Re: why my logic is wrong! help please!!! i've got WA#4.
Послано Hrayr 21 июн 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.
Послано [RSU_Tash]Nodirbek_Kuklamov 18 ноя 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