Информатика

Недавно директору Ресторана Отеля пришла в голову следующая мысль: <<Все какое-то обычное. Надо что-то модернизировать!>> Именно так и решили заменить всех официантов на роботов или, точнее, робоантов.

Но вот беда! Денег на закупку высококачественного оборудования не нашлось, и партия робоантов была заказана в ОАО <<В Гараже у Петровича>>. И вот теперь, спустя неделю работы по непонятным причинам робоанты начали глючить. Проблема в том, что скоро в Отеле большой банкет. Для его проведения в Ресторане уже расставили \(n\) столов и приготовили \(n\) блюд. Все блюда попарно различны и имеют номера от \(1\) до \(n\). Изначально, блюда по мере готовности как-то расставили по \(n\) столам, причем на каждый стол поставили только одно блюдо. Однако, к банкету необходимо расставить все на свои места, а именно, \(i\)-е блюдо должно оказаться на \(i\)-м столе.

Рядом с каждым столом изначально стоит робоант. Далее каждый робоант независимо от других может выполнять следующую операцию неограниченное число раз: пусть сейчас робоант стоит у \(i\)-го стола. Тогда, если у него с собой нет ни одного блюда, он может взять (а может и не брать) блюдо в данный момент, находящееся на \(i\)-м столе и перейти к любому \(j\)-му столу при условии, что \(i\) и \(j\) имеют общий делитель больший \(1\). Далее, если у робоанта есть с собой блюдо, он может положить его на \(j\)-й стол (а может и не класть).

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

Формат входных данных
В первой строке записано одно целое число \(n\) (\(1 \le n \le 200\,000\)) — количество столиков в Ресторане.

Во-второй строке записано \(n\) различных целых чисел \(a_1, a_2, \dots a_n\) (\(1 \le a_i \le n\)) — номера блюд изначально расставленных на соответственно \(1\)-й, \(2\)-й, …\(n\)-й столиках.

Формат выходных данных
Выведите <<YES>>, если робоанты смогут расставить все блюда по местам, и <<NO>> в противном случае случае.

Рассмотрим первый пример: здесь расставить все по местам может один робоант, изначально стоящий у второго стола. Для этого он:

1. Берёт со \(2\)-го стола \(8\)-е блюдо, перемещается к \(8\)-му столу, кладет блюдо.

2. Берёт с \(8\)-го стола \(2\)-е блюдо, перемещается ко \(2\)-му столу, кладет блюдо.

3. Перемещается к \(4\)-му столу.

4. Берёт с \(4\)-го стола \(6\)-е блюдо, перемещается к \(6\)-му столу, кладет блюдо.

5. Берёт с \(6\)-го стола \(4\)-е блюдо, перемещается к \(4\)-му столу, кладет блюдо.

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

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

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

Но не все так просто, некоторые питомцы слишком увлекаются едой и начинают толкать своего соседа справа во время трапезы, тем самым мешая другим кушать и портя общую милоту ужина. Допустим, вы знаете, что \(i\)-й котик толкается, тогда вы можете избежать толкания, если посадить либо \(i\)-го котика, либо \(i+1\)-го котика ужинать за общую миску, но в таком случае отсаженный котик уже не будет привносить милоту в общую милоту ужина. Вам известно, что толкание \(i\)-го котика своего соседа справа отнимает \(q_i\) общей милоты ужина. Таким образом, общая милота ужина вычисляется как сумма милоты всех котиков, которые ужинают за своей миской, из которой вычитаются все \(q_i\) котиков, которые толкают своего соседа на позиции \(i+1\).

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

Формат входных данных
Первая строка содержит одно целое число \(n\) \((1 \le n \le 10^6)\) — количество котиков.

Вторая строка содержит \(n\) целых чисел \((1 \le a_i \le 10^6)\), где \(a_i\) — милота \(i\)-го котика.

Третья строка содержит одно число \(m\) \((0 \le m < n)\) — количество котиков, толкающих своего соседа.

Каждая из последующих \(m\) строк содержит два числа \(k_i\) \((1 \le k_i < n)\) и \(q_{k_i}\) \((1 \le q_{k_i} \le 10^6)\), обозначающую, что если \(k_i\) котик толкается, то общая милота ужина уменьшается на \(q_{k_i}\).

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

В первом примере можно отсадить первого питомца к общей миске, а остальных отправить ужинать за свои миски. Суммарная милота благодаря тому, что котики кушают за своими мисками, будет равна \(20 + 30 + 40 + 50 = 140\), но третий котик будет толкать четвертого, поэтому из этой суммы вычитается \(q_3 = 25\). Таким образом, ответ на этот пример равен \(115\).

Вы с друзьями устроили марафон просмотра фильмов про отели, проголодались и решили заказать пиццу. Пока вы выбирали, с какого фильма начать просмотр, курьер с пиццей уже почти приехал. Вам пришло уведомление, что <<Курьер уже почти на месте>>, но прошло уже 5 минут, а пицца всё ещё не доставлена. Что же случилось?

Курьер действительно приехал по нужному адресу, но не может понять, действительно ли это тот отель, в который заказали пиццу. Вывеска отеля представляет из себя прямоугольник, состоящий из \(n\) строк по \(m\) заглавных латинских букв в каждой. И курьер не имеет ни малейшего понятия, где на ней написано название отеля.

Курьер попросил помощи у прохожего, на что тот ответил, что не помнит, как называется отель, зато знает, как найти название на вывеске. Он рассказал, что ещё совсем недавно у курьера не возникло бы проблем: на вывеске было только слово <<HOTEL>> и название отеля (также состоящее из 5 букв). Название начинается с буквы <<L>>, поэтому хозяин решил оформить вывеску так: он написал слово <<HOTEL>> так, чтобы соседние буквы граничили по стороне, а после этого так же (с тем же расположением букв относительно предыдущих) написал название, начав его с последней буквы слова <<HOTEL>>. Для лучшего понимания посмотрите, как могла бы выглядеть вывеска отеля с названием LUCKY:

Хозяину отеля так понравилось рисовать буквы, что он решил заполнить ими вообще все клетки матрицы-вывески. Чтобы у посетителя остался шанс найти название, хозяин вписал буквы так, чтобы ни в каком другом месте нельзя было прочитать слово <<HOTEL>>.

Зная всю эту информацию, курьер смог выяснить название отеля. А сможете ли вы?

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

В следующих \(n\) строках дана сама матрица-вывеска. Каждая из строк состоит из \(m\) заглавных букв латинского алфавита.

Гарантируется, что слово <<HOTEL>> встречается в матрице ровно один раз.

Формат входных данных
Выведите единственное слово из пяти заглавных латинских букв — название отеля.

На плоскости отмечены несколько красных, синих и черных точек. Требуется покрасить каждую черную точку в красный или синий цвет так, чтобы сумма расстояний между всеми парами красных точек и расстояний между всем парами синих точек было минимальным. На вход подается csv-файл, в первой строке которого записаны заголовки столбцов: id,x,y,color

Входные данные
В каждой из остальных строк записана информация об одной из точек: id, x и y — целые числа, color — 0 для черных точек, 1 для красных точек и 2 для синих.

Общее количество точек не превосходит 15.

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

Примеры

Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

• A. вычти 2
• B. вычти 4
• C. найди целую часть от деления на 2

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 86 результатом является 14, при этом траектория вычислений содержит число 39 и не содержит чисел 26 и 76?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы CBA при исходном числе 23 траектория состоит из чисел 11, 7, 5.

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

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Типовой пример организации данных в файле

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

• убрать из кучи 2 камня;
• убрать из кучи 4 камня;
• уменьшить количество камней в куче в 2 раза (количество камней, полученное при делении, округляется до меньшего).

Например, из кучи в 20 камней за один ход можно получить кучу из 18, 16 или 10 камней.

Игра завершается, когда количество камней в куче становится не более 20. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 20 или менее камней. В начальный момент в куче было S камней, \(S \geq 21\).

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

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

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

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

В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

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

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

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

В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

Алгоритм вычисления функций F(n) и G(n), где n – целое число, задан следующими соотношениями:

\(F(n) = F(n - 5) + 3219, \text{ если } n \geq 20; \\ F(n) = 8 \times (G(n - 9) - 34), \text{ если } n < 20; \\ G(n) = n / 24 + 32, \text{ если } n \geq 250\,000; \\ G(n) = G(n + 9) - 3, \text{ если } n < 250\,000. \)

Чему равно значение функции F(925)?

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

• в строке есть два числа, каждое из которых повторяется дважды, остальные три числа различны;
• максимальное число строки не повторяется.

В ответе запишите только число.

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.

Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:

Повтори 8 [Вперёд 33 Направо 90 Вперёд 15 Направо 90]
Поднять хвост
Вперёд 5 Направо 90 Вперёд 4 Налево 90
Опустить хвост
Повтори 8 [Вперёд 20 Направо 90 Вперёд 24 Направо 90]

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

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

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Типовой пример организации данных в файле

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Квадрат разлинован на N × N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.

Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

В «угловых» клетках поля – тех, которые справа и снизу ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.

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

В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

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

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

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

В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

Алгоритм вычисления функций F(n) и G(n), где n – целое число, задан следующими соотношениями:

\(F(n) = F(n - 5) + 3480, \text{ если } n \geq 21;\\ F(n) = 10 \times (G(n - 9) - 30), \text{ если } n < 21;\\ G(n) = n / 20 + 33, \text{ если } n \geq 264\,685;\\ G(n) = G(n + 9) - 2, \text{ если } n < 264\,685.\)

Чему равно значение функции F(675)?