Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Кошачий ужин#91273

В отеле есть традиция устраивать публичное вечернее кормление всех живущих в отеле кошек. Всего в нём живёт \(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\).

Задача на реализацию

✓ 2✗ 51 200средняяВойти и решать

Рекурсия - 2#84263

Дана блок-схема алгоритма F(A, B)

Найдите такую пару целых положительных чисел A и B (известно, что B > 1), чтобы вызов F(A, B) вернул число 1240029. Если таких пар существует несколько, найдите ту, у которой максимальное значение A. В ответе укажите через пробел сначала значение A и затем значение B.

Рекурсия

1 200труднаяВойти и решать

Непизанские кролики (2024-2025, 11)#80754

Дана блок-схема алгоритма, реализованного в виде рекурсивно вызываемой функции:

Известно, что 𝐴, 𝐵 и 𝐶 - натуральные числа и что 𝐴 < 𝐵 < 𝐶.
Петя вызывает эту функцию, передавая ей в качестве входного параметра натуральное число. Известно, что для некоторого 𝑘 функция возвращает следующие значения:
𝐹(𝑘) = 50890368413;
𝐹(𝑘 + 1) = 93601980590;
𝐹(𝑘 + 2) = 172160883161.
Определите значения 𝐴, 𝐵 и 𝐶, при которых это возможно. Если таких вариантов несколько, выберите вариант с наименьшей суммой 𝐴, 𝐵 и 𝐶. В ответе введите в указанном порядке значения 𝐴, 𝐵 и 𝐶, разделённые пробелом.

Рекуррентные последовательности Рекурсия

1 200труднаяВойти и решать

Перевод ДНК в аминокислоты#58285

В биоинформатике перевод ДНК-последовательности в последовательность аминокислот — ключевой шаг в анализе генетических данных. Каждая группа из трёх нуклеотидов (триплет или кодон) кодирует определённую аминокислоту в соответствии с генетическим кодом.

Необходимо:

Найти старт-кодон ATG.
Найти ближайший стоп-кодон (TAA, TAG, TGA) после старт-кодона.
Перевести последовательность между старт- и стоп-кодонами в аминокислотную последовательность.
Повторить процесс для всех возможных белков в последовательности.

Можете использовать словарь генетического кода: https://silvertests.ru/NoteBook.aspx?id=58286

Поиск подстроки в строке Строки

✓ 4✗ 481 200средняяВойти и решать

Подсчёт длины белков в последовательности ДНК#58281

В процессе трансляции последовательность ДНК сначала транскрибируется в РНК, а затем транслируется в белок. Белки кодируются участками между старт-кодоном (ATG) и ближайшим стоп-кодоном (TAA, TAG, TGA). Длина белка измеряется количеством аминокислотных остатков, где каждые три нуклеотида (триплет) кодируют одну аминокислоту.
Надо написать программу, которая:

Найти все белковые последовательности в заданной цепочке ДНК.
Подсчитать длину каждой белковой последовательности (в аминокислотах).
Вывести все найденные белки и их длины.

Длина белка в аминокислотах - это количество триплетов между старт- и стоп-кодонами.

Поиск подстроки в строке Строки

✓ 0✗ 341 400средняяВойти и решать

Никаких котлет#55395

В салон красоты пришли n девушек. Каждая из них должна посетить парикмахера и косметолога. У каждого она проводит по m часов. За какое наименьшее время k сотрудников салона красоты смогут обслужить всех девушек, если каждый сотрудник может выполнять функции как косметолога, так и парикмахера?

Входные данные
Вводится три натуральных числа k, m, n, не превосходяших 10 000.

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

Цикл while

✓ 1✗ 661 200средняяВойти и решать

Распредели призы#54199

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

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

Гарантируется, что N делится на K

Входные данные
На вход программы поступают два числа: N и K (1≤<N≤200, 1≤K≤200, K является делителем N).

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

Если распределить призы требуемым образом невозможно, выведите одно число 0.

Цикл for Эвристические методы

✓ 1✗ 151 300средняяВойти и решать

Подземелья Одинокой горы#50865

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

Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет \(b\) единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из \(k\) отрядов, уменьшается на \((k - 1) \cdot X\) единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда.

Известно, что в Средиземье проживают \(n\) рас, и количество существ \(i\)-й расы равно \(c_i\). Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.

Формат входных данных
Первая строка входных данных содержит три целых числа \(n\), \(b\) и \(X\) (\(1 \le n \le 200\,000\), \(1 \le b \le 10^6\), \(0 \le X \le 10^9\)) — количество рас и константы \(b\) и \(X\), описанные выше.

Вторая строка содержит \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 200\,000\)) — количество существ каждой из \(n\) рас.

Гарантируется, что \(c_1 + c_2 + \ldots + c_n \le 200\,000\).

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

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.

Замечание

В первом примере жители Средиземья могут составить \(3\) отряда. Так как \(X = 0\), то сила армии не уменьшится из-за количества отрядов. Далее жителей по отрядам можно распределить так:

Единственного представителя первой расы можно отправить в первый отряд.
Первого представителя второй расы можно отправить в первый отряд, второго представителя второй расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на \(b = 1\).
Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на \(3 \cdot b = 3\), так как они образуют три пары, находящиеся в разных отрядах.

Таким образом, суммарная сила армии равна \(4\).

Массивы

✓ 3✗ 21 200средняяВойти и решать

Какая формула?#50661

Формулу из ячейки {1} электронной таблицы скопировали в ячейку {2} и {3}. В результате в ячейке {2} получилась сумма значений ячеек {4} и {5}, а в ячейке {3} - сумма значений ячеек {6} и {7}. Какая формула могла быть записана в ячейке {1}?

В ответе укажите формулу без пробелов.

Вычисление по заданной формуле

1 300труднаяВойти и решать

Функции Pandas - 11#50302

Что из нижеперечисленного используется для получения столбцов с именами 'cl3' и 'cl5' из массива данных df?

print(df.loc['cl3','cl5'])
print(df.loc[['cl3','cl5']])
print(cls.iloc[['cl3','cl5']])
print(df.iloc['cl3','cl5'])

NumPy

1 300труднаяВойти и решать

Функции Pandas - 8#50299

Что выдает приведенный ниже код?
df.loc[df.clmn==10,:]

Возвращает столбцы clmn, в которых значение равно 10
Вернуть все столбцы фрейма данных df со значением, равным 10
Вернуть все столбцы clmn и первые 10 строк
Ничего из вышеперечисленного

NumPy

1 300труднаяВойти и решать

50100#50100

Карта Карно - графический способ представления логической функции, составляемый для формирования минимизированной функции в аналитическом виде.
Для логической функции от четырёх переменных f(a, b, c, d) карта составляется следующим образом:

ab cd	00	01	11	10
00	f(0,0,0,0)	f(0,0,0,1)	f(0,0,1,1)	f(0,0,1,0)
01	f(0,1,0,0)	f(0,1,0,1)	f(0,1,1,1)	f(0,1,1,0)
11	f(1,1,0,0)	f(1,1,0,1)	f(1,1,1,1)	f(1,1,1,0)
10	f(1,0,0,0)	f(1,0,0,1)	f(1,0,1,1)	f(1,0,1,0)

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

все значения истинны;
размер области равен 2n, где n - любое натуральное число.

При этом считают, что первый и последний столбец, а также первая и последняя строки расположены "рядом", то есть в них также можно формировать склейки.
Цель формирования склеек - выделить как можно меньшее их число, для этого склейки должны иметь наибольший размер и могут накладываться друг на друга.
Для логической функции от четырёх переменных требуется составить карту Карно, в которой указать разными цифрами формируемые склейки: самые большие для этой функции (по 8 элементов) - цифрой 4, следующие по размеру (по 4 элемента) - цифрой 3, и т.д.

Входные данные
16 строк, составляющие полную таблицу истинности функции. В каждой строке через пробел записаны значения переменных a, b, c, d и значение функции f в виде нулей и единиц (0 - значение ложно, 1 - значение истинно).

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0	0 3 3 0 3 3 3 3 0 0 0 0 0 3 3 2	Для заданной функции выделяются склейки во 2-й строке и в квадрате в первой и последней строках по 4 элемента (обозначены цифрой 3), а также склейка из двух элементов в конце 4-й строки. Поскольку она накладывается на предыдущую склейку, то только второй элемент в ней обозначен цифрой 2.
2	0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1	3 3 0 0 4 4 4 4 4 4 4 4 0 0 0 0	Для данной функции выделяется склейка во 2-й и 3-й строках, она состоит из 8 элементов и обозначается цифрой 4. Также выделяется квадрат из 4-х элементов (первые 2 в 1-й и 2-й строках), он накладывается на большую склейку, поэтому только его половина отмечена цифрой 3.

Задача на реализацию Логика

✓ 2✗ 11 200средняяВойти и решать

Магический квадрат подрядка N#49391

Магическим квадратом порядка N называется квадратная матрица размера NхN, составленная из чисел 1, 2, ..., N²так, называется квадратная матрица размера NхN, такая что суммы по каждому столбцу, каждой строке и каждой из двух больших диагоналей равны между собой. Напишите программу, которая проверяет, является ли заданная квадратная матрица магическим квадратом.

Формат входных данных
В первой строке вводится размер матрицы N (0 < N <= 100). В следующих N строках вводятся строки матрицы, по N значений в каждой, разделённые пробелами.

Формат выходных данных
Программа должна вывести слово 'YES', если матрица является магическим квадратом, и слово 'NO', если не является.

Двумерные массивы

✓ 1✗ 411 200средняяВойти и решать

Генераторы квадратов#48941

Множество \(A = \{a_1, a_2, \ldots, a_k\}\) различных натуральных чисел с суммой \(a_1+a_2+\ldots+a_k=n\) называется генератором квадратов, если сумма любых \(k-1\) элементов этого множества является полным квадратом целого числа.

Например, множество \(\{1, 22, 41, 58\}\) является генератором квадратов, так как \(1 + 22 + 41 = 64 = 8^2\), \(1 + 22 + 58 = 81 = 9^2\), \(1 + 41 + 58 = 100 = 10^2\), \(22 + 41 + 58 = 121 = 11^2\).

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

Формат входных данных
На ввод подаются два целых числа \(n\) и \(k\) (\(2 \le n \le 200\,000\), \(2 \le k \le 30\)).

Формат выходных данных
Если искомый генератор квадратов существует, выведите <<YES>> на первой строке, а на второй строке выведите \(k\) натуральных чисел "— искомое множество.

Если генератора квадратов с заданными параметрами не существует, выведите <<NO>>.

Вывод формулы Перебор реализация

✓ 1✗ 211 200средняяВойти и решать

Самые сильные волшебники#47475

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

Входные данные
Программа получает на вход в первой строке натуральное число n (2 < n < 10⁹) - количество юных волшебников. Далее идет n строк, в каждой из которых записано по 2 натуральных числа. Первое число - это идентификационный номер волшебника (1 <= номер <= n). Второе число - это мощность его волшебной палочки (100 <= мощность <= 200).

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

Примеры

№	Входные данные	Выходные данные
1	4 3 160 1 150 4 145 2 145	3 1 2

Цикл for

✓ 1✗ 1551 300средняяВойти и решать

Третий по росту#47383

В спортивной секции n спортсменов. У каждого спортсмена на футболке написан уникальный номер (от 1 до n). Тренер попросил выстроиться всех спортсменов по росту (от самого высокого к самому низкому). Найдите номер, который написан на футболке у спорстмена, который будет стоять на третьем месте. Если у нескольких спорстменов равный рост, то они выстраиваются по возрастанию номеров, записанных на футболке.

Входные данные
Программа получает на вход в первой строке натуральное число n (2 < n < 10⁹) - количество спортсменов. Далее идет n строк, в каждой из которых записано по 2 натуральных числа. Первое число - это номер (1 <= номер <= n), записанный на футболке. Второе число - это рост спортсмена (100 <= рост <= 200).

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	4 3 160 1 150 4 145 2 145	2

Цикл for

✓ 2✗ 1731 200средняяВойти и решать

Параллельное программирование#44715

Миша занимается параллельным программированием. Сегодня он пишет программу для исполнителя "Квадратик". Исполнитель "Квадратик" живет на клетчатом поле размера N х M, размер одной клетки 1х1. Перемещаясь он закрашивает клетку, на которой побывал. Клетку, на которой он начал движение и на которой остановился он также закрашивает.
Миша установил на поле K "Квадратиков". Каждый "Квадратик" будет двигаться в указанном Мишей направлении и останавливаться дойдя до конца поля. После окончании движения всех "Квадратиков", Миша хочет узнать сколько клеток поля получились закрашенными. Так как задача подсчета не относится к параллельному программированию, а размер поля может быть очень большим, Миша попросил вас написать программу для подсчета таких клеток.

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

Программа получает на вход несколько строк. Первая строка содержит целые числа M и N - размеры поля исполнителя "Квадратик" (1 <= M, N <= 10⁶). Во второй строке записано число K - количество "Квадратиков" на поле (0 <= K <= 10³). Далее идут K строк, каждая из которых описывает положение определенного "Квадратика" и направление, в котором он будет перемещаться. Формат каждой из таких строк: два целых числа, записанных через один пробел и один символ {N, E, S, W} - начальные координаты и направление движения соответствующего "Квадратика". Символ отделен от чисел ровно одним пробелом.
Символами обозначены следующие направления движения: N - вверх, S - вниз, W - влево, Е - вправо.

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

Выведите количество закрашенных клеток поля, после окончания движения всех "Квадратиков".

Пояснения
Поле исполнителя и расположение "Квадратиков" для первого примера, показаны на рисунке ниже. Стрелочкой обозначено направление движения соответствующего "Квадратика".

Примеры

№	Входные данные	Выходные данные
1	8 5 4 4 4 S 6 2 W 6 3 N 6 4 S	13

Двумерные массивы

✓ 6✗ 1201 200средняяВойти и решать

Массив сумм#44508

Юля выписала на доску n последовательных натуральных чисел a, a+1, …, a+n−1 и написала под каждым из них сумму его цифр в десятичной записи, под i-м числом было выписано sum_i.

После этого Юра стёр исходные числа и оставил только их суммы цифр. От вас требуется восстановить первое число в исходной последовательности a.

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

В первой строке содержится одно целое число n (2 <= n <= 100000) - длина исходной последовательности.

В следующей строке содержатся n целых чисел sum₁, sum₂, …, sum_n (1 <= sum_i<= 90) - суммы цифр чисел исходной последовательности.

Гарантируется, что для всех тестов существует подходящее a, такое что 1 <= a <= 10¹⁸.

Выходные данные
Выведите одно число a (1 <= a <= 10¹⁸) - первое число исходной последовательности. В случае, если существует несколько подходящих a, можно вывести любое.

Примечание

В первом тестовом примере сумма цифр 1 равняется 1, сумма цифр 2 равняется 2, сумма цифр 3 равняется 3, что соотносится с массивом sum, поэтому a = 1 подходит под условие задачи.

Во втором тестовом примере сумма цифр 77 равняется 14, сумма цифр 78 равняется 15, сумма цифр 79 равняется 16, сумма цифр 80 равняется 8, сумма цифр 81 равняется 9, что соотносится с массивом sum, поэтому a = 77 подходит под условие задачи.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3	1
2	5 14 15 16 8 9	77

Вывод формулы Задачи на моделирование

✓ 5✗ 1381 200средняяВойти и решать

Максимальный XOR - 2#44507

Два числа a и b записаны в шестнадцатеричной системе счисления. Запись обоих имеет длину n. Вы можете сколько угодно раз менять две соседние цифры местами в любом из чисел. Какое максимальное значение может быть у результата применения побитовой операции XOR к получившимся после применения таких перестановок числам?

Эта операция определена над двоичным представлением чисел.

Определим операцию побитового исключающего «ИЛИ» (XOR). Пусть даны два целых неотрицательных двоичных числа x и y длины k (возможно с ведущими нулями): x_k-1...x₂x₁x₀и y_k-1...y₂y₁y₀. Здесь x_i это i-й бит числа x, а y_i это i-й бит числа y. Пусть r = x XOR y - результат операции XOR над числами x и y. Тогда двоичной записью r будет r_k-1...r₂r₁r₀, где:

\(r_i = \begin{cases} 1, ~ \text{если} ~ x_i ~ \neq ~ y_i \\ 0, ~ \text{если} ~ x_i ~ = ~ y_i \end{cases}\)

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

В первой строке содержится одно целое число n (1 <= n <= 100000) - длина записи чисел. Во второй строке задана запись числа a. В третьей строке задана запись числа b.

Буквы A, B, C, D, E, F отвечают за цифры 10, 11, 12, 13, 14, 15 в шестнадцатеричной системе счисления соответсвенно. Записи могут содержать ведущие нули.

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

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

Примечание

В первом примере можно поменять две соседние цифры в первом числе, получится F0 XOR 0E = FE.

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

В третьем примере можно получить 101010 из a и 010100 из b.

Примеры

№	Входные данные	Выходные данные
1	2 0F 0E	FE
2	3 000 000	000
3	6 010110 011000	111110

Битовые операции

✓ 6✗ 71 200средняяВойти и решать

Надпись на табло#44288

Вы получили доступ к одной из камер наблюдения в особо секретной огранизации. В зоне видимости камеры находится табло, с которого вы постоянно считываете информацию. Теперь вам нужно написать программу, которая по состоянию табло определяет, какая буква изображена на нём в данный момент. Табло представляет из себя квадратную таблицу, разбитую на n × n равных квадратных светодиодов. Каждый диод либо включён, либо выключен. Введём систему координат, направив ось OX вправо, а ось OY — вверх, приняв сторону диода равной 1.
На табло могут быть изображены только следующие буквы:
• I — прямоугольник из горящих диодов.
• O — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом границы выключенного прямоугольника не должны касаться внешнего, то есть x1 < x3 < x4 < x2 и y1 < y3 < y4 < y2.
• C — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом правая граница выключенного прямоугольника находится на правой границе внешнего прямоугольника, то есть x1 < x3 < x4 = x2 и y1 < y3 < y4 < y2.

• L — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого есть прямоугольник из выключенных диодов с координатами углов (x3, y3) и (x4, y4). При этом правые верхние углы выключенного прямоугольника и внешнего прямоугольника совпадают, то есть x1 < x3 < x4 = x2 и y1 < y3 < y4 = y2.
• H — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого находятся 2 прямоугольника из выключенных диодов с координатами углов (x3, y3), (x4, y4) у первого и (x5, y5), (x6, y6) у второго. При этом выключенные прямоугольники должны иметь одинаковую
ширину, находиться строго один под другим, один прямоугольник должен касаться верхней стороны, а другой прямоугольник должен касаться нижней стороны внешнего прямоугольника, то есть x1 < x3 = x5 < x4 = x6 < x2 и y1 = y3 < y4 < y5 < y6 = y2.

• P — прямоугольник из горящих диодов с углами (x1, y1) и (x2, y2), внутри которого находятся 2 прямоугольника из выключенных диодов с координатами углов (x3, y3), (x4, y4) у первого и (x5, y5), (x6, y6) у второго. При этом правый нижний угол первого выключенного прямоугольника должен совпадать с правым нижним углом внешнего прямоугольника, а другой выключенный прямоугольник должен находиться строго выше и не касаться границ других прямоугольников, также левые границы двух выключенных прямоугольников должны совпадать, то есть x1 < x3 = x5 < x6 < x4 = x2 и y1 = y3 < y4 < y5 < y6 < y2.

• Любое другое состояние табло считается буквой X.
По виду табло определите, какая буква на нём изображена.

Входные данные
В первой строке входных данных находится одно число n (1 ≤ n ≤ 10) — сторона табло.
В следующих n строках находятся строки длины n из символов «.» и «#» — строки таблицы.
«.» обозначает выключенный квадратный диод табло, а «#» — горящий.

Выходные данные
Программа должна вывести единственный символ: если данная таблица подходит под одно из описаний букв I, O, C, L, H, P, то выведите её (все буквы — английские). Если же данная таблица не подходит ни под какие условия, то выведите X.

Примеры

№	Входные данные	Выходные данные
1	4 .##. .##. .##. ....	I
2	5 #...# .#.#. ..#.. .#.#. #...#	X

Задача на реализацию

✓ 2✗ 431 200средняяВойти и решать