Задачи на моделирование

Мозаика

Мозаика состоит из N строк и M столбцов. Изначально все плитки были погашены. Обычная команда переключает все плитки одной выбранной строки или одного выбранного столбца; строки и столбцы можно выбирать повторно.

После всех обычных команд один лишний импульс мог переключить одну отдельную плитку. Лишнего импульса могло и не быть.

По окончательному состоянию определите координаты плитки, получившей лишний импульс, либо установите, что импульса не было.

Входные данные

В первой строке N и M (3 <= N, M <= 1000). Далее N строк по M символов без пробелов: 0 — плитка погашена, 1 — светится. Строки и столбцы нумеруются с 1.

Гарантируется, что состояние могло получиться описанным способом и ответ единственный.

Выходные данные

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

Ретрансляторы

Есть цепочка из N ретрансляторов. Радиограмма проходит их строго по порядку. Каждый ретранслятор ежедневно начинает передачу в своё фиксированное время HH:MM; длительность передачи T минут.

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

Доставка завершена в момент окончания последней передачи. Сутки длятся 1440 минут и нумеруются с 0.

Входные данные

В первой строке N и K (1 <= N <= 100000, 0 <= K <= 1440). Во второй строке начальное время HH:MM в нулевые сутки. Далее N строк: ежедневное время запуска HH:MM и длительность T (1 <= T <= 10^6).

Выходные данные

Выведите номер суток D и время HH:MM, когда закончится последняя передача.

Печати

На двери заброшенного архива Лера обнаружила ряд светящихся печатей. На каждой было записано положительное целое число. Рядом сохранилась надпись: «Истинная запись останется, когда исчезнут тройные печати».

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

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

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

Входные данные

В первой строке задано целое число N — исходное количество печатей (1 <= N <= 100000).

Во второй строке через пробел записаны N целых чисел от 1 до 10^9 включительно.

Выходные данные

В первой строке выведите M — количество оставшихся печатей. Если M > 0, во второй строке выведите оставшиеся числа слева направо. Если все печати исчезли, выведите только 0.

Ты ввёл silvertests.ru в адресной строке и нажал Enter. В каком порядке всё происходит?

1. HTTP-запрос → DNS → HTTP-ответ → отрисовка
2. Отрисовка → HTTP-ответ → DNS → HTTP-запрос
3. DNS → HTTP-ответ → HTTP-запрос → отрисовка
4. DNS → HTTP-запрос → HTTP-ответ → отрисовка

В расписании записаны моменты начала каждого урока (часы и минуты). Уроки идут в хронологическом порядке. Перерывом считается промежуток между концом одного урока и началом следующего. Каждый урок длится ровно 45 минут. Определите количество перерывов длительностью более 30 минут.

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

Каждая строка содержит два целых числа: часы и минуты начала урока (0 ≤ часы ≤ 20, 0 ≤ минуты ≤ 59). Последовательность заканчивается строкой «0 0». Она не является временем урока. Гарантируется, что уроков не менее двух.

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

Одно число — количество перерывов длительностью строго более 30 минут.

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

Но вот незадача, Портье ещё не успел освоиться на новом месте, как уже начались проблемы. Недовольные постояльцы вызвали его к себе в номер на шестом этаже, однако, по неопытности он заблудился и зашел в комнату \(404\)!!! А там…Лабиринт.

Лабиринт представляет собой последовательность из \(n\) дверей, расположенных друг за другом на одном этаже. Каждая \(i\)-я дверь покрашена в какой-то цвет \(a_i\), причём на этаже ровно по две двери каждого из цветов.

Допустим, что \(i\)-я и \(j\)-я двери покрашены в один и тот же цвет, причём \(i < j\). В таком случае, если Портье зайдёт в \(i\)-ю дверь, то он окажется между \(j\)-й и \((j+1)\) -й дверьми и сможет дальше зайти в одну из них. Если же он зайдёт в \(j\)-ю дверь, то он окажется между \((i-1)\) -й и \(i\)-й дверьми и далее сможет зайти в одну из них. Если \(i = 1\), то войдя в \(j\)-ю дверь, Портье окажется левее первой двери и далее сможет зайти только в неё же, а если \(j = n\), то войдя в \(i\)-ю дверь, он окажется правее последней двери и выберется из лабиринта.

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

Формат входных данных
В первой строке находится чётное число \(n\) \((2 \le n \le 200\,000)\) — количество дверей в лабиринте.

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)), где \(a_i\) — цвет \(i\)-й двери в последовательности. Гарантируется, что в лабиринте ровно по две двери каждого из цветов.

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

Ниже на картинке изображено пояснение к первому примеру из условия.

Вы с друзьями уже давно заехали в отель, но только сейчас выяснилось, что в отеле существуют так называемые <<Тихие часы>>. Во время этих часов все должны находиться в своих комнатах, и обойти это ограничение нельзя, потому ключи от комнат на время <<Тихих часов>> забирает персонал отеля. К счастью, вам повезло и вы с друзьями живёте на одном этаже, в последовательных комнатах с номерами от \(1\) до \(n\). Расстояние между соседними комнатами равно 5 метрам.

Вы пришли к достаточно изящной идее, которая поможет справиться со столь сложной ситуацией. За одну ночь под всеми комнатами вы проложили конвейер из \(3n\) ячеек, позволяющий перевозить посылки. Соседние ячейки, так же, как и комнаты, находятся на расстоянии 5 метров друг от друга. Ячейки конвейера с номерами от \(n + 1\) до \(2n\) находятся под комнатами друзей, ячейки с номерами от \(1\) до \(n\) – левее комнаты номер \(1\), а ячейки с номерами от \(2n + 1\) до \(3n\) – правее комнаты с номером \(n\).

В один из таких <<Тихих часов>> каждый друг отправил посылку одному другому другу. Для того, чтобы перемещать посылки, есть две кнопки: <<ВПРАВО>> и <<ВЛЕВО>>, сдвигающие конвейер на 5 метров вправо и влево соответственно.

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

Первая строка входных данных содержит одно целое число \(n\) (\(2 \le n \le 100\,000\)) — число друзей, обменивающихся посылками.

Вторая строка содержит \(n\) целых чисел \(a_i\) (\(1 \le a_i \le n, a_i \ne i\)) — номер друга, которому адресована посылка \(i\)-го из друзей.

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

Разберём пример из условия. Сначала можно 1 раз нажать кнопку <<ВПРАВО>>, после этого второй друг получит посылку от первого, а третий — от второго. После этого необходимо 2 раза нажать на кнопку <<ВЛЕВО>>, тогда второй друг получит посылку от третьего. И наконец, нужно ещё 2 раза нажать кнопку <<ВЛЕВО>>, после чего первый друг получит посылку от четвёртого. Итого потребуется 5 нажатий.

Отель представляет собой последовательность из \(n\) зданий различной высоты, построенных вплотную друг к другу. Не так давно в Отель провели кабельное телевидение, которым все теперь с удовольствием пользуются. Но есть одна проблема: на крыше \(m\)-го здания осталась куча оборудования от спутникового телевидения, которое надо с неё спустить, и вам поручили это сделать.

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

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

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

Формат входных данных
На первой строке вводится два целых числа \(n, m\) \((1 \le m \le n \le 100\,000)\) — число зданий и номер здания, на котором находится оборудование, соответственно.

Вторая строка содержит \(n\) целых чисел \(h_1, h_2, \dots, h_n\) \((1 \le h_i \le 10^9)\) — высоты зданий.

Формат выходных данных
Выведите одно целое число — минимальный размер лестницы, достаточной для демонтажа.

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

Входные данные

Выходные данные

Примечание