Задача A. Марсианская лингвистическая реформа ≡

Условие

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

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

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

Например, если старое слово имело вид eeaaeeuinfaormaaiatoyuaoics, то новое слово будет таким: eeaaeeuinfaormaaiatoyuaoics ↦ informatics.

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

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

Ограничения

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

eeaaeeuinfaormaaiatoyuaoics

informatics

aeeaaayyaaauaaiaaiaacm

acm

bzzt

bzzt

Задача B. Домик для друзей ≡

Условие

Крокодил Гена и Чебурашка решили построить Домик для друзей, выбрав для него красивое место в точке c координатами (X_F, Y_F). Первым делом им необходимо доставить к этому месту кирпичи, складированные в точке (X_S, Y_S). Для этого герои решили воспользоваться проходящей неподалеку железной дорогой. Железная дорога представляет собой бесконечную прямую, совпадающую с осью Ox, по которой в любом из двух направлений может перемещаться дрезина с произвольным количеством кирпичей.

Герои задумали действовать следующим образом. Чебурашка будет носить кирпичи от точки (X_S, Y_S) до некоторой точки (X_A, 0) на железной дороге и там складывать их на дрезину. Затем кирпичи по железной дороге будут доставляться в некоторую другую точку дороги (X_B, 0), где их будет забирать Гена и нести до точки (X_F, Y_F).

К сожалению, Чебурашка невелик, и носить стопки кирпичей ему тяжело — на каждом полном километре пути он теряет по L_C штук. Во время перевозки материала по железной дороге на каждом полном километре пути разбивается по L_R кирпичей. Да и Гена, пока идет с грузом, отвлекается на окрестных шушанчиков, теряя из-за этого L_G кирпичей на каждом полном километре пути.

Теперь крокодила Гену и Чебурашку интересует вопрос, как выбрать точки X_A и X_B, чтобы суммарные потери строительного материала были минимальны.

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

Во входном файле содержатся целые числа X_S Y_S X_F Y_F L_C L_R L_G.

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

В выходном файле должны находиться два вещественных числа — абсциссы точек погрузки и разгрузки кирпичей — X_A и X_B, вычисленные с абсолютной ошибкой не более 10⁻³.

Ограничения

 −1000 ≤ Y_S < 0, 0 < Y_F ≤ 1000,

 −1000 ≤ X_S, X_F ≤ 1000,

0 ≤ L_C, L_R, L_G ≤ 1000.

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

0 -1
1 1
1 1 1

0.5 0.5

0 -1
1 1
10 1 10

0.125000 0.906250

Задача C. Транспортное кольцо ≡

Условие

Основная транспортная артерия города — дорога, имеющая форму кольца. Длина дороги составляет N километров. На ней есть N Т-образных перекрестков через каждый километр пути. Перекрестки пронумерованы числами от 1 до N в порядке обхода. Для каждого i от 1 до N, на i-ом перекрестке к кольцу примыкает дорога, имеющая длину a_i километров.

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

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

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

Выведите в выходной файл единственно число — искомое расстояние.

Ограничения

3 ≤ N ≤ 2 × 10⁵

1 ≤ a_i ≤ 10⁹

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

6
1 1 3 1 4 4

10

Задача D. Планета странной формы ≡

Условие

Торанианцы живут на планете, о форме которой не имеют никакого представления. Однако, им удалось составить карту поверхности планеты. Карта представляет собой прямоугольную таблицу N × M клеток. Угловые клетки имеют координаты (1, 1), (N, 1), (1, M), (N, M). Известно, что из каждой клетки можно перейти ровно в четыре соседние, причём если клетка находится на краю карты, то можно перебраться на клетку противоположного края. Например, при N = 10, M = 5 из клетки (1, 2) можно перейти в (1, 1)(1, 3)(2, 2)(10, 2), а для клетки (1, 1) соседними будут (2, 1)(1, 2)(10, 1)(1, 5).

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

Планетарное Правительство находится в клетке с координатами (x, y). Оно постановило создать в одной из клеток Планетарную Свалку. Согласно постановлению расстояние от свалки до клетки, занимаемой правительством, должно быть наибольшим. Требуется найти координаты свалки.

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

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

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

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

В приведенном ниже примере наибольшее расстояние равно 2. Возможные варианты расположения свалки — (2, 1) и (2, 3). Первые координаты равны, поэтому выводится ответ, у которого меньшая вторая координата.

Ограничения

1 ≤ N, M ≤ 10⁹

1 ≤ x ≤ N

1 ≤ y ≤ M

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

2 3 1 2

2 1

Задача E. Поездка на Хэллоуин ≡

Условие

Владивостокский программист приглашает коллегу к себе домой в гости на празднование Хэллоуина.

Оба программиста живут за городом. Их дома расположены в точках с координатами (X_A; Y_A) и (X_B; Y_B).

В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами начала (X_S; Y_S) и конца (X_E; Y_E). Дорога является платной: за любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение — не имеет значения) взимается плата в размере C_R. Остальная местность занята полями, которые (в связи со скорым Хэллоуином) сплошь засажены тыквами. При движении на автомобиле по полю взимается плата в размере C_F за каждый километр пути — ущерб за раздавленные тыквы.

Помогите программисту добраться к другу с минимальными затратами.

Обратите внимание, при сколь угодно малом приближении к дороге плата за въезд на неё не взимается. Смотрите пример №3.

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

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

Ограничения

−10³ ≤ X_A, Y_A, X_B, Y_B, X_S, Y_S, X_E, Y_E ≤ 10³

1 ≤ C_F ≤ 10³

1 ≤ C_R ≤ 10⁶

Дома программистов находятся в разных точках и не находятся на дороге

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

1 1 2 2 0 3 3 0 1 1

2.414213562373095

1 5 4 0
-2 -2 10 10
1 2

7.656854249492381

10 10 25 19
15 13 20 16
1 1000000

17.492855684535900

Задача F. Три плюс один ≡

Условие

Прямоугольник состоит из M × N квадратиков размером 1 × 1. Три вершины каждого квадратика раскрашены в белый цвет, а одна — в черный. Правильной считается раскраска, при которой стыкующиеся вершины квадратиков имеют одинаковые цвета.

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

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

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

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

В приведенном примере существует 10 раскрасок, а 10 по модулю 7 (т. е. остаток от деления 10 на 7) дает 3.

Ограничения

1 ≤ N, M ≤ 10⁵

2 ≤ m ≤ 10⁹

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

2 3 7

3

Задача G. Торанианхендж ≡

Условие

Планетарное Правительство торанианцев приняло решение о постройке масштабного комплекса скульптур в свою честь. Для этого на карте планеты был выделен прямоугольный участок, поверхность которого можно представить в виде таблицы W × H клеток, ориентированных вдоль сторон света.

Каждая клетка рассматриваемого участка может быть свободна для застройки и обозначаться символом '.' (ASCII 46), либо быть занята обелиском знаменитому торанианцу. Обелиски торанианцев строго симметричны либо вдоль направления восток-запад, либо вдоль направления север-юг, либо в обоих направлениях одновременно и обозначаются на карте как '|' (ASCII 124), '-' (ASCII 45) и '+' (ASCII 43) соответственно.

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

1. Cкульптуры, находящиеся в той же строке карты, что и любой обелиск, симметричный в направлении восток-запад, расположены симметрично относительно него.
2. Cкульптуры, находящиеся в том же столбце карты, что и любой обелиск, симметричный в направлении север-юг, расположены симметрично относительно него.
3. Для каждого обелиска, симметричного в направлении восток-запад, имеется хотя бы одна скульптура, находящаяся в той же строке.
4. Для каждого обелиска, симметричного в направлении север-юг, имеется хотя бы одна скульптура, находящаяся в том же столбце.

Требуется по данной карте участка составить план расположения скульптур или определить, что это невозможно.

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

В первой строке входного файла находятся числа W и H. В следующих H строках по W символов находится описание карты.

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

Выходной файл должен содержать H строк по W символов в каждой — искомый план сооружения. При этом J-й символ I-й строки должен быть символом '#' (ASCII 35), если в данную клетку следует установить скульптуру, и '.' (ASCII 46) — в противном случае. Если решений несколько, выведите любое из них.

Если составить план невозможно, выходной файл должен содержать единственную строку NONE.

Ограничения

1 ≤ W, H ≤ 100.

Поле содержит не менее одного и не более 100 обелисков.

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

3 2
.|.
-..

.#.
#..

3 2
.||
-..

NONE

6 4
......
...|..
.-....
......

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