Из кулуаров олимпиады по программированию

[taki_net]

Феерическое читерство

Рассказ слышал от одного из ребят. Итак, задача: даны два числа
k<n<10^6. Вывести в выходной файл число n, равное количеству простых чилел, лежащих между k и n.

Ограничение на память стандартное - 64Мбайт, на время работы - 2 с. Причем эксперимент показывает, что пересылка в памяти 10^8 элементов массива в тот же или другой массив занимает около 1 с, т.е. алгоритм, требующий порядка
n * n^0,5 операций (т.е. 10^9) не проходит ограничение по времени.

Внезапно одна из команд сдает решение, которое выполняется малые доли секунды и на всех тестах дает правильный ответ. Жюри в недоумении и обращается к исходному тексту программы (правила предполагают, что на тестирование сдается исходный код, который компилируется на компиляторе командной строки и потом запускается на тестах). Недоразумение развеивается.

1. Что увидело жюри, открыв файл программы?

2. Какое решение имело в виду жюри?

Комменты пока скрываются.

Comments

[kouzdra.livejournal.com]

Ребята протабулировали количество простых чисел от нуля до N

[ygam.livejournal.com]

В программе перечислены все простые числа между 1 и 1000000?

[elentin]

Меня бы никогда не взяли в маткласс, нельзя сдавать задачи с таким количеством исправлений :)

1. В массив забиты все простые числа от 2 до 1000000. Пробегаем по массиву, пока не встретим меньшее число, начинаем увеличивать счётчик, как только встретили большее - вываливаемся из цикла. Распечатываем наш счётчик. Всё.

Как забили простые числа в массив? Ну не руками, конечно. Написали вспомогательную программу, которую не надо сдавать жюри, перенаправили стандартный вывод (или записали прямо в файл), делов-то.

2. человеческое решение :-)

[kstoor.livejournal.com]

Рискну предположить, что читерский код содержал заранее вычисленный массив из (10^6)-2 элементов, где n-й элемент содержит количество простых чисел, меньших n. Какое решение ожидало жюри, не знаю. Вряд ли обычное решето Эратосфена.

[sergey-m.livejournal.com]

Если ограничение 64Мбайт, и числа меньше 10^6 - можно в вектор размером 10^6 загнать количество простых чисел до индекса элемента в векторе. А сам алгоритм будет состоять из того, чтобы взять элемент массива по индексу n и вычесть элемент массива по индексу k. Жюри, возможно, имело в виду некий хитрый алгоритм поиска простых чисел (похожий на "решето Эратосфена" и т.п.).

[golergka.livejournal.com]

1. Нагугленный спислк простых чисел от 1 до миллиона или использование стандартной библиотеки/стандартной ф-ции
2. Сходу не скажу... :(

[ormuz.livejournal.com]

понятно ж - все простые числа меньше 1 000 000 влезут в 64 мегабайта как пить дать.

а хотели наверное решето эратосфена хитрое.

[genebee.livejournal.com]

1 -- таблицу простых чисел от 2 до 10^6? ;)

[(Anonymous)]

Статическую таблицу простых чисел, и алгоритм поиска нижней/верхней грани.

[kot-ivanovich.livejournal.com]

1. Binary search in a precomputed array of prime numbers? Though it could fail on compilation time...
2. No idea, will think later.

[fakir57.livejournal.com]

Думаю, что
1) Массив простых чисел от 2 до миллиона
2) Начинать надо всегда с 2, независимо от k. Каждый раз мы проверяем делимость текущего числа только на все уже известные простые числа, которых порядка ln(n). Поэтому общее время работы - n*ln(n), что есть порядка 10^8, и нас устраивает.

[kondybas.livejournal.com]

Статиком вбитая в код последовательность простых чисел от 1 до 10"6. И простой линейный поиск по массиву. Потом один индекс вычесть из другого - и все.

[rockmefast.livejournal.com]

1. Массив из списка простых чисел от 0 до 10^6 сгенерированный любым алгоритмом. И фильтр вывода.
2. Не знаю..

[spartach.livejournal.com]

Может, так?
1. return floor(n/log(n) - k/log(k));
Точнее, надо бы брать целое число, ближайшее к x, - не помню, как это зовется.

2. Если n мало (например, < 10^5), то рисуем решето Эратосфена. Иначе чтобы успеть, k должно быть близко к n, и проверяем на простоту все числа от k до n, сравнимые с +-1 mod 6.

[akusasik.livejournal.com]

Ребята во время компиляции считали все простые числа от 1 до 10^6?

[(Anonymous)]

1. Список простых чисел <1000000 (всего 80 тысяч)
2. Алгоритм тот список порождающий

[pilpilon.livejournal.com]

что-то вроде n/ln(n) - k/ln(k) ?
а жюри имело ввиду заранее вычислить список всех простых меньше тысячи и вбить в массив в тексте программы?

[v-l-a-d.livejournal.com]

Думаю, в исходнике были захардкодены все простые числа от 1 до 1000000 :)

[vvagr.livejournal.com]

1. Формулу Гаусса? :-)

[mikev.livejournal.com]

1. Таблицу простых чисел, инициализирующую массив (всего около 80000 чисел)
2. Решето Эратосфена

а в чем проблема?

[a-shen.livejournal.com]

я, наверно, чего-то не понимаю - надо уметь вычислять (дважды) количество простых чисел, меньших n. В принципе, в 64 мегабайта можно поместить просто эту самую таблицу. Но если это слишком много, можно хранить данные с некоторым шагом и вычислять недостающие с помощью проверки простоты (или таблицы простых чисел)

или имеется в виду что-то другое?

[herr-widerlich.livejournal.com]

Хм... не знаю, что предполагало жюри, но с таким раздольем по памяти я бы написал вспомогательную программу, которая высчитала бы все простые числа до миллиона включительно - это что-то около пяти-шестимегабайтного массива. :) А дальше сама программа сводится к двум бинарным поискам в этом массиве. :)

ЗЫ. Хотя есть ещё более читерский вариант - использовать оценку Чебышева количества простых чисел, меньших заданного. :))))
n/(ln(n)-4) > p(n) > n/ln(n)
Ну, или в каноническом варианте: 1.1*n/ln(n) > p(n) > 0.92*n/ln(n)
:-)

[slavka.livejournal.com]

жюри предполагали что ребятки напишут программу, подбирающую простые числа (и пересчитывающую их)

а ребятки просто забили в программу таблицу простых чисел?

[fakir57.livejournal.com]

2) Прошу прощения, сглючил. Поскольку простых чисел порядка n/ln(n), то можно делать так: проверять все числа с остатками 1 и 5 при делении на 6 (т.е. n/3 чисел) на делимость на все уже известные простые числа, меньшие \sqrt{n} (которых примерно sqrt(n) / ln(sqrt(n))).
В итоге получаем:
n/3 * (sqrt(n) / (ln(n)/2)) = 2/3 * n^1.5 / ln(n), что есть 10/9 * 10^8.

[(Anonymous)]

в исходнике массив простых чисел :)

[sorotokin.livejournal.com]

Я бы сказал, ожидалось увидеть что будет проверяться делимость только на простые числа меньшие 1000. А школьники, небось, просто захардкодили все простые числа до 1000000 в текст программы.

[bljakhin-mukher.livejournal.com]

Первое, что приходит в голову: массив простых чисел до 1 000 000.

[igordaily.livejournal.com]

по-видимому, программа использовала готовый список простых чисел, содержащихся в промежутке между 1 и 1000000

жюри же, очевидно, хотело, чтобы алгоритм был частным случаем решения подобной задачи для n<k<m, где m=10^6

[ibigdan.livejournal.com]

попробую угадать - сгенерировали таблицу простых чисел от 0 до 10^6, вывели в файл, подключили как массив к программе и при задании k и n просто отыскивали их позиции в массиве, выдавая на выходе разницу индексов.

[scolar.livejournal.com]

C++ программа, в которой всё посчитано на шаблонах в compile-time?

[malyj-gorgan.livejournal.com]

Все что помню о простых числах -- определение. :) Исходя из этого, поскольку ограничений на размер исходника Вы не накладывали,

1. код программы -- определение массива из всех простых чисел меньше миллиона (итого 78948, исходник получается немногим больше полумега). Дальше понятно: считаем количество элементов между k и n.

2. а кто их знает? ;) Если разрешается в коде иметь массив 168 простых чисел меньше тысячи (если не разрешается, придется при исполнении генерировать массив простых чисел меньше/равно корню из n, что увеличит время на соответствующее, но несмертельное число операций). Дальше остается перебор. Если не умничать, и напрямую пропускать при переборе только четные числа, то получается максимум n / 2 * 167 целочисленных операций mod(). Самую малость меньше, учитывая, что простые числа до тысячи (или корня n) уже и так известны. Такой порядок алгоритма (<10^8) проходит ограничение по времени?

[raindog-2.livejournal.com]

1) Они увидели там большой массив.
static int p[1000000] = { 0, 0, 1, 2, 2, 3, 3, 4, ... };
где p[x] - количество простых чисел не превышающих x.
После этого программа выводила p[n] - p[k] в const time.

2) Жюри ожидало увидеть проверку на "простоту" для каждого числа между k и n. В самом наивном варианте, чтобы проверить x, на простоту, нужна итерация от 2 до sqrt(x). Отсюда n * n^0.5.

[kondybas.livejournal.com]

Да, а "правильное" решение, по всей видимости, такое:

int count(int val)
{
   int retval = val;

   for (d=2; d<int(sqrt(val)); d++)
      retval -= val % d;

   return retval;
}

int main()
{
   k = lolim;
   n = hilim;

   printf("%d\n", count(hilim) - count(lolim));
}

((from Alex Dribin))

[(Anonymous)]

Ну в коде, понятное дело, был список всех простых чисел от 1 до 10^6.
Кстати, это наиболее профессионально грамотное решение ;)
А вот что было в голове у жюри я не берусь угадать. Надеюсь, что не решение методами метапрограмирования имени тов. Александреску? ;)

[nickgrigoriev.livejournal.com]

1. Загнали список простых чисел от 1 до 10^6 в отсортированный статический массив прямо в коде? Их там 78500, ничего страшного; а кодогенератор пишется в три строчки... Останется найти индексы начала и конца того куска, где k < p < n; при бинарном поиске это требует несколько десятков операций. Будет летать, реально :-).

2. Ну, наверное, как-то так:

- найти все простые числа от 2 до sqrt{n) решетом Эратосфена - max 170 штук,
- посчитать n - n/2 - n/3 - n/5 .... + n/2/3 + n/3/5 ... - n/2/3/5 ...
- посчитать то же для k и вычесть.

Первый шаг занимает ~ 500 x 10 вычеркиваний, второй и третий ~ 170 x 170 / 2 целочисленных делений и сложений - должно уместиться. Но со статическим массивом не сравнить, конечно :-).

Без попытки ответить.

[bv.livejournal.com]

Ребята доказали по ходу гипотезу Римана, вероятно.
Такие задачки нам академик Ершов давал в 74 году, когда я программированию учился. На БЭСМ-6 решали. Теперь квалификацию потерял.
Но если бы у меня была практическая задача, то я бы просто использовал готовый массив простых чисел, до лимона их не так много.

[kot-ivanovich.livejournal.com]

2. Чего-то мне лень напрягаться, но мне кажется, что аккуратно запрограммированного решета Эратосфена должно хватить. Простых чисел до 1000 всего 168, а на вычёркивание простого p нужно всего N/p операций. С очевидными ухищрениями (типа цикла с шагом 6) должно проехать. Есть, конечно, более продвинутые методы, но довольно трудно ожидать их знания от школьников, да и запрограммировать их за пару часов вряд ли посильно.

[avkh.livejournal.com]

в коде прописан предварительно посчитанный массив простых чисел до 1,000,000

[avkh.livejournal.com]

ой, про второй вопрос я пока не успел подумать :))

[beldmit.livejournal.com]

1. Список простых чисел от 2 до 10^6.

[avkh.livejournal.com]

на второй вопрос ответ возможно такой (хотя это тоже по-сути шулерство как и в первом комменте):
Разбить этот миллион на диапазоны, скажем 1000 диапазонов по 1000 или иначе (надо прикинуть по быстродействию, но это какжется нормальный вариант).
Посчитать количество простых в каждом диапазоне и вбить в код.
На хвостах (огрызках диапазонов) посчитать уже программно.

[almor.livejournal.com]

Посчитали по долгому алгоритму, а потом в программе просто сделали вывод чисел. :)

[ex-clyde404.livejournal.com]

Жюри увидело массив всех простых чисел от 1 до 10^6, тупо вбитый в исходный код программы. Если Вам несложно, когда раскроете комменты - ответте на этот что угодно, чтоб мне извещение в почту пришло - обидно будет пропустить.

[yyi.livejournal.com]

я наверное торможу со страшной силой, но я не понимаю [предполагая к>0] как n может быть больше чем 3. или это опечатка - в условии говорится что вывести нужно n, но n это и одно из данных чисел и количество простых чисел между n и k<n?