В офисе, где работает Бомбослав, установлены стильные дизайнерские часы. Их циферблат имеет стандартную разметку: на окружности расположены 60 делений, соответствующих минутам, 12 из которых (начиная с расположенного вверх от центра окружности, далее равномерно с шагом в пять делений) сделаны крупнее остальных, то есть соответствуют часам. Стильными эти часы делает тот факт, что циферблат не содержит никаких цифр, так как предполагается, что всем хорошо известно, какое деление соответствует какому значению текущего времени.
Сегодня над рабочим местом Бомбослава повесили такие часы. Периодически поглядывая на них, он сначала заметил некоторую странность в направлении движения стрелок. Приглядевшись внимательнее, Бомбослав обнаружил, что на самом деле над его рабочим местом находится зеркало, а часы расположены на стене за его спиной. Это означает, что Бомбослав видит циферблат отражённым относительно вертикальной оси, проходящей через его центр. Теперь он хочет научиться быстро определять настоящее текущее время, зная время, которое показывается на отражённом циферблате.
Часы устроены таким образом, что обе стрелки движутся дискретно, то есть что часовая стрелка всегда указывает на одно из 12 крупных делений, соответствующих текущему количеству часов, а минутная стрелка на одно из 60 делений, соответствующее текущему количеству минут.
В единственной строке входных данных записаны два целых числа h и m (0 ≤ h ≤ 11, 0 ≤ m ≤ 59) — положение часовой стрелки и положение минутной стрелки в отражённом циферблате соответственно. h = 0 означает, что часовая стрелка указывает вертикально вверх, h = 3 соответствуют стрелке, направленной строго направо, h = 6 — стрелка смотрит вертикально вниз, h = 9 — строго налево. Аналогичные указания верны для минутной стрелки для значений m = 0, m = 15, m = 30 и m = 45.
Выведите два целых числа x и y (0 ≤ x ≤ 11, 0 ≤ y ≤ 59) — реальное значение текущего времени на часах.
2 45
10 15
6 0
6 0
На картинке изображён первый тестовый пример. Левый циферблат соответствует тому, что видит Бомбослав, а правый — реальному положению стрелок. Часовая стрелка изображена красным цветов, а минутная синим.
Аркадий — большой фанат использования машинного обучения в любой задаче. Он верит в безграничную силу волшебства этой популярной молодой науки. Именно поэтому Аркадий постоянно постоянно придумывает всё новые и новые факторы, которые можно вычислить для различных объектов.
Напомним, палиндромом называется строка, которая одинаково читается от начала к концу и от конца к началу. Для каждой строки в своей базе данных Аркадий хочет найти самую короткую её подстроку, состоящую хотя бы из двух символов и являющуюся палиндромом. Если таких подстрок несколько, Аркадий хочет выбрать лексикографически минимальную.
В единственной строке входных данных записана одна строка из базы Аркадия — непустая последовательность строчных букв английского алфавита. Длина строки составляет не менее 2 и не превосходит 200 000 символов.
Выведите минимальную по длине подстроку строки из входных данных, состоящую хотя бы из двух символов и являющуюся палиндромом. Напомним, что среди всех таких строк Аркадий хочет найти лексикографически минимальную.
abac
aba
yandex
-1
Говорят, что строка a = a1a2... an лексикографически меньше строки b = b1b2... bm если верно одно из двух условий:
После работы Оля и Толя решили вместе сходить в тир. После прохождения вводного инструктажа и получения оружия они оказались на позициях для стрельбы, а напротив них находятся n мишеней. Все мишени можно считать фигурами, нанесёнными на бесконечную плоскость, при этом каждая мишень является кругом или прямоугольником, мишени могут накладываться и пересекаться произвольным образом.
Перед тем как начать стрельбу, Оля и Толя хотят убедиться, что они смогут однозначно идентифицировать результаты своих выстрелов. Для этого они договорились провести прямую, которая поделит плоскость с мишенями на две части. Однако, чтобы никому не было обидно, они хотят провести прямую таким образом, чтобы каждая мишень была поделена ровно пополам, то есть для каждого круга и каждого прямоугольника должно быть верно, что прямая делит его на две фигуры равной площади.
Когда Оля и Толя наконец закончили прорабатывать все условия разделения мишеней на две части, они начали сомневаться, что провести такую прямую вообще возможно, и просят вас ответить на этот вопрос.
В первой строке входных данных записано целое число n (1 ≤ n ≤ 100 000) — количество мишеней. Каждая из последующих n строк содержит целое число ti (0 ≤ ti ≤ 1), обозначающее тип мишени. Если ti = 0, то мишень является кругом и далее следуют три целых числа ri, xi и yi, определяющие радиус и координаты центра круга соответственно (1 ≤ ri ≤ 1000, - 10 000 ≤ xi, yi ≤ 10 000). Если же ti = 1, то мишень является прямоугольником, который затем определяют восемь целых чисел x1, i, y1, i, x2, i, y2, i, x3, i, y3, i, x4, i, y4, i — координаты всех четырёх вершин ( - 10 000 ≤ xj, i, yj, i ≤ 10 000), перечисленных в порядке обхода по часовой стрелки или против часовой стрелки. Гарантируется, что данные четыре вершины образуют прямоугольник ненулевой площади.
Если существует прямая, которая поделит каждый из имеющихся кругов и прямоугольников на две части одинаковой площади, выведите "Yes". В противном случае выведите "No".
Алексей регулярно проводит собеседования с кандидатами на позицию стажёра. И хотя он провёл уже не одну сотню собеседований, в последнее время этот процесс даётся ему нелегко — кандидаты стали без труда решать все годами протестированные и отработанные задачи Алексея!
Делать нечего, и в преддверии очередного собеседования Алексей придумал новую задачу. Имеется числовая последовательность, на первом шаге состоящая из двух чисел 1. На каждом шаге следующем шаге между каждыми двумя соседними элементами добавляется новый элемент, равный их сумме. После первых нескольких шагов последовательность выглядит следующим образом:
На собеседовании Алексей хочет попросить кандидата написать программу, которая по заданному числу n будет определять, сколько раз число n будет встречаться в последовательности на n-м шаге? Алексей ещё не научился решать свою задачу, но слышал, что кандидат, которого он будет сейчас собеседовать, добился высоких результатов в спортивном программировании, поэтому, скорее всего, легко справится с этим вопросом.
Во входных данных записано единственное число n (1 ≤ n ≤ 1013).
Выведите одно целое число, равное количеству вхождений числа n в описанную в условию последовательность на шаге n.
4
2
1
2
Для обеспечения сохранности пользовательских данных Аркадий постоянно изобретает и тестирует новые схемы организации резервного копирования. В этот раз он пронумеровал все имеющиеся у него компьютеры с данными от 1 до n и для каждого компьютера с номером от 1 до n - 1 назначил резервный компьютер pi. При этом он строго соблюдал правило, что номер компьютера для резервного копирования всегда больше номера самого компьютера, то есть pi > i. По этой причине, у компьютера с номером n компьютера для резервного копирования нет.
В ходе текущего эксперимента Аркадий выбрал некоторую конфигурацию значений pi и будет последовательно отключать компьютеры по одному каждую секунду. Эксперимент заканчивается, когда Аркадий отключает компьютер с номером n. Изначально, на каждом компьютере находится некоторый блок данных размера 1. При отключении компьютера с номером x, изначально расположенный на нём блок данных размера 1 передаётся на компьютер с номером px, при этом, если на компьютере номер x находилось другие блоки данных (полученные от других компьютеров при их отключении), то они исчезают. Если же компьютер px уже отключен, то и блок данных с компьютера x никуда не передаётся и тоже исчезает.
Аркадий хочет, чтобы эксперимент продолжался как можно дольше, но он вынужден соблюдать ещё одно дополнительное ограничение: если на каком-либо компьютере собирается k блоков данных, то в целях сохранности железа этот компьютер необходимо тут же выключить в течение следующей секунды. Обратите внимание, что последняя секунда (во время которой выключается компьютер n) не учитывается.
В первой строке входных данных записано целое число t (1 ≤ t ≤ 20) — количество тестовых примеров.
Далее следует t описаний тестовых примеров, каждое описание начинается со строки содержащей два целых числа n и k (1 ≤ n ≤ 100 000, 2 ≤ k ≤ 10) — количество компьютеров, участвующих в эксперименте и предельное количество блоков данных на одном компьютере соответственно. Вторая строка содержит n - 1 число p1, p2, ..., pn - 1 (i + 1 ≤ pi ≤ n).
Для каждого из t тестовых примеров выведите одно целое число — максимально возможную продолжительность эксперимента, то есть максимальный номер секунды, на которой Аркадий может отключить компьютер с номером n.
4
6 3
6 6 6 6 6
4 3
2 3 4
1 3
10 3
8 8 8 9 9 9 10 10 10
2
3
0
7
Для испытания новых алгоритмов машинного обучения Евгений использует n·m процессоров, расположенных в единичных клетках платы размера n × m. Таким образом, процессоры занимают n рядов, по m процессоров в каждом. При этом два процессора считаются соседними, если они расположены в соседних клетках одного ряда, или на одной и той же позиции в соседних рядах.
В результате неудачного эксперимента с новым алгоритмом некоторые из процессоров научились врать Евгению. Однако, благодаря тому, что была использована только базовая версия алгоритма, если какой-то процессор начинает врать, то он будет делать это всегда, поэтому результаты его работы всё ещё не сложно интерпретировать.
Теперь перед Евгением стоит задача определить, какие из процессоров постоянно выдают неверную информацию, но сначала он хочет оценить масштаб проблемы. Для этого он послал каждому из процессоров вопрос: верно ли, что среди соседних ему процессоров есть и исправные процессоры, и процессоры-лжецы? На удивление Евгения, все процессоры ответили на такой запрос утвердительно. Теперь он хочет узнать, какое минимальное количество процессоров-лжецов может находится на плате?
В единственной строке входных данных записаны два целых числа n и m (1 ≤ n ≤ 7, 1 ≤ m ≤ 100) — количество рядов в плате и количество процессоров в одном ряду соответственно.
Выведите одно целое число — минимальное возможное количество процессоров-лжецов на плате, при котором каждый процессор мог сообщить Евгению, что среди его соседей есть и исправные процессоры и процессоры-лжецы.
2 3
2
6 6
10
Одним из возможных решений в первой тесте является (испорченные процессоры отмечены как 1):
100
001