Задача A. Двухцветная полоса ≡

Условие

Дана полоса, состоящая из N разноцветных клеток. Требуется написать программу, которая найдёт самый длинный отрезок этой полосы, состоящий из клеток не более двух разных цветов.

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

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

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

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

Если существует несколько оптимальных решений, выведите решение с минимальным значением P.

Ограничения

1 ≤ N ≤ 10⁶

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

xxxxx

1 5

abbaaccca

4 6

Задача B. Султан и мудрецы ≡

Условие

Однажды султан решил проверить знание математики у своих мудрецов.

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

Мудрецы начал выступать по очереди, i-й мудрец называл число a_i. И вот очередь дошла до N−1-го мудреца — Васи.

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

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

• N = 3;
• a_i ≤ 1000;

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

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

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

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

Если решений несколько, выведите любое из них.

Ограничения

3 ≤ N ≤ 10⁵

1 ≤ D, a_i ≤ 10⁹, a_i ≠ a_j∀ i ≠ j

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

18 4
2 6

1

26 5
2 5 9

4

13 4
2 5

-1

Задача C. Три точки на букву ≡

Условие

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

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

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

Если при рассмотрении точек слева направо их координаты y образуют возрастающую последовательность, то это буква '//'. Если убывающую — '\\'. Если последовательность точек сначала возрастает, потом убывает, это буква '/\'. Если сначала убывает, потом возрастает — '\/'.

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

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

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

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

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

Первая строка входного файла содержит целое число N — количество букв. Последующие N строк содержат по 6 целых чисел — x₁, y₁, x₂, y₂, x₃, y₃ — координаты точек буквы в произвольном порядке.

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

Выходной файл должен содержать N строк — '//', '\\', '/\', либо '\/' — названия соответствующих букв.

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

1
2 0 1 4 3 5

\/

Задача D. Питание программистов ≡

Условие

Оргкомитет сборов по программированию знает, что важно организовать правильное питание участников. Еда должна быть вкусной, а блюда — разнообразными. Поэтому разработку меню доверили повару тёте Вале.

Тётя Валя умеет готовить несколько разных блюд. Она использует для их обозначения маленькие английские буквы. Всего в течение сборов будет n приёмов пищи. Тётя Валя составила черновик меню — строку s, состоящую из n маленьких английских букв. Символ s_i обозначает блюдо, которое она запланировала для i-го приёма пищи.

Черновик меню полностью сбалансирован по всем питательным компонентам, но тётя Валя не особо заботилась о разнообразии.

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

Если существует несколько решений, выведите любое из них.

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

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

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

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

Ограничения

1 ≤ n ≤ 100000;

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

olmkoo

moloko

Задача E. Космос для школьников ≡

Условие

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

Учитель астрономии решил поддержать юных исследователей и выдал друзьям список существующих спутников, которые будут пролетать над городом, где живут Игорь с Олегом, в день предполагаемого запуска их спутника. Для каждого из N спутников в списке указан момент его пролёта над городом с точностью до минуты.

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

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

В первой строке входного файла содержится число N. Далее следуют N строк вида HH:MM, где HH — часы, MM — минуты.

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

Выходной файл должен содержать последовательность строк вида HH:MM - HH:MM или HH:MM — интервалы времени, в течение которых над городом нет спутников. Интервалы должны быть расположены в хронологическом порядке.

Ограничения

1 ≤ N ≤ 1440

0 ≤ H ≤ 23

0 ≤ M ≤ 59

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

2
10:10
10:12

00:00 - 10:09
10:11
10:13 - 23:59

4
10:11
10:12
10:10
10:13

00:00 - 10:09
10:14 - 23:59