Задача A. Космос и математика ≡

Условие

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

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

Ученый-археолог обнаружил значения энергии кристаллов А, Б и С, но в пророчестве утеряна информация об применении гармонизации и синтеза, пророчество выглядело так: A?Б?С. Помогите ученому выбрать наилучшие преобразования, чтобы получить максимальное количество квантов энергии и открыть портал в измерение Вечности.

Формат входных данных

Входные данные содержат 3 строки, в каждой из которых одно целое не отрицательное число, не превосходящее 100.Первая строка содержит А.Вторая строка содержит Б.Третья строка содержит С.

Формат выходных данных

Требуется вывести целое число — максимальное количество квантов энергии.

Примечание

Для перового примера ответом будет 350, так как оптимально будет расставить преобразования так: 5 * 7 * 10 = 350.

Для второго примера ответом будет 5, можно либо сделать так: 1 + 2 * 2, либо 1 + 2 + 2.

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

5
7
10

350

1
2
2

5

Задача B. Что надеть на прогулку? ≡

Условие

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

У Пети в шкафу кроме повседневной одежды есть:

• Куртка (jacket);
• Перчатки (gloves);
• Зонтик (umbrella);
• Шарф (scarf);
• Свитер (switer).

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

Что требуется Пете для комфортной прогулки

• Если температура (T ≤ 0), необходимо надеть куртку, дабы не замерзнуть;
• Если температура (T ≤  − 5), необходимо утеплиться и к куртке добавить шапку;
• Если температура (T ≤  − 10), необходимо ещё надеть шарф и перчатки;
• Если идёт дождь (R = 1), необходимо взять зонтик и надеть куртку;
• Но если дождь (R = 1) тёплый (T ≥ 15) то куртку надевать не нужно;
• Eсли дует ветер (W = 1), то брать зонтик нельзя, его ведь сдует;
• Если дует тёплый (T ≥ 15) ветер (W = 1) и идёт дождь (R = 1), то нужно надеть перчатки, чтобы хоть что-то не намокло;
• Если идёт снег (R = 1), то необходимо надеть шапку и перчатки;
• Если снег не идёт (R = 1) и температура сильно опустилась T ≤  − 15, то необходимо надеть свитер.

Формат входных данных

Входные данные содержат три целых числа, разделенные пробелами:

• Температура (T): Целое число, выраженное в градусах Цельсия. Может быть как положительным, так и отрицательным, но его абсолютное значение не превосходит 100;
• Осадки (R): Целое число (0 или 1). 0 означает отсутствие осадков, 1 означает наличие осадков (дождь при T > 0, снег при T ≤ 0);
• Ветер (W): Целое число (0 или 1). 0 означает отсутствие ветра, 1 означает наличие ветра.

Формат выходных данных

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

Возможные вещи: jacket, umbrella, hat, gloves, scarf, switer.

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

0 1 0

jacket hat gloves

1 1 1

jacket

Задача C. Карта вселенной ≡

Условие

Астроном Кирилл изучает космос с помощью гигантского телескопа. Кирилл собрал кучу данных и скомпилировал их в одно гигантское изображение (карту вселенной) размером N*M, где N — размер карты по вертикали, а M — размер карты по горизонтали. Изображение включает пустое пространство "." и галактики "#". Например:

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

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

По полученной карте найдите длину кратчайшего пути между каждой парой галактик с учётом расширения вселенной. Какова сумма этих длин?

Формат входных данных

В первой строке вводятся целые числа N и M — размеры карты, составленной Кириллом (2 ≤ N, M ≤ 25). Ниже идут M строк, состоящих из N символов "." или "#" — исходная карта вселенной.

2 ≤ число галактик ≤ 50

Формат выходных данных

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

Примечание

В приведённом выше примере один столбец и две строки не содержат галактик:

Эти строки и столбцы должны быть втрое больше. Соответственно исправленная карта выглядит следующим образом:

Получив корректную карту, можно найти кратчайший путь между каждой парой галактик. В примере выше 4 галактики образуют 6 пар. Для большей наглядности пронумеруем галактики. Например, вот один из кратчайших путей "+" между галактикой 1 и 4:

Этот путь имеет длину 9, поскольку требуется минимум 9 шагов, чтобы добраться от галактики 1 до галактики 4 (восемь отмеченных мест "+" плюс шаг в саму галактику 4). Вот ещё несколько кратчайших путей:

--- Между галактикой 1 и галактикой 2: 6

--- Между галактикой 4 и галактикой 3: 2

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

5 5
.....
#...#
.....
...#.
..#..

38

Задача D. Двадцать одно ≡

Условие

Денис и Тимофей играют в <<21 очко>>. В их версии игры два игрока по очереди берут карты из колоды, получая очки. Побеждает тот, кто по итогам игры будет ближе к 21 очку, чем противник. Если игроки оказались на одинаковом отдалении от 21 очка, то происходит ничья. Если игрок больше не хочет добирать карты, он пасует. Если один из игроков спасовал, второй может продолжать добирать столько карт, сколько захочет.

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

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

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

Формат входных данных

В первой строке вводится целое число N — размер колоды (2 ≤ N ≤ 10^4).

Вторая строка содержит N целых чисел, стоимостью от 1 до 21 — порядок карт в колоде, начиная с верха колоды.

Формат выходных данных

Выведите <<DENIS>>, если в игре победит Денис. Если победит Тимофей, выведите <<TIMOFEY>>. В случае ничьи выведите <<DRAW>>.

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

12
12 11 10 9 8 7 6 5 4 3 2 1

DRAW

16
10 2 4 4 5 21 7 3 3 3 1 14 9 2 1 8

DENIS

13
12 11 10 10 3 3 3 1 14 9 2 1 4

TIMOFEY

Задача E. Волшебные сокровища ≡

Условие

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

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

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

Формат входных данных

В первой строке дано число N (1 ≤ N ≤ 10⁵) — количество сундуков.

Во второй строке даны N чисел a_i (1 ≤ a_i ≤ 10⁹) — ценность i-го сокровища в сундуках.

Во третьей строке даны N чисел b_i (1 ≤ b_i ≤ 10⁹) — ценность i-го альтернативного сокровища.

Формат выходных данных

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

Решения, работающие при N ≤ 100 будут набирать не более 20 баллов.

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

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

4
5 3 4 1
4 6 2 7

20

6
8 7 1 2 1 9
6 11 4 1 5 7

38