Задача A. Расписные салфеточки ≡

Условие

У Марфы Геннадьевны имеется кусок очень красивой атласной ткани с выбитыми цветами. Длина куска составляет L см. Марфа Геннадьевна — большая рукодельница и любит делать всякие поделки. Она надумала сделать из ткани несколько салфеточек и подарить их на праздник своим подружкам.

Марфа Геннадьевна хочет разрезать этот кусок ткани ровно на N частей. При этом длина каждой части l должна быть целым числом и должно выполняться неравенство a ≤ l ≤ b (чтобы салфетки были не слишком маленькими и не слишком большими).

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

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

Входной файл содержит целые числа N L a b.

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

Выходной файл должен содержать N целых чисел l_i, если задача имеет решение, и единственное число 0, если задача не имеет решения.

Ограничения

1 ≤ N ≤ 100

1 ≤ L ≤ 1000

1 ≤ a ≤ b ≤ 1000

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

3 5 1 2

1 2 2

3 7 1 2

0

Задача B. Арифметическая прогрессия ≡

Условие

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

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

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

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

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

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

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

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 10⁶

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

7
1 3 4 2 7 8 10

4
1 3 5 7

Задача C. Кто не списал? ≡

Условие

После контрольной работы по физике преподаватель заподозрил неладное. Все сданные студентами работы были одинаковы! Поразмыслив над этим феноменом, преподаватель определил его причину: один из студентов честно выполнил задание, а остальные у него списали.

Преподаватель решил зачесть работу только тому единственному студенту, который выполнил её самостоятельно. Чтобы определить этого студента, он пронумеровал всех студентов, писавших контрольную, числами от 1 до N, и задал каждому вопрос: "Чьё это решение?".

Каждый студент назвал номер студента, который является настоящим автором работы.

Незадолго до этого куратор группы студентов, писавших контрольную, сообщил преподавателю физики, что ровно M среди N студентов группы всегда говорят правду, а остальные всегда врут.

Напишите программу, которая по этим данным определит самостоятельного студента.

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

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

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

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

Ограничения

1 ≤ N ≤ 100000 0 ≤ M ≤ 100000

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

2 1
1 1

-1

2 0
2 2

1

Задача D. В какую группу? ≡

Условие

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

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

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

Руководитель второй кафедры принимает студента с максимальным баллом по информатике, а если таких несколько — студента с максимальным баллом по математике среди них.

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁵; 1 ≤ a_i, b_i ≤ 10⁶

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

1
1 1

1

3 
1 1 2 1 2 2

3 2 1

Задача E. Комбинированная эстафета ≡

Условие

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

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

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

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

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

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

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

Ограничения

0 ≤ t_ij ≤ 120

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

49.61 55.47 61.97 53.33
53    59.5  66.5  57.5
56    63    70    61
59.5  67.5  75    65

3 2 4 1 

Задача F. Марфа Геннадьевна в столовой ≡

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит c_i рублей. Для каждого блюда известен также коэффициент сытости блюда — a_i.

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

Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более одной порции блюда (любое целое неотрицательное число порций).

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

Входной файл содержит целые числа N A.

Далее следуют N пар целых чисел c_i a_i.

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ c_i ≤ 500

1 ≤ a_i ≤ 100

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

3 10
2 1
5 4
6 6

11

4 32
1 8
2 4
3 2
4 1

4

Задача G. Спортивная ходьба ≡

Условие

В любых спортивных соревнованиях важно честное соблюдение правил. Особенно тяжёлыми в этом плане являются соревнования по спортивной ходьбе. Важно, чтобы участники не переходили на бег. Организаторы одного из соревнований по спортивной ходьбе решили разместить n судей вдоль трассы, на которой будут проходить состязания. Судьи будут следить за тем, чтобы все участники соблюдали правила.

Трасса для спортивной ходьбы представлена в виде ломаной на плоскости с вершинами в точках (x₁, y₁), (x₂, y₂), … (x_k, y_k). Ломаная может иметь самокасания и самопересечения. Судья с номером i неподвижно стоит в точке (cx_i, cy_i) и обозревает вокруг себя круг с радиусом r_i.

Таким образом, каждая точка трассы обозревается некоторым (возможно, нулевым) количеством судей. Напишите программу, которая по заданной трассе и положению судей определит длину участков, обозреваемых ровно m судьями для целых m от 0 до n.

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

Входной файл содержит целые числа n k. Далее содержится n троек целых чисел cx_i cy_i r_i, задающих положение судей. Далее содержится k пар целых чисел x_j y_j, задающих ломаную.

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

Выходной файл должен содержать n + 1 число — ответы для 0, 1, …, n судей с точностью не менее 10⁻⁶.

Ограничения

1 ≤ n ≤ 1000;

2 ≤ k ≤ 1000;

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

2 4
3 0 2
6 0 2
0 0
4 0
6 0
10 0

3.000000
6.000000
1.000000

Задача H. Судьба математика - 3 ≡

Условие

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

Однако, он сумел вспомнить, что в записной книжке:

1. все имена состоят из строчных латинских букв;
2. все имена отсортированы в лексикографическом (алфавитном) порядке;
3. где-то перед именем девушки встречалось имя S₁;
4. где-то после имени девушки встречалось имя S₂;
5. имя девушки имело длину от 1 до L букв.

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

Так, в приведённом ниже примере подходящими являются имена (в лексикографическом порядке): aa, ab, ... az, b, ba.

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

Первая строка входного файла содержит целое число L. Следующие две строки входного файла содержат имена S₁ и S₂, длинной не менее одного и не более L символов каждое. Имя S₁ лексикографически строго меньше, чем S₂.

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

Выходной файл должен содержать единственное число — количество строк длиной от 1 до L, находящихся лексикографически строго между S₁ и S₂.

Ограничения

1 ≤ L ≤ 50

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

2
a
bb

28