Задача A. Amazon ≡

Условие

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

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

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

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

Первая строка входных данных содержит два натуральных числа, записанных через пробел: x₁ и y₁ — координаты белой амазонки. Во второй строке в том же формате содержатся координаты чёрного короля x₂ и y₂. Гарантируется, что позиции фигур различны.

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

Выведите Yes или No — ответ на вопрос задачи.

Ограничения

1 ≤ x₁, x₂, y₁, y₂ ≤ 8

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

Смотри рисунок. Во втором примере король может атаковать амазонку.

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

7 6
7 8

Yes

6 7
7 8

No

Задача B. Bonus points ≡

Условие

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

На доске записаны два n-значных числа, первое — состоящее только из цифры d₁, второе — только из цифры d₂. Определите, какая цифра находится на k-м месте в сумме этих чисел. Места пронумерованы слева направо начиная с 1.

Вам же нужны дополнительные баллы?

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

Четыре строки входных данных содержит четыре натуральных числа: n, d₁, d₂ и k. Гарантируется корректность k.

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

Выведите одну десятичную цифру — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁹

1 ≤ k ≤ n + 1

1 ≤ d₁, d₂ ≤ 9

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

В примере n = 2 (складываются двузначные числа), d₁ = 5 (первое число 55), d₂ = 8 (второе число 88). Сумма 55 + 88 = 143. k = 1 (учителя интересует первая цифра результата). На первом месте в числе 143 цифра 1.

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

2
5
8
1

1

Задача C. Clustering of triangles ≡

Условие

Имеется набор треугольников, заданных трехмерными координатами своих вершин.

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

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

Входные данные содержат натуральное число N, за которым следует 9 × N целых чисел, задающих координаты вершин:

(X1i, Y1i, Z1i), (X2i, Y2i, Z2i), (X3i, Y3i, Z3i), где i = 0, 1, …, (N − 1).

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

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

Сначала указывается число треугольников, включенных в набор, после чего следуют их номера во входных данных (нумерация начинается с 0).

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

Ограничения

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

 − 1000 ≤ (Xki, Yki, Zki) ≤ 1000,

2 ≤ N ≤ 10⁵.

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

6

 166  -61 -108
-175  122  133
 -81   96   71

-100 -228  246
 -64   58  -68
 -85   12  -27

 131 -140 -101
  37 -114  -39
  72  -35  -46

 137 -186 -113
  84 -127  -70
  66   11  -34

-140 -143  121
 -45  -73   98
  34   31   25

-135 -170 -173
 -86   45 -252
  39  124   31

3

3 3 2 0
2 4 1
1 5

Задача D. Digital circuit ≡

Условие

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

Логические элементы представлены как прямоугольные области, обрамленные рамкой из символов '#' (ASCII 35).

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

Описание может быть разбито на части, разделенные пробелами либо разнесенные по разным строкам.

Провода обозначены в виде последовательностей из символов '.' (ASCII 46).

Оставшееся свободное пространство схемы заполнено пробелами.

Рамки никаких двух элементов не могут стыковаться между собой (между ними всегда имеется зазор).

Провода могут стыковаться между собой только под углом в 90^∘.

Параллельные провода не могут идти вплотную друг к другу (между ними всегда имеется зазор).

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

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

Шина это набор связанных между собой проводов.

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

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

Входные данные содержат ASCII-изображение.

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

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

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

Далее указывается число шин M, за которым следуют наборы
подключенных к ним элементов.

В начале каждого набора указывается число его элементов,
затем следуют их номера
(начиная с нуля).

Ограничения

Общее количество символов изображения не превосходит 10⁶.

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

           #####        
#######    #abc#        
# xyz #    #123#        
#     #....#####   #####
#######    .       #   #
           .    ...#abc#
............    .  #   #
.               .  #####
. ############  .       
. #  123     #  .       
. #    xyz   #........  
. ############       .  
.         .          .  
...........          .  
          .    #########
          .....#  abc  #
 #######  .    #########
 #xyz  #...             
 #     #  .       ##### 
 # abc #  ........#123# 
 #######   .      ##### 
           #####        
           #xyz#        
           #####        

8
abc 123
xyz
abc
123 xyz
abc
xyz abc
123
xyz

3
6 0 3 4 5 6 7
3 2 3 4
2 0 1

Задача E. Equidistant strings ≡

Условие

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

Расстояние Хэмминга H(A, B) равно количеству позиций i от 1 до n таких что A[i] ≠ B[i].
Определим P(A, B) как множество строк длины n, равноудаленных от A и B ({ C: H(A, C) = H(B, C)}).

Требуется определить количество строк в множестве P(A, B).

Так как ответ может оказаться слишком большим, выведите остаток от его деления на 10⁹.

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

Входные данные содержат две строки: A и B.

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

Выведите единственное целое число — ответ.

Ограничения

1 ≤ n ≤ 10⁴.

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

abc
1b3

41688

ab
ab

1296

Задача F. Fencing the bishop ≡

Условие

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

Шахматная доска представляет из себя поле из 8 на 8 чередующихся белых и черных клеток. Столбцы шахматной доски обозначаются буквами от A до H, строки — цифрами от 1 до 8. Координаты клетки записываются как [столбец][строка], например, E2. Левый нижний угол, клетка A1, имеет черный цвет.

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

Ваша программа должна делать запросы вида "? A B", где A и B — координаты двух клеток игрового поля, левого нижнего и правого верхнего углов прямоугольника, за которым вы хотите установить мониторинг. После каждого запроса слон совершает ход, и вам сообщается в какие из наблюдаемых прямоугольников попал слон после этого хода.

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

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

В первой строке входных данных записана строка color, равная white или black — цвет клетки, на которой изначально стоит слон.

Протокол взаимодействия

Чтобы сделать запрос, ваша программа должна вывести "? A B", где A, B — строки из двух символов, координаты левого нижнего и правого верхнего углов прямоугольника, за которым нужно установить наблюдение.

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

Когда ваша программа определила текущее положение слона X, она должна вывести "! X", где X — строка из двух символов, координаты клетки слона. После вывода ответа программа должна завершиться.

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error". Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

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

Ограничения

"A1"  ≤ A, B, X ≤  "H8"

A ≤ B

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

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

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

white

0

01

000

0000

00000

100100

? B2 E4

? A4 C7

? A7 B8

? E4 F8

? H4 H8

? G1 H2

! E4

black

0

01

? A1 A1

? C3 C3

! C3

Задача G. Graph minimization ≡

Условие

Пусть нам известны два непересекающихся набора узлов некоторого ориентированного графа: A и B.
Для каждого узла из множества A задан набор всех достижимых из него узлов из B.
При этом узлы из A не должны иметь входящих ребер, а узлы из B — выходящих.

В графе также могут быть промежуточные узлы (множество C), связанные ребрами с узлами из A и B.
При этом никакие два узла из множества C не могут быть связаны между собой.

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

В качестве ответа следует вывести число узлов и ребер в полученном графе.

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

Входные данные содержат целые числа: N — размер множества A и M — размер множества B.
Далее следуют наборы узлов множества B, достижимых из каждого узла множества A.

В начале набора указывается число узлов в наборе (может быть нулевым),
а затем уже следуют номера самих узлов (нумерация начинается с нуля).

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

Выходные данные должны содержать два целых числа: число узлов и ребер.

Ограничения

1 ≤ (N, M) ≤ 1000

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

5 4

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

10 9

5 4

2 1 0
2 0 2
2 2 3
2 3 0
2 0 1

9 10

Задача H. Health and light ≡

Условие

В городке N — радостное событие! На единственной улице установят фонарь и откроют аптеку. Помогите градоначальнику установить оптимальное место для размещения этих объектов.

Представим улицу отрезком координатной оси, на которой самый левый дом имеет координату 0. Будем считать размер домов ничтожно малым по сравнению с протяженностью улицы и станем отмечать их точками на оси.

У фонаря есть параметр "яркость", выражающий, на каком максимальном расстоянии от фонаря всё еще светло. Например, при яркости, равной 10, фонарь, установленный в точке x = 25, будет освещать улицу на отрезке от 15 до 35, включая границы.

У аптеки есть параметр "удаленность", выражающий, на каком расстоянии домов от нее, люди, живущие в этих домах, будут её посещать. Например, при удаленности, равной 100, аптека, размещенная в точке x = 25, будет посещаться людьми, живущими в домах с координатами на отрезке от 0 до 125, включая границы (домов с отрицательными координатами нет).

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

Первая строка входных данных содержит три натуральных числа, записанных через пробел: n — количество домов, a — яркость и b — удаленность. В следующих n строках через пробел расположены по два неотрицательных целых числа x_i, q_i — координату дома и количество проживающих в нем людей (дома могут быть пустые).

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

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

Ограничения

1 ≤ n, a, b ≤ 10⁵

0 ≤ x_i, q_i ≤ 10⁹

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

В примере дано пять домов, яркость фонаря 15 и удаленность аптеки 20. Фонарь может быть установлен либо в точке 15, либо в точке 25, в обоих случаях освещено будет 4 дома. Аптеку можно расположить в точке 20, в этом случае посещать её смогут все жители города.

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

5 15 20
0 6
10 5
20 0
30 7
40 10

4 28

Задача I. Identical digits ≡

Условие

Женя Славин — первый человек, родившийся на Марсе. Он еще маленький, и очень любит смотреть на электронные часы, висящие напротив его кровати. Больше всего ему нравятся моменты, когда все цифры на табло становились одинаковыми. В такие моменты он всегда радуется и хлопает в ладоши.

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

• в одних марсианских сутках будет ровно h марсианских часов;
• в одном марсианском часе будет ровно m марсианских минут;
• в одной марсианской минуте будет ровно s марсианских секунд.

Текущее время на Марсе — h_M часов, m_M минут и s_M секунд. Через сколько секунд Женя захлопает в ладоши? Время на марсианских электронных часах выводится с ведущими нулями во всех разрядах, лишние разряды не используются.

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

Во входных данных содержатся шесть целых чисел, по одному в строке: h, m и s — описание разбиения марсианских суток, затем h_M, m_M и s_M — текущее время.

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

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

Ограничения

0 ≤ h_M < h ≤ 10⁶

0 ≤ m_M < m ≤ 10⁶

0 ≤ s_M < s ≤ 10⁶

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

В первом примере марсианские сутки ничем не отличаются от земных (24 часа по 60 минут по 60 секунд). Сейчас 23 часа 50 минут ровно (на табло горят цифры 23:50:00). Через 10 минут (или 600 секунд) на табло во всех разрядах будут гореть одни нули.

Во втором примере марсианские сутки содержат 627 часов по 5 минут по 777 секунд. Сейчас 49 часов 3 минуты и 2 секунды (на табло горят цифры 049:3:002). Через 61 час 3 минуты и 109 секунд (или 239425 марсианских секунд) на табло во всех разрядах будут гореть одни единицы.

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

24
60
60
23
50
0

600

627
5
777
49
3
2

239425

Задача J. Jolly evening ≡

Условие

Марина Цветаева, Андрей Белый и Саша Чёрный коротают вечер за шахматной доской. В каждой партии играют двое, третий ждет своей очереди, чтобы занять место проигравшего. Победитель предыдущей партии в следующей играет белыми фигурами.

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

Андрей Белый любит играть белыми фигурами, Саша Чёрный — черными, Марина Цветаева любит играть любым цветом. Определите количество партий, в которых оба противника играли своим любимым цветом. В самой первой партии встречались Белый (играл белыми) и Черный. Ни одна партия не завершилась вничью.

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

Две строки входных данных содержат два натуральных числа n и k.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁹

1 ≤ k ≤ 100

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

Было сыграно 4 партии, игравший белыми выигрывал 1 партию, следующую — проигрывал.

В первой партии Белый — Чёрный оба играют любимым цветом. Игравший белыми Андрей побеждает.

Во второй партии Белый — Цветаева оба играют любимым цветом. Игравший белыми Андрей проигрывает.

В третьей партии Цветаева — Черный оба играют любимым цветом. Игравшая белыми Марина побеждает.

В последней партии Цветаева — Белый только Марина играет любимым цветом. Итого ответ: 3 партии.

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

4
1

3

Задача K. Karousel ≡

Условие

В детском парке открылся новый аттракцион "Карусель" на n мест. Согласно технике безопасности при её эксплуатации рассаживать детей можно только таким образом, чтобы центр тяжести всех катающихся совпадал с центром карусели и расстояния между ними по окружности были одинаковыми. Например, при n = 6 одновременно могут кататься 2, 3 или 6 ребят, а при n = 5 — только ровно 5. Другими словами, разрешается запустить карусель, если на ней размещено k детей, причём k — делитель n и k ≠ 1.

В очереди к карусели стоит d детей. Дети, которые покатались на карусели, уходят в поисках новых развлечений. Какое минимальное количество запусков аттракциона следует осуществить, чтобы все дети прокатились на карусели ровно по одному разу?

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

Две строки входных данных содержат натуральные числа n и d.

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

Выведите одно натуральное число — ответ к задаче. Если всех ребят прокатить не получится, выведите -1.

Ограничения

1 ≤ (d, n) ≤ 10⁵

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

В первом примере дано n = 16 и d = 14 (карусель на 16 мест, в очереди 14 детей). Достаточно 3 запуска карусели: в первый раз прокатятся 8 ребят, во второй — 4, в третий — 2.

Во втором примере дано n = 15 и d = 7. Всех детей прокатить не получится, так как согласно правилам разрешено катать только по 3, 5 или 15 ребят.

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

16
14

3

15
7

-1