Задача A. Обезьянки ≡

Условие

На днях в Елизовский зоопарк прибыли новые жильцы – N обезьянок. Администрации зоопарка предстоит решить, как лучше всего распределить N обезьянок по имеющимся в зоопарке K свободным вольерам таким образом, чтобы ни один вольер не остался пустым. Главным критерием при размещении является комфортное обитание обезьян, поэтому администрацию в первую очередь интересует, сколько обезьянок окажется в самом заполненном вольере (то есть в вольере с максимальным числом обезьянок).

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

Формат входного файла

Формат выходного файла

Примеры тестов

7 4

2 4

12 3

4 10

Задача B. Яблоки поровну ≡

Условие

В школьной столовой на завтрак раздавали яблоки. Каждому школьнику должно было достаться по одному яблоку, но трём из них удалось незаметно набрать в карманы a₁, a₂ и a₃ яблок соответственно.

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

Например, если у первого школьника 2 яблока, у второго — 3, а у третьего — 4, то третий школьник может передать первому одно яблоко, и тогда у каждого из них будет по 3 яблока.

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

Формат входного файла

Входной файл содержит целые числа a₁ a₂ a₃.

Формат выходного файла

Выходной файл должен содержать целые положительные числа x y z — номер школьника, который отдаёт яблоки, номер школьника, которому отдаёт яблоки школьник x, и количество яблок.

Если у школьников уже одинаковое количество яблок, выведите единственное число 0.

Если решения не существует, выведите единственное число  − 1.

Ограничения

1 ≤ a_i ≤ 1000; 1 ≤ x, y ≤ 3

Примеры тестов

3 3 3

0

1 3 5

3 1 2

1 3 6

-1

Задача C. Двухцветная полоса ≡

Условие

Дана полоса, состоящая из N разноцветных клеток. Требуется написать программу, которая найдёт самый длинный отрезок этой полосы, состоящий из клеток не более двух разных цветов.

Формат входного файла

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

Формат выходного файла

Выходной файл должен содержать два числа P L, где P — номер первого символа искомого отрезка, L — его длина. Нумерация клеток начинается с 1.

Если существует несколько оптимальных решений, выведите решение с минимальным значением P.

Ограничения

1 ≤ N ≤ 10⁶

Примеры тестов

xxxxx

1 5

abbaaccca

4 6

Задача D. Марфа Геннадьевна в кустах ≡

Условие

Марфа Геннадьевна считает, что её соседка по даче, Элеонора Агафьевна, слишком любопытна и постоянно подглядывает за Марфой Геннадьевной из окна. Граница участков Марфы Геннадьевны и Элеоноры Агафьевны представляет собой отрезок длиной L см.

Марфа Геннадьевна решила загородить соседке обзор, засадив границу кустами. У Марфы Геннадьевны имеются семена N видов кустов. Известно, что кусты i-го вида вырастают до ширины в a_i см. При этом для нормального развития кустам i-го вида необходимо, чтобы расстояние между краями соседних кустов, а также от края куста до края границы участков было не менее b_i см.

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

Рекомендуется рассмотреть следующие частичные решения

• N = 1;
• N = 2;

Формат входного файла

Входной файл содержит целые числа N L, за которыми следует N пар целых чисел a_i b_i — ширина куста и минимальное расстояние для i-го вида.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 10³

2 ≤ L ≤ 10⁴

1 ≤ a_i, b_i ≤ 10⁴.

Примеры тестов

2 5
3 1
2 1

2

2 7
3 2
2 3

4

1 10
5 3

10

Задача E. Султан и мудрецы ≡

Условие

Однажды султан решил проверить знание математики у своих мудрецов.

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

Мудрецы начал выступать по очереди, i-й мудрец называл число a_i. И вот очередь дошла до N − 1-го мудреца — Васи.

От числа, которое назовет Вася, зависит судьба всех мудрецов. Помогите мудрецу Васе найти такое ещё не названное число a_N − 1, чтобы последний мудрец имел возможность назвать число a_N, отличающееся от всех предыдущих чисел и дополняющее их сумму до D.

Рекомендуется рассмотреть следующие частичные решения

• N = 3;
• a_i ≤ 1000;

Формат входного файла

Входной файл содержит натуральные числа D N, за которыми следует N − 2 натуральных числа a_i — числа, названные мудрецами до Васи.

Формат выходного файла

Выходной файл должен содержать подходящее для Васи число, либо  − 1, если такого числа не существует.

Если решений несколько, выведите любое из них.

Ограничения

3 ≤ N ≤ 10⁵

1 ≤ D, a_i ≤ 10⁹, a_i ≠ a_j∀ i ≠ j

Примеры тестов

18 4
2 6

1

26 5
2 5 9

4

13 4
2 5

-1

Задача F. Газон Ивана ≡

Условие

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x₁, y₁) и (x₂, y₂). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x₃, y₃) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x₃, y₃) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

Формат входного файла

В первой строке входного файла содержатся четыре целых числа x₁ y₁ x₂ y₂. Во второй строке входного файла содержатся три целых числа x₃ y₃ r.

Формат выходного файла

Ограничения

 − 10⁵ ≤ x₁, y₁, x₂, y₂, x₃, y₃ ≤ 10⁵

1 ≤ r ≤ 10⁵

Примеры тестов

0 0 5 4
4 0 3

14

Задача G. Треугольник Максима ≡

Условие

С детства Максим был неплохим музыкантом и мастером на все руки. Недавно он самостоятельно сделал несложный перкуссионный музыкальный инструмент — треугольник. Ему нужно узнать, какова частота звука, издаваемого его инструментом.

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

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

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

Система оценивания

Решения, правильно работающие только для целых чисел f_i, имеющих одинаковую четность, будут оцениваться из 40 баллов.

Формат входного файла

Первая строка входного файла содержит целое число n — количество нот, которые воспроизводил Максим с помощью тюнера. Последующие n строк содержат записи Максима, причем каждая строка содержит две компоненты: вещественное число f_i — частоту, выставленную на тюнере, в герцах, и слово closer или слово further для каждой частоты, кроме первой.

Слово closer означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: |f_i − f_треуг.| < |f_i − 1 − f_треуг.|.

Слово further означает, что частота данной ноты дальше, чем предыдущая.

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

Гарантируется, что результаты, полученные Максимом, непротиворечивы.

Формат выходного файла

В выходной файл необходимо вывести через пробел два вещественных числа с точностью не менее 10^− 8 — наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом.

Ограничения

2 ≤ n ≤ 1000, 30 ≤ f_i ≤ 4000

Примеры тестов

3
440
220 closer
300 further

30.0 260.0

4
554
880 further
440 closer
622 closer
	

531.0 660.0

Задача H. НОД и числа Фибоначчи (исправленная) ≡

Условие

k-тым числом Фибоначчи называется k-тый член последовательности F_k = F_k − 1 + F_k − 2 , F₀ = 0 , F₁ = 1

Формат входного файла

Формат выходного файла

В выходном файле должно содержаться единственное число — наибольший общий делитель F_n и F_k.

Ограничения

Примеры тестов

1 2

1

6 9

2

Задача I. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

Формат входного файла

Входной файл содержит три целых числа: W, H, N

Формат выходного файла

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

Примеры тестов

2 3 10

9

Задача J. Конфеты и самоконтроль ≡

Условие

Сегодня Петя и Вася купили себе K конфет. Петя предложил просто разделить их поровну и съесть, на что Вася ответил, что так не интересно и вместо этого предложил сыграть в игру.

Каждый по очереди берет конфеты из мешка. Первым ходит Петя, первый раз он всегда берет одну конфету, а каждый следующий раз - на одну больше, чем в предыдущий. Вася же каждый раз берет столько конфет, сколько Петя всего в сумме взял до этого. То есть во время первого хода Петя возьмет 1 конфету, затем во время второго хода Вася возьмет 1 конфету, потом Петя возьмет 2 конфеты, Вася возьмет 1 + 2 = 3 конфеты и т. д.

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

Формат входного файла

Первая строка входного файла содержит целые числа K и S — количество конфет и количество ходов соответственно.

Формат выходного файла

Выходной файл должен содержать единственное целое число M — такое максимальное количество конфет, чтобы игра продлилась хотя бы S ходов.

Ограничения

1 ≤ S ≤ K ≤ 10⁹, M ≤ K

Примеры тестов

6 4

2

14 6

4