January 2019

M T W T F S S
 123456
78 910111213
14 151617181920
21222324252627
28293031   

За стиль благодарить

Развернуть метки

No cut tags

November 27th, 2007

taki_net: (Default)
Tuesday, November 27th, 2007 10:44 pm

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



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

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

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

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

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

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

taki_net: (Default)
Tuesday, November 27th, 2007 11:24 pm
Я нарочно оставил обычные туристкие фото - наряду со снимками городских хищников, они очень дополняют друг друга... Ну и последняя - слегка выбивается из этого ряда.Read more... )