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

Обсуждение задачи 1091. Тмутараканские экзамены

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
   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.
Послано 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