Будущие программисты Андрей и Борис вчера впервые поехали кататься с родителями по новой кольцевой дороге. Каждый из них выехал на дорогу в определённом месте, сделал полный круг и вернулся домой. От скуки они оба считали фонарные столбы, расположенные посередине дороги между встречными полосами движения, так что все N фонарных столбов у каждого из мальчиков получили номера от 1 до N . Но само значение N они не запомнили. При этом два столба обоим мальчикам запомнились особенно: на одном из них висел яркий плакат ко Дню города, а на другом — флаг Москвы. Каждый из мальчиков записал себе в тетрадку номер каждого из этих двух столбов.

Сегодня обе семьи, Андрея и Бориса, пошли на выставку кошек, и там мальчики, обсудив свои поездки, задались вопросом: сколько же всего фонарных столбов на новой кольцевой дороге? Единственное, что они смогли выяснить, в одном ли направлении ехали они по дороге.

Так сложилось, что Андрей — ваш младший брат, поэтому именно вам предстоит ответить на вопрос мальчиков. У вас есть серьёзное подозрение, что может не получиться однозначно найти ответ, а мальчики боятся больших чисел, поэтому вы решили сказать им лишь минимальное из возможных значений числа N .

В этом примере N = 6 , A _p = 4 , A _f = 2 , B _p = 1 , B _f = 5 .

Команда туристического клуба «В гору пойдёт!» только что вернулась из очередного похода. Прямо сейчас участники экспедиции с жаром спорят о том, какой же горный хребет они покорили.

Достоверно известно, что на маршруте было N стоянок, причём все — на разной целочисленной высоте от 1 до N над уровнем моря. Альпинисты заблаговременно прибыли на место первой стоянки, а потом шли по маршруту в течении N - 1 дня: в первый день они шли от 1 -й стоянки до 2 -й, во второй — от 2 -й до 3 -й и так далее, пока в последний день не совершили переход от стоянки под номером N - 1 до стоянки под номером N , завершив этим свой маршрут.

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

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

Что может быть проще простого числа? Казалось бы, объяснить, что такое простое число, можно даже человеку, совершенно далёкому от математики: целое число называется простым, если оно не меньше двух и не делится ни на какое целое положительное число, кроме единицы и самого себя. Это определение будет понятно даже третьекласснику, только-только познакомившемуся с делением. Что может быть проще? Но, как часто случается в математике, за кажущейся простотой определения скрывается очень глубокая теория с множеством нетривиальных фактов, многие из которых остаются недоказанными и по сей день.

Прочитав популярную книгу Д. Дербишира «Простая одержимость» , Леопольд узнал следующий занятный факт. Оказывается, существует Теорема о распределении простых чисел , гласящая, что количество простых чисел, не превышающих N , можно очень точно оценить как . Например, начиная с N > 5000 , эта формула даёт ошибку, не более чем в 15% от реального значения. Более того, с ростом N относительная погрешность такой оценки падает, стремясь к нулю.

Леопольд крайне заинтересовался простыми числами и связанной с ними теорией. Он решил выдвинуть какую-нибудь не менее важную и серьёзную гипотезу, а потом доказать её, и назвать полученный факт теоремой Леопольда. Для этого ему нужна помощь в отыскании закономерностей, описывающих простые числа. Он просит вас написать для него программу, которая ищет для него Q отрезков, i -й из которых состоит из L _i последовательных натуральных чисел и содержит определённое количество K _i простых чисел. Для простоты анализа он просит вас ограничиться в поисках первыми десятью миллионами чисел. Помогите ему, и, возможно, вам с ним удастся оставить след в истории!

Склад завода по изготовлению матрёшек переполнен! Нужно как-то освобождать место, поэтому директор завода принял волевое решение продать абсолютно всё, что там лежит. Больше всего места на складе занимают заготовки для матрёшек — нераскрашенные статуэтки целых положительных размеров, которые можно вставлять друг в друга. Увы, в таком неприглядном виде покупать их никто не хочет.

К счастью, завод сотрудничает с союзом художников по матрёшкам. В частности, был заключён договор, позволяющий заводу заказывать роспись матрёшек. В договоре указано, что матрёшка — это упорядоченный набор из M статуэток ( 1 ≤ M ) размеров a ₁ , a ₂ , ..., a _M , где a ₁ + 1 = a ₂ , a ₂ + 1 = a ₃ , ..., a _{M - 1} + 1 = a _M . Там же прописано, что стоимость раскрашивания одной матрёшки равна одному тугрику, при этом количество статуэток, входящих в матрёшку, значения не имеет.

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