Задача A. Дворец в квадрате ≡

Условие

Вы работаете программистом в строительной компании. Царь выдал компании заказ на постройку в Лесу фей дворца. Дворец должен иметь форму квадрата со стороной a и быть окружён квадратным садом. Прораб сообщил вам, что самый большой квадратный участок в Лесу имеет площадь S.

Команде садовников-аналитиков для разработки оптимального сада требуется знать, какой площадью для сада они располагают. Площадь для сада — это площадь на участке, не занятая дворцом.

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

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

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

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

Ограничения

1 ≤ a ≤ 1000

1 ≤ S ≤ 10⁸

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

1 1

0

2 10

6

2 2

-1

Задача B. Круговорот шушанчиков в природе ≡

Условие

Шушанчики — любимые питомцы олимпиадных программистов. Некоторые Человеки прознали об этом и быстро организовали бизнес по транспортировке и продаже этих милых зверей.

Ежедневно из Хабаровска во Владивосток транспортируется A шушанчиков, из Владивостока в Якутск — B шушанчиков, а из Якутска в Хабаровск — C шушанчиков.

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

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

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

В первой строке записано три целых числа A, B, C — количество ежедневно транспортируемых шушанчиков на каждом из маршрутов: из Хабаровска в Владивосток, из Владивостока в Якутск, из Якутска в Хабаровск соответственно.

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

В первой строке выведите два целых числа — количество шушанчиков, которых следует транспортировать из Хабаровска во Владивосток и из Хабаровска в Якутск соответственно.

Во второй строке выведите два целых числа — количество шушанчиков, которых следует транспортировать из Владивостока в Якутск и из Владивостока в Хабаровск соответственно.

В третьей строке выведите два целых числа — количество шушанчиков, которых следует транспортировать из Якутска в Хабаровск и из Якутска во Владивосток соответственно.

Ограничения

1 ≤ A, B, C ≤ 1000

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

13 3 7

6 0
0 0
0 4

5 5 5

0 0
0 0
0 0

Задача C. Timforces ≡

Условие

Существует много способов готовиться к олимпиадам по программированию. Один из них — решать задачи на сайте Timforces. На этом сайте есть рейтинг всех пользователей, составленный на основе количества решенных каждым пользователем задач. Нумерация мест в рейтинге начинается с 1, номера мест не повторяются. Чем больше задач пользователь решил, тем меньше его номер в рейтинге. Если два и более пользователей решили одинаковое количество задач, то они располагаются в произвольном порядке.

Алексей придумал понятие продвинутого пользователя. Продвинутыми считаются те пользователи, у которых количество решенных задач не меньше занимаемого места в рейтинге. Например, если пользователь занимает 3 место в рейтинге и при этом решил 5 задач, то он продвинутый, а если пользователь с 10 места решил лишь 9 задач, то он не продвинутый.

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

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

В первой строке входного файла записано одно целое число N — количество пользователей на сайте Timforces.

Во второй строке записано N целых чисел a_i — количество решенных задач у пользователя с i-го места в рейтинге.

В третьей строке записано одно целое число Q — количество вопросов Алексея.

Далее следует Q целых чисел p_i — суммарное количество задач, решенных некоторыми пользователями.

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

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

Выведите Q целых чисел — ответы на каждый вопрос Алексея.

Ограничения

1 ≤ N, Q ≤ 10⁵

0 ≤ a_i, p_i ≤ 10⁹

Пояснение к примерам

В первом вопросе Алексея из первого примера пользователь с третьего места может решить одну задачу и станет продвинутым. Помимо этого, продвинутыми уже являются пользователи с первого и второго места.

Во втором вопросе из первого примера пользователь со второго места может решить 2 задачи, пользователь с третьего места — 4 задачи, пользователь с четвертого места — 5 задач. Тогда положение пользователей в рейтинге изменится. Например, на первом месте нового рейтинга будет пользователь с четвёртого места старого рейтинга и т.д. Количество задач у пользователей в новом рейтинге: 7 6 5 4. В таком случае все пользователи являются продвинутыми.

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

4
4 3 2 2
2
1 11

3 4

4
5 1 0 0
5
1 4 5 10 11

2 2 3 3 4

Задача D. Забористый дизайн ≡

Условие

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

Забор состоит из N досок, i-я доска имеет высоту h_i и четную ширину w_i. Все доски заострены сверху, чтобы обеспечить безопасность. Согласно техническому заданию, эскиз забора необходимо выполнить в наилучшей CAD системе для проектирования — программе "Блокнот". Эскиз состоит из следующих символов:

• '-' и '|' для обозначения горизонтальной и вертикальной границы;
• '/' и '\' для обозначения заострённой части;
• '+' для обозначения углов;
• ' ' (пробел) для обозначения пространства внутри досок;
• '.' для обозначения пустого пространства вокруг забора.

Высота доски — количество символов от самой нижней части до самой верхней. Ширина доски — количество символов пространства между левой и правой границей доски.

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

Для полного понимания внимательно рассмотрите примеры.

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

В первой строке записано одно целое число N — количество досок в заборе.

Далее следует N строк, содержащих по два целых числа h_i и w_i — высота и ширина каждой доски.

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

Выведите эскиз забора в описанном формате.

Ограничения

1 ≤ N ≤ 50, 2 ≤ w_i, h_i ≤ 50, 2 + w_i2 ≤ h_i, Все w_i — четные.

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

3
5 4
8 6
6 8

......../\............
......./  \...........
....../    \..../\....
../\.+      +../  \...
./  \|      |./    \..
+    +      |/      \.
|    |      +        +
+----+------+--------+

1
3 2

./\.
+  +
+--+

2
5 2
5 6

./\.../\...
+  +./  \..
|  |/    \.
|  +      +
+--+------+

Задача E. Дошкольная сортировка ≡

Условие

Когда юному программисту Васе было три года, он уже знал, что буквы бывают "маленькие" (a, b, c, ..., z) и "большие" (A, B, C, ... Z), но ещё не выучил порядок букв в алфавите.

Мама играла с Васей в игру: она выписывала последовательность маленьких и больших букв, и спрашивала, "в порядке ли они". Если в последовательности шли сначала только маленькие буквы, а потом только большие, Вася отвечал YES (как будущий программист, он уже начал учить английские слова). Если в последовательности маленькие и большие буквы были перемешаны, Вася отвечал NO.

Напишите программу, которая будет действовать как Вася.

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

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

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

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

Ограничения

Длина входной строки от 1 до 10 символов.

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

maMA

YES

pRograMma

NO

zzzz

YES

AA

YES

Задача F. Алфавитное сжатие ≡

Условие

Недавно компания TIoN разработала новый способ сжатия сообщений.

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

После выбора отрезка он заменяется на "*n.d", где '*' — первая буква отрезка, 'n' — количество букв в отрезке, 'd' — разница между каждой парой соседних букв. Например, отрезок "cdefghi" после сжатия будет выглядеть как "c7.1", а отрезок "geca" — "g4.-2".

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

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

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

Первая строка содержит одно целое число N — длина сообщения.

Вторая строка содержит строку S — сообщение, которое подвергается сжатию.

Строка S состоит из строчных букв латинского алфавита.

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

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

Ограничения

1 ≤ N ≤ 10⁵

Пояснение к примерам

В первом примере есть два варианта сжатия сообщения: "x10.0t5.-4" и "x9.0x6.-4". Второй вариант короче первого на 1 символ.

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

15
xxxxxxxxxxtplhd

9

7
cdefghi

4

4
geca

4

Задача G. Вася и мысли ≡

Условие

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

В начале прогулки Вася размышляет о Важных Вещах, и ноги несут его с постоянной скоростью, равной либо v₁, либо v₂ м/c. Затем Вася отвлекается и начинает думать о Всякой Ерунде. В этот момент его скорость становится равной либо w₁, либо w₂ м/c.

Если Вася затратил на прогулку T секунд, каково максимальное возможное расстояние, пройденное им с Важными Вещами в голове?

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

Первая строка входного файла содержит числа D T. Во второй строке записаны числа v₁ v₂. В третьей строке записаны числа w₁ w₂. Каждое число имеет не более трёх знаков после десятичной точки.

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

Выходной файл должен содержать одно вещественное число d — максимальное возможное расстояние с точностью не менее 3 десятичных знаков.

Входные данные таковы, что решение всегда существует.

Ограничения

1 ≤ D, T ≤ 1000

10^− 3 ≤ v₁ < v₂ ≤ 10²

10^− 3 ≤ w₁ < w₂ ≤ 10²

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

10.0 5.0
1.0 3.0
0.5 1.0

9.0

15.0 3.0
1.0 2.5
4.25 6.1

2.291

25.0 5.0
1.0 3.0
4.0 5.0

0.0

Задача H. Три пути ≡

Условие

Цапля вилка недавно переехала в Антарктику в государство пингвинов — Пингвинию, и устроилась работать в местную логистическую компанию. Всего в Пингвинии N городов и M дорог, по дорогам можно двигаться в обе стороны. Исторически сложилось, что каждый пингвин посещает ровно три города (возможно проезжая по пути через остальные города). Пингвины не любят однообразие, поэтому одна из самых популярных услуг в логистической компании это прокладка маршрутов между тремя городами a, b, c так чтобы при проезде из a в b, из a в c, и из b в с существовал максимум один город который посещался 3 раза.

Как вы уже могли догадаться Цапля просит вас о помощи, у неё скопилось ровно Q запросов вида a, b, c. И для каждого запроса требуется вывести 3 пути, из a в b, из a в c, и из b в c, так чтобы эти пути удовлетворяли заданным требованиям.

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

Входной файл содержит числа N и M. Далее следует M пар чисел u_i и v_i, означающих что города u_i и v_i соединены дорогой. Далее следует число Q, за которым следует Q попарно различных чисел a_i, b_i, c_i.

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

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

Ограничения

3 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000, 1 ≤ M ≤ N ⋅ (N − 1)2, 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ a_i, b_i, c_i ≤ N

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

3 2
1 2
2 3
1
1 2 3

2 1 2
3 1 2 3
2 2 3

4 3
1 2
1 3
1 4
2
3 4 1
1 2 4 

3 3 1 4 
2 3 1 
2 4 1 
2 1 2 
2 1 4 
3 2 1 4 

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

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

Задача I. Игра Risk 1D ≡

Условие

Алиса, Вова и Слава решили поиграть в Risk 1D. В отличии от полной версии игры, игровое поле в 1D представляет из себя линию из N клеток-государств. Каждое государство соединено границей со своими соседями слева и/или справа.

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

Алиса выбрала себе в качестве начального государство с номером A, Вова — B, Слава — C. Первой ходит Алиса, потом Вова, потом Слава, далее по кругу. Каждый игрок старается максимизировать количество государств, которые будут у него после разделения.

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

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

В первой строке записано одно целое число N — количество государств.

Во второй строке записано три целых числа A, B и C — номера начальных государств Алисы, Вовы и Славы соответственно.

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

Выведите одно целое число — количество государств у Вовы, если все будут играть оптимально.

Ограничения

1 ≤ A < B < C ≤ N ≤ 1000

Пояснение к примерам

В первом примере Алиса может захватить государства с номерами 1, 2 и 3, Вова — 4 и 5, Слава — 6, 7 и 8.

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

8
2 4 6

2

11
2 4 8

3

15
12 13 15

2

Задача J. Я видел двойку! ≡

Условие

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

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

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

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

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

Выходной файл должен содержать только строки, содержащие не более одной двойки, в порядке, в котором они встречаются во входном файле. Если в строке встречается цифра кроме 0, 1, или 2, то программа "сходит с ума" и выводит единственную строку — ERROR.

Ограничения

1 ≤ n ≤ 100

Количество цифр в каждой из строк составляет от 1 до 100.

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

5
1110001010
111111111111
11111121110
1111211120
00000000012

1110001010
111111111111
11111121110
00000000012

3
000000011101
111111211111
1111111111113

ERROR