Задача A. Сколько студентов? ≡

Условие

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

Помогите Васе узнать минимально возможное общее число студентов в его университете.

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

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

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

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

Ограничения

1 ≤ P, S ≤ 100

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

10 20

50

2 19

5000

Задача B. Открытка программиста ≡

Условие

На день святого Валентина Дима решил сделать подарить своей девушке Лене открытку с сердечками. Лена учится в ДВФУ на программиста, поэтому Диме хотелось сделать программистскую открытку.

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

Изображение открытки представляет собой прямоугольную таблицу, состоящую из символов "." (ASCII 46), "/" (ASCII 47), "V" (ASCII 86), "\" (ASCII 92), "^" (ASCII 94). На открытке изображено n сердец. Каждое сердце задаётся координатами центра x y и размером d. Координата x отсчитывается по горизонтали слева направо, а координата y — по вертикали сверху вниз.

Изображение сердца состоит из шести наклонных линий, состоящих из символов "/" и "\". Две линии, образующие нижний контур сердца, имеют длину по d символов, две линии, образующие внешнюю часть верхнего контура, имеют длину по ⌊(d + 1) / 2⌋ символов, а две линии, образующие внутреннюю часть верхнего контура, имеют длину по ⌊(d − 1) / 2⌋ символов.

Центр и нижняя точка сердца обозначены символами "V". Если d чётно, то две верхние точки сердца обозначены символами "^".

Изображение открытки должно иметь минимально возможный размер, охватывающий изображения всех заданных сердец. Все позиции, не занятые изображениями сердец, должны содержать символ ".".

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

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

Входной файла содержит натуральное число n  — количество сердец, за которым следует n троек натуральных чисел x_i y_i d_i.

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

Выходной файл должен содержать изображение открытки.

Ограничения

1 ≤ n ≤ 10²

1 ≤ x_i, y_i, d_i ≤ 50

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

3
4 4 3
7 7 6
17 11 1

./\./\............
/..^..\..^........
\./.\././.\.......
./...\./...\......
/.\./.V.....\.....
\..V......../.....
.\........./......
..\......./.......
...\...../...../V\
....\.../......\./
.....\./........V.
......V...........

Задача C. Профессор и песок ≡

Условие

Профессор одной из кафедр ДВФУ разработал инновационный метод для того, чтобы определять момента завершения лекции. У профессора есть двое песочных часов. В первых песок полностью пересыпается за a минут, во вторых — за b минут. В начале лекции весь песок в часах находится внизу и профессор переворачивает первые, вторые или сразу и те и другие часы. Как только песок в каких-нибудь часах полностью пересыпался, профессор может опять перевернуть первые, вторые или сразу и те и другие часы.

К концу лекции весь песок в часах вновь должен оказаться внизу. Лекция длится T минут.

По заданным a, b и T определите искомую последовательность переворотов.

Считается, что профессор переворачивает часы мгновенно.

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

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

Первая строка входного файла содержит количество тестов n. Далее следует n строк с целыми числами T, a, b.

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

Выходной файл должен содержать n блоков с ответами на тесты.

Первая строка каждого блока должна содержать количество действий, k. Далее должно следовать k строк с парами целых чисел t_i m_i в каждой, где t_i — время выполнения действия, m_i — одно из чисел 1, 2 или 3, обозначающее, что необходимо перевернуть первые, вторые или и те и другие часы соответственно. Для первого действия должно быть t_i = 0, для остальных t_i должно быть таким, что в этот момент песок хотя бы в одних часах только что полностью пересыпался вниз. Все t_i должны быть различны и расположены по возрастанию.

Для каждого теста выведите такой ответ, в котором количество действий не превосходит 500. Гарантируется, что в каждом тесте такой ответ существует.

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

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

2
11 4 7
7 4 7

2
0 1
4 2
1
0 3

Задача D. Выборы заведующего кафедрой ≡

Условие

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

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

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

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

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

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

Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Задача E. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

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

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO