Задача A. Дифтонги ≡

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

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

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

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

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

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

3
e
ee
eee

ee

3
aabbee
cyydyyy
xiixiixiii

aabbee
xiixiixiii

Задача B. Ставка ≡

Условие

Андрей очень любит играть в Космический покер.

В космическом покере вместо карт используются фишки трех цветов. Казино определяет два числа A и C — коэффициенты для вычисления ставок. Затем игрок по определенным правилам ставит фишки трех цветов: красного, зеленого и синего. Выигрыш игрока вычисляется по формуле: A ⋅ (r² + g² + b²) + C ⋅ min { r, g, b}, где r, g, b — количество фишек красного, зеленого и синего соответственно.

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

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

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

В первой строке задано одно целое число t (1 ≤ t ≤ 10 000) — количество игровых ситуаций.

Каждая игровая ситуация описывается двумя строками. В первой строке задано два целых числа A и C (1 ≤ A, C ≤ 10) — коэффициенты для вычисления выигрыша. Во второй строке задано три целых числа r, g и b (0 ≤ r, g, b ≤ 15) — количество фишек красного, зеленого и синего цвета, соответственно.

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

Выведите t строк. В k-ой строке выведите RED, если оптимально добавить красную фишку, GREEN, если оптимально добавить зеленую фишку или BLUE, если оптимально добавить синюю фишку. Если есть несколько оптимальных вариантов, можно вывести любой из них

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

3
2 10
2 4 4
1 2
3 4 5
4 2
7 7 7

RED
BLUE
GREEN

Задача C. Последний урок ≡

Условие

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

Например, Вася, получивший в течение четверти оценки 3, 4, 2, 3, 3, 5, будет иметь среднюю оценку 20 / 6 = 3.3333... и получит итоговую оценку 3.

Средние оценки 1.5, 2.5, 3.5 и 4.5 округляются до 2, 3, 4 и 5 соответственно.

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

Например, если Вася на последнем уроке сумеет получить пятёрку, то его средняя оценка станет равна 25 / 7 = 3.571... и итоговая оценка повысится до 4 баллов.

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

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

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

Ограничения

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

1
6 2 2 2 2 2 2

0

2
6 3 4 2 3 3 5
4 4 5 4 5

1

Задача D. Восстановление сетки ≡

Условие

Турнир по олимпийской системе, состоящий из N раундов, проводятся между 2^N участниками по следующей схеме: сначала составляется последовательность из расставленных в произвольном порядке игроков. В первом раунде первый в последовательности участник соревнуется со вторым, третий с четвёртым, и т.д. Проигравшие выбывают из турнира, и на втором раунде победитель первой пары играет с победителем второй, победитель третьей с победителем четвёртой, и т.д. Наконец, после N-го раунда остаётся ровно один участник, который становится победителем турнира.

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

Назовём упорядоченной такую первоначальную последовательность участников, что в каждом матче сетки победителем оказывается первый участник. Например, первоначальная последовательность в приведённой справа сетке не соответствует этому условию — чтобы это исправить, нужно расположить участников в порядке: Life, MarineKing, TaeJa, Leenock, Mvp, Symbol, Rain, Hero.

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

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

N ≤ 10;

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

Входной файла содержит целое число N, за которым следуют 2^N − 1 пар чисел W_i L_i, означающих, что участник с номером W_i победил участника с номером L_i. Участники пронумерованы от 1 до 2^N.

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

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

Ограничения

1 ≤ N ≤ 20

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

3
1 2  3 1  7 3
7 6  6 5  7 8  3 4

7 8 6 5 3 4 1 2 

Задача E. Бутылка на всех ≡

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Problem F. Lin-log sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Problem G. Square sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Задача H. Два компьютера ≡

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров T_i секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

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

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

Ограничения

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

5 7 10 3 5 6

16

Задача I. Автомобильные номера ≡

Условие

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

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

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

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

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

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

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

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

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

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача J. Длинное взятие ≡

Условие

На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек. Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.) Вертикали обозначены буквами a, b, c, … слева направо. Клетка, таким образом, задается комбинацией из буквы и числа, например d12. Ход шашки задается перечислением всех клеток, которые она посетила за этот ход, включая начальную и конечную. Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.

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

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

Ограничения

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

5
.....
.O.O.
....X
.O.O.
X....  

e3-c1-a3-c5-e3  

4
X...
....
....
...O  

Impossible

Задача K. Сумма с перестановкой ≡

Условие

Заданы три числа: a, b, c. Необходимо выяснить, существуют ли такие числа x и y, что:

1. x получается перестановкой цифр числа a;
2. y получается перестановкой цифр числа b;
3. x и y не содержат лидирующих нулей;
4. x + y = c.

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

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

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

Если искомые числа существуют, вывести в первую строку выходного файла слово YES, а во вторую — числа x y, разделённые пробелом. В противном случае вывести слово NO.

Ограничения

1 < a, b, c < 10⁹

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

12 31 25

YES
12 13

12 31 26

NO

Задача L. Слово из кубиков ≡

Условие

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

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

Ограничения

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

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4