Сережа очень любит математические задачи. Недавно на математическом кружке ему рассказали, что такое НОД и НОК.

НОД двух натуральных чисел \(a\) и \(b\) — это их наибольший общий делитель, то есть такое максимальное число \(x\), что \(a\) делится на \(x\) и \(b\) делится на \(x\). Например, НОД(24, 18) = 6. А НОК целых чисел \(a\) и \(b\) — это их наименьшее общее кратное, то есть такое минимальное число \(x\), что \(x\) делится на \(a\) и на \(b\). Например, НОК(24, 18) = 72.

Сережа сразу заметил, что может существовать несколько пар чисел с одинаковыми НОД и НОК. Теперь он заинтересовался вопросом: если заданы числа \(a\) и \(b\), насколько близко друг к другу могут быть два числа, у которых такие же НОД и НОК.

Помогите ему по заданным двум числам \(a\) и \(b\) найти такие числа \(x\) и \(y\), что \(НОД(a, \ b) \ = \ НОД(x, \ y), \ НОК(a, \ b) \ = \ НОК(x, \ y)\), а их разность \(y \ − \ x\) минимальна.

Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на все его сосуды с эликсиром мудрости.

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

Чтобы добиться этого, Мерлин решил действовать следующим образом. Он выбирает несколько сосудов и переливает весь эликсир из выбранных сосудов в оставшиеся. Он может распределить переливаемый эликсир между оставшимися сосудами произвольным образом. После того, как весь эликсир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся сосудам.

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

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

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

По окончании регистрации стало понятно, что для подведения итогов олимпиады использовать данную таблицу невозможно: участнику будет неудобно себя искать. Было решено привести таблицу к следующему виду:

• для всех участников сначала написана фамилия, затем имя, а затем — отчество;
• участники в таблице упорядочены лексикографически по фамилии.

Пользуясь этой информацией, помогите им привести таблицу к желаемому виду.

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

Петя начинает путь на дороге возле своего дома. При этом он может выбрать любое из двух направлений. Когда Петя подъезжает к перекрестку, он может повернуть на любую другую проходящую через него дорогу или продолжить ехать по текущей. Поскольку Петя не очень опытный водитель, каждый поворот, который он совершает, заставляет его волноваться. Причем волнение Пети равно величине угла, на который он поворачивает, в градусах. Например, при повороте на прямой угол волнение Пети равно 90.

Помогите Пете выяснить, чему равно минимальное суммарное волнение, которое он испытает, добравшись до дома Васи.

Учительница математики очень не любит Колю и всегда заставляет его отвечать у доски самые сложные задачи.

Вот и сегодня она написала на доске последовательность из \(n\) целых неотрицательных чисел чисел \(a_1, \ a_2, \dots, \ a_n\) и вызвала Колю к доске. За одно действие учительница разрешает Коле стереть любое число и на его место записать число на единицу больше. Учительница требует от Коли за минимальное число действий добиться того, чтобы где-нибудь в этой последовательности встречались подряд в возрастающем порядке числа от \(1\) до \(h\).

Помогите Коле понять, за какое минимальное число действий ему удастся добиться того, что для некоторого \(i\) будет выполнено \(a_i \ = \ 1, a_{i \ + \ 1} \ = \ 2, \dots, \ a_{i \ + \ h \ − \ 1} \ = \ h\), или выясните, что это невозможно и учительница опять безнаказанно издевается над бедным Колей.