Как непросто быть школьником! Именно такие мысли чаще всего посещают Петю после уроков математики. Сегодня учительница рассказывала, что такое простые числа. Петя впервые услышал о них. Оказывается, простое число — это такое натуральное число, которое имеет ровно два различных натуральных делителя, то есть делится без остатка только на единицу и на само себя. После урока Петя и его друг Сережа придумали такую игру: один называет два числа A и B, а другой говорит, сколько нулей на конце произведения всех простых между A и B включительно. Петя заметил, что Сережа отвечает на вопрос намного быстрее, чем он сам, и очень просит вас ему помочь. Напишите для Пети программу, которая будет отвечать на вопросы Сережи.

Оценив последние успехи вашего друга в экономическом отделе компании, владеющей сетью маршрутных такси, директор повысил его до главного диспетчера. Теперь друг указывает, на какой маршрут должна выходить та или иная маршрутка.

В автопарке компании есть \(n\) маршруток, \(i\)-ая маршрутка номинально вмещает \(a_i\) пассажиров. По договору с департаментом транспорта города компания обязана обслуживать \(m\) маршрутов. Накопленная статистика говорит, что оптимальнее всего, если \(j\)-ый маршрут обслуживает такси номинальной вместимостью \(b_j\) пассажиров. Каждая маршрутка приписывается не более чем к одному маршруту, каждому маршруту приписывается не более одной маршрутки.

Разумеется, каждый уважающий себя диспетчер при назначении маршруток на маршруты старается минимизировать потери, которые бывают следующими:

• если \(i\)-ая маршрутка обслуживает \(j\)-ый маршрут, то компания теряет \(|a_i-b_j|\) у.е., так как чем меньше заполнено такси, тем больше не используются его возможности, а чем больше переполнено такси, тем чаще его приходится ремонтировать;
• от каждой простаивающей маршрутки, то есть такой, которой не назначен ни один маршрут, компания несет убыток \(p\) у.е.;
• компании приходится платить штраф \(q\) у.е. департаменту транспорта за каждый не обслуживаемый маршрут.

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

В Тридевятом царстве царь был любителем разных заморских традиций. Как прознает, что в другом царстве есть какой-то обычай, сразу думает, как бы его к тридевятым реалиям приспособить.

Вот неделю назад вернулось посольство из Тридесятого царства. И главный посол доложил царю: дескать, придумал Тридесятый царь следующую вещь. Чтобы как-то зарегулировать гуляния народные, повелел он указать определенные дни, и в эти дни устраивать широкие гуляния, а в остальные дни массовые сборища запретить. И с тех пор жизнь в Тридесятом царстве стала прекрасной: гулять так гулять, работать так работать, и все строго по цареву указу.

Понравилась мысль такая царю Тридевятого царства. Подумал он ввести и у себя такие порядки. Собрал царь советников своих, и говорит: подготовьте мне список дней, в которые гулять можно. Только не на год, а на \(N\) дней вперед — посмотрим, дескать, что получится; понравится — сделаем круглогодичным.

И вот вчера принесли советники царю список. Но вот незадача: каждый советник свой список приготовил, да еще и обоснование предложил, какой праздник в какой из этих дней надо отмечать. И у всех советников праздники важные, но у всех — разные! Царь думал-думал и решил: а возьмем их все — объединим предложения советников! Если какой-то день есть в списке хотя бы одного советника, то объявим этот день праздничным, и пускай народ гуляет! Глядишь, и не будет недовольных.

Только одна проблема осталась: некоторые дни оказались в списках сразу у нескольких советников. Но царь и тут нашел выход: перенесем некоторые праздники на более поздние дни, так, чтобы в каждый день получался только один праздник, и переносы были бы как можно короче.

Пусть, например, четыре советника сразу предложили сделать некоторый день (пускай день 5) праздничным. Тогда перенесем три из этих четырех праздников на дни 6, 7 и 8 — так, что праздничными будут дни с 5 по 8 включительно. А если оказывается, что, например, день 7 тоже предложен в качестве праздничного кем-нибудь из советников, то перенесем этот праздник еще дальше — на день 9.

Напишите программу, которая, зная предложения советников, определит, какие дни будут праздничными, а какие нет. Не забывайте, что праздники можно переносить только на более поздние дни; на более ранние переносить нельзя.

Сеть компьютерных салонов «ХТТП» представлена в городе Н. двумя магазинами. Руководство Н-ского отделения сети решило реорганизовать витрины, на которых представлены ноутбуки. В каждом из двух магазинов на витрине должны быть представлены \(N\) моделей ноутбуков, выставленные в ряд от касс вглубь помещения магазина. Маркетологи каждого из магазинов уже определили порядок, в котором на витрине должны быть расположены эти модели (эти порядки в двух магазинах, конечно же, могут быть разными).

На витрины надо выставлять специальные, выставочные, образцы ноутбуков, с соответствующим программным обеспечением, показывающим рекламу, и т.д. В распоряжении администрации компьютерных салонов есть две версии специализированного ПО: работающие под управлением операционных систем Windows и Linux. Соответственно, каждый из выставочных образцов ноутбуков должен иметь предустановленной ровно одну из этих систем.

Для снижения затрат было принято решение закупить по два идентичных экземпляра каждой модели ноутбуков (т.е. с одинаковыми предустановленными операционными системами), отправить по одному экземпляру в каждый из магазинов сети, и расставить их на витрине в соответствии с порядком, определенным маркетологами того магазина.

Но при этом возникла проблема. По требованиям Федеральной антимонопольной службы, компьютерные салоны не должны предоставлять преимущества ни одной из операционных систем. Начальство сети «ХТТП» знает, как проходит проверка на соответствие этой норме законодательства. Инспектор антимонопольной службы идет по магазину начиная от касс вдоль витрины с ноутбуками, считает отдельно количество встреченных ноутбуков с Windows и Linux, а также модуль разности этих чисел (т.е. на сколько ноутбуков с одной системой он встретил больше, чем ноутбуков с другой системой). В некоторый момент он останавливается и говорит: «Ага!». Это значит: слишком у вас большой дисбаланс между операционными системами, поэтому платите штраф. Размер штрафа пропорционален разнице (взятой по модулю) количества ноутбуков с разными системами, которые увидел инспектор.

Естественно, руководство сети не в состоянии предсказать, в какой из магазинов пойдет инспектор, а также сколько ноутбуков он просмотрит. Тем не менее, они хотят минимизировать штраф, который им будет выписан в худшем случае. Помогите им.

Например, пусть \(N=5\): в магазинах должны быть выставлены пять моделей ноутбуков. Будем нумеровать модели ноутбуков от 1 до 5. Пусть в первом магазине маркетологи определили, что оптимальный порядок ноутбуков следующий (от касс вглубь зала):

2 4 1 3 5,

а во втором магазине —

3 1 2 5 4.

Тогда, если закупить ноутбуки моделей 1, 3 и 4 с операционной системой Windows, а 2 и 5 — с Linux, то порядок операционных систем в магазинах будет следующий (от касс вглубь зала):

L W W W L,

W W L L W.

Тогда, если, например, инспектор придет в первый магазин и просмотрит первые четыре ноутбука, то он скажет: «Ага!», и выпишет штраф за то, что он увидел Windows-ноутбуков на два больше, чем Linux. Аналогичный результат будет, если он придет во второй магазин и просмотрит только первые два ноутбука.

А если закупить ноутбуки 2 и 3 с системой Linux, а 1, 4, 5 — с Windows, то порядок операционных систем будет следующий:

L W W L W,

L W L W W,

и в какой бы магазин не пришел инспектор, и сколько бы ноутбуков он не посмотрел, разница Windows- и Linux-ноутбуков не будет превосходить по модулю 1, и это и будет оптимальным вариантом для руководства сети. (Напомним, что инспектор всегда начинает осмотр магазина от касс и идет вглубь магазина вдоль ряда с ноутбуками).