Задача 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 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

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

Условие

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

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

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

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

Входной файл состоит из четырёх строк по четыре числа в каждой. 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 

Задача D. Отгадай слово ≡

Условие

Хрюша и Степашка играют в игру "Отгадай слово". Правила игры просты. Хрюша придумывает слово, состоящее из букв латинского алфавита, придумывает загадку и загадывает её Степашке. Задача Степашки — отгадать слово.

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

Ход Степашки заключается в том, что Степашка называет любую букву латинского алфавита.

1. Если такая буква есть в слове и все такие буквы закрыты, то все они открываются.
2. Если такая буква есть в слове и все такие буквы открыты, то все они закрываются.
3. Если такой буквы нет в слове, то никакие буквы не открываются и не закрываются.

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

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

Входной файл содержит ровно две строки.

Первая строка входного файла состоит из маленьких букв латинского алфавита и представляет собой слово, придуманное Хрюшей.

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

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

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

Если i-я буква открыта, то i-й символ выходной строки должен совпадать с i-м символом первой строки входного файла.

Если же буква закрыта, то соответствующий символ выходной строки должен быть '.' (точка).

Ограничения

Количество букв в слове от 1 до 15.

Количество ходов Степашки от 1 до 20.

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

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

frog
or

.ro.

frog
oro

.r..

frog
fffrrroooog

fr.g

frog
golf

f.og

frog
gorf

frog

Задача E. Замена скобок: выполнение алгоритма ≡

Условие

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

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

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

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

В первой строке входного файла содержится исходная последовательность.

Во второй строке содержится число N.

В каждой из последующих N строк содержится по два числа l_i r_i, задающих позиции первого и последнего символа подстроки, в которой на i-ом шаге меняются скобки.

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

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

Ограничения

1 ≤ N, L ≤ 10⁵

1 ≤ l_i ≤ r_i ≤ L

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

(((((
1
1 5 

)))))

((())(()
3
1 8
2 6
4 7

)(((()((

Задача F. В лесу родилась ёлочка ≡

Условие

Скоро Новый год, и Марфа Геннадьевна послала своих сыновей срубить несколько ёлок на продажу.

Хорошие, толстые, густые ёлки стоят на рынке 5000 руб., а ёлки похуже, тонкие, менее густые стоят 2000 руб.

На всё про всё у ребят есть ровно T минут. Хорошие ёлки растут подальше, и рубить их дольше. Ёлки похуже растут поближе, и рубить их быстрее. На то, чтобы дойти до i-й ёлки, срубить её и вернуться домой, нужно затратить t_i минут.

У ребят есть электронная карта участка леса, на которой отмечены ёлки. Сейчас им ой как нужна программа, вычисляющая максимально возможную выручку.

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

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

Далее следует число M — количество ёлок похуже. За ним следуют M целых чисел t_i.

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

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

Ограничения

1 ≤ N, M ≤ 1000

1 ≤ T ≤ 10000

1 ≤ t_i ≤ 10000

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

250
1
240
2
120 100

5000

250
1
240
3
60 80 70

6000

Задача G. Минимальный лабиринт ≡

Условие

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

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

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

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

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

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

Далее идут N строк по M символов, описывающие лабиринт:

• # (ASCII 35) — обозначает блок
• . (ASCII 46) — обозначает пустое место

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

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

Ограничения

1 ≤ N, M ≤ 100

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

3 7
......#
.#..#.#
....#..

......#
.#..#.#
....#..

3 8
##.#..##
##.#.###
...#.##.

.#.#..#.
##.#.#.#
...#.##.

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

Условие

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

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

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

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

Входной файл содержит целое число 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

Задача I. Мы делили... ≡

Условие

На день рождения пришли N гостей. Праздничный торт разделили между всеми гостями поровну. После этого неожиданно явились ещё K гостей.

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

Ответ вывести в виде несократимой обыкновенной дроби A / B.

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

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

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

Выходной файл должен содержать два целых числа — A B, обозначающие числитель и знаменатель соответственно.

Ограничения

1 ≤ N, K ≤ 10⁴

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

1 3

3 4

3 9

1 4

Задача J. Судьба математика - 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

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

Условие

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

Преподаватель решил зачесть работу только тому единственному студенту, который выполнил её самостоятельно. Чтобы определить этого студента, он пронумеровал всех студентов, писавших контрольную, числами от 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

Задача L. Во саду ли, в огороде ≡

Условие

Во саду ли, в огороде бегала собачка.

Огород, по которому бегает собачка, представляет собой квадрат размером N × N метров.

Разумеется, это не первая среди собак, бегавших по этому огороду, и каждая из них хотя бы раз закапывала в нем косточки. Поэтому в разных местах огорода присутствует вкусный запах разной интенсивности. Огород разделён на N² квадратиков, в квадратике с координатами (i, j) интенсивность запаха равняется a_i,j.

Квадратик с координатами (1, 1) расположен в левом верхнем углу огорода. Первая координата откладывается по горизонтали, вторая — по вертикали.

Вначале собака находится в квадратике с координатами (i₀, j₀). На каждом шаге собака перемещается в соседний (слева, сверху, справа или снизу) квадратик, в котором запах самый сильный и сильнее, чем в квадратике, в котором находится собака. Если такого квадратика не оказалось, то собака останавливается.

Напишите программу, позволяющую найти траекторию собаки.

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

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

Далее следуют N² целых чисел a_i,j.

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

Выходной файл должен содержать пары целых чисел — траекторию собаки.

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

Ограничения

2 ≤ N ≤ 100

0 ≤ a_i,j ≤ 100

1 ≤ i₀, j₀ ≤ N

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

3 2 2
5 0 3
2 1 1
2 3 4

2 2
2 3
3 3