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

[taki_net]

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

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

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

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

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

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

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

Comments

[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 целочисленных делений и сложений - должно уместиться. Но со статическим массивом не сравнить, конечно :-).