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

A-функция от строчки#56657

Дана строка S, состоящая из N символов. Определим функцию A(i) от первых i символов этой сроки следующим образом:

A(i) = максимально возможному k, что равны следующие строки:

S[1]+S[2]+S[3]+…+S[k]

S[i]+S[i–1]+S[i–2]+…+S[i–k+1]

где S[i] – i-ый символ строки S, а знак + означает, что символы записываются в строчку непосредственно друг за другом.

Напишите программу, которая вычислит значения функции A для заданной строчки для всех возможных значений i от 1 до N.

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

Выходные данные
Выведите N чисел — значения функции A(1), A(2), … A(N).

Алгоритмы на строках

✓ 1✗ 5—Войти и решать

Кубическое уравнение#56655

Напишите программу, которая будет искать все целые X, удовлетворяющие уравнению

AX³ + BX² + CX + D = 0,

где A, B, C, D — данные целые числа.

Входные данные
Во входном файле записаны четыре целых числа: A, B, C, D. Все числа по модулю не превышают 2<=10⁹.

Выходные данные
В выходной файл выведите сначала количество решений этого уравнения в целых числах, а затем сами корни в возрастающем порядке. Если уравнение имеет бесконечно много корней, выведите в выходной файл одно число –1 (минус один).

Целые числа

✓ 2✗ 6—Войти и решать

Призы победителям сборов#56653

Оргкомитет и жюри Московской олимпиады проводят очередные учебно-тренировочные сборы. Победители туров на сборах получают в качестве приза мороженое. Поскольку мороженое имеет тенденцию таять, то оно должно храниться в холодильнике. Холодильник, имеющийся в 179 школе слишком мал для хранения всего запаса мороженого. Поэтому организаторы решили заказать специальный супер-пупер-большой холодильник. Новый холодильник должен быть параллелепипедом A × B × C и хранить ровно N кубических баночек мороженого размером 1 × 1 × 1. Для уменьшения потерь холода, общая площадь поверхности холодильника должна быть как можно меньше.

Например, если размер холодильника должен быть 12, возможными вариантами являются:

Размеры баночек	Площадь поверхности
3 × 2 × 2	32
4 × 3 × 1	38
6 × 2 × 1	40
12 × 1 × 1	50

Лучшим вариантом является 3 × 2 × 2.

Помогите организаторам сборов выбрать оптимальную форму холодильника.

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

Входной файл содержит одно число N (1 ≤ N ≤ 10⁶).

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

Выведите три числа A, B и C — оптимальные длины сторон холодильника. Если решений несколько — выведите любое из них.

Простые числа и разложение на множители

✓ 2✗ 2—Войти и решать

Крестики-крестики#56652

В игру крестики-крестики играют на поле размером 1 × N. Два игрока ходят по очереди. На каждом ходу игрок выбирает одну свободную ячейку и ставит там крестик. Если после его хода оказывается три крестика подряд, то он побеждает.

По известному N вам необходимо определить какой игрок победит при оптимальной игре обоих игроков.

Входные данные
Входной файл содержит одно число N (3 ≤ N ≤ 2000).

Выходные данные
Выведите 1, если побеждает первый игрок и 2, если побеждает второй игрок.

Функция Гранди

✓ 1✗ 0—Войти и решать

Класс Самолет#56450

На проверку сдается код, содержащий только описание классов!

Объявите базовый класс Aircraft (самолет), объекты которого создаются командой:

air = Aircraft(model, mass, speed, top)

где __model - модель самолета (строка, private); _mass - подъемная масса самолета (любое положительное число, protected ); _speed - максимальная скорость (любое положительное число, protected); _top - максимальная высота полета (любое положительное число, protected).

В каждом объекте класса Aircraft должны создаваться локальные атрибуты с именами: __model, _mass, _speed, _top и соответствующими значениями. Если передаваемые аргументы не соответствуют указанным критериям (строка, любое положительное число), то генерируется исключение командой:

raise TypeError('неверный тип аргумента')

Изменение и считывание значений атрибута __model должна осуществляться по имени (obj.model = ..., print(obj.model)

Далее, в программе объявите следующие дочерние классы:

PassengerAircraft - пассажирский самолет;
WarPlane - военный самолет.

Объекты этих классов создаются командами:

pa = PassengerAircraft(model, mass, speed, top, chairs)  
# chairs - число пассажирских мест (целое положительное число)

wp = WarPlane(model, mass, speed, top, weapons) 
# weapons - вооружение (словарь); ключи - название оружия, значение - количество

В каждом объекте классов PassengerAircraft и WarPlane должны формироваться локальные атрибуты с именами _chairs (protected) и _weapons (protected) соответственно. Инициализация остальных атрибутов должна выполняться через инициализатор базового класса.

В инициализаторах классов PassengerAircraft и WarPlane проверять корректность передаваемых аргументов chairs и weapons. Если тип данных не совпадает, то генерировать исключение командой:

raise TypeError('неверный тип аргумента')

Пример создания объектов

pa1 = PassengerAircraft('МС-21', 1250, 8000, 12000.5, 140)
pa2 = PassengerAircraft('SuperJet', 1145, 8640, 11034, 80)
wp1 = WarPlane('Миг-35', 7034, 25000, 2000, {"ракета": 4, "бомба": 10})
wp2 = WarPlane('Су-35', 7034, 34000, 2400, {"ракета": 4, "бомба": 7})

Задачи на процедуры и функции

✓ 3✗ 26—Войти и решать

Сигнализация#56315

Подземный бункер состоит из \(n\) комнат, соединённых \(n - 1\) коридорами. Каждый коридор соединяет две различные комнаты и имеет определённую длину. Бункер устроен таким образом, что из любой комнаты \(i\) можно дойти в любую другую комнату \(j\). Заметим, что существует единственный такой путь, не проходящий по одному и тому же коридору дважды. Сумма длин коридоров, составляющих этот путь, называется расстоянием между комнатами \(i\) и \(j\) и обозначается \(\rho(i, j)\).

Каждая комната бункера оборудована звуковой сигнализацией, состоящей из сирены и датчика звука, который её включает. Сирена, включённая в комнате \(i\), активирует датчик звука в каждой комнате, расстояние до которой не превосходит расстояние \(d_i\), определяемое мощностью этой сирены. Другими словами, включение сирены в комнате \(i\) автоматически включает сирену во всех комнатах \(j\), таких что \(\rho(i, j) \leq d_i\). Эта сирена, в свою очередь, может вызвать автоматическое включение других сирен и так далее.

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

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

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

Первая строка входных данных содержит единственное число \(n\) — количество комнат.

Вторая строка содержит последовательность из \(n\) целых чисел \(d_i\), \(i\)-е из них равно максимальному расстоянию, на котором расположенная в комнате \(i\) сирена активирует датчики (\(0 \leq d_i \leq 10^9\)).

Последующие \(n - 1\) строк описывают коридоры бункера. В \(i\)-й из них находятся три целых числа: \(u_i\), \(v_i\), \(l_i\), где \(u_i\), \(v_i\) — номера различных комнат, соединённых коридором \(i\), а \(l_i\) — длина этого коридора (\(1 \leq u_i, v_i \leq n\); \(1 \leq l_i \leq 10^9\)).

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

Замечание
В тесте из примера сирена в комнате 4 включает сирену в комнате 5, которая, в свою очередь, включает сирены в комнатах 6 и 7. Сирена в комнате 2 включает сирену в комнате 3. Сирена в комнате 8 включает сирены в комнатах 1, 9 и 10.

графы реализация Центроиды

✓ 1✗ 0—Войти и решать

Фонари#56311

Улицу Подводный канал освещают \(n\) фонарей, пронумерованных вдоль улицы от 1 до \(n\). Один или несколько подряд стоящих фонарей назовём сегментом. Таким образом, общее количество сегментов \(\frac{n(n+1)}{2}\). Сегмент считается исправным, если лампочки во всех фонарях этого сегмента исправны.

С фонарями регулярно происходят события одного из двух типов:

в каком-то сегменте из-за скачков напряжения все лампочки одновременно перегорают;

Архиэнерго выбирает некоторый сегмент и посылает ремонтников, чтобы заменить на нем все перегоревшие лампочки на исправные.

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

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

Входные данные
В первой строке входных данных содержатся два числа \(n\) и \(q\) — количество фонарей и количество произошедших событий. Следующая строка входных данных состоит из \(n\) символов 0 и 1, описывающих начальное состояние фонарей, где 1 обозначает фонарь с исправной лампочкой, а 0 — с перегоревшей.

В каждой из последующих \(q\) строк содержатся описания событий в виде трёх чисел \(l_i, r_i\) и \(c_i\), которые означают, что после этого события все лампочки в фонарях с номерами \(l_i, l_i+1, \ldots, r_i\):

перегорают при \(c_i = 0\),
становятся исправными при \(c_i = 1\).

В описаниях всех событий \(1 \le l_i \le r_i \le n\), а \(c_i\) принимает значение \(0\) или \(1\).

Выходные данные
В первой строке выходных данных выведите единственное число "— количество исправных сегментов в начальном состоянии. Затем по одному в строке выведите \(q\) чисел: для каждого из произошедших событий выведите количество сегментов, указываемых в отчёте после этого события.

Дерево отрезков, RSQ, RMQ дп

✓ 1✗ 0—Войти и решать

Подводная лодка#56309

Подводная лодка легла на грунт на мелководье. Для её обнаружения используются данные спутника, который с высокой точностью измеряет отклонение высоты поверхности воды от среднего уровня моря. Снимок, получаемый со спутника, представляет собой массив из \(h\) строк по \(w\) элементов в каждой строке.

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

<<корпус>> — полоса из элементов с координатами от \((x_1, y_1)\) до \((x_2, y_1)\), где \(x_1 < x_2\);
<<рубка>> — полоса из элементов с координатами от \((x_3, y_1)\) до \((x_3, y_2)\), где \(x_1 \leq x_3 < x_2\); \(y_1 \leq y_2\);
<<хвост>> — полоса из элементов с координатами от \((x_4, y_3)\) до \((x_4, y_4)\), где \(x_3 < x_4 \leq x_2\); \(y_3 \leq y_1 \leq y_4\).

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

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

Входные данные
Для сжатия передаваемых со спутника данных каждый элемент снимка кодируется строчной буквой английского алфавита. Первая строка входных данных содержит число \(k\) — количество использованных для кодирования букв (\(k \le 26\)). Вторая строка входных данных содержит \(k\) целых чисел \(c_i\) — значения отклонений соответствующих каждому кодовому символу по порядку букв в английском алфавите от 1 до \(k\)-й.

Третья строка входных данных содержит числа \(h\) и \(w\) — размеры снимка. Последующие \(h\) строк содержат по \(w\) символов — кодовые значения элементов снимка.

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

Примеры

№	Входные данные	Выходные данные	Изображение
1	2 -10 1 6 11 aaaaaaaaaaa aaabaaaaaaa aaabaaaabaa abbbbbbbbba aaaaaaaabaa aaaaaaaaaaa	13	........... ...b....... ...b....b.. .bbbbbbbbb. ........b.. ...........
2	3 -4 -3 4 5 5 bbabc ccaac accba baccb baaaa	16	..... .c... .cc.. ..c.. .....
3	3 -2 4 0 5 5 abccb cccac cbcba cccbb accba	24	.b... .c... .b.b. cccbb ...b.
4	4 -1 -5 -3 0 5 5 bbabc ccaac acdba baccb baaaa	-2	..... ..aa. ..... ..... .....

Пояснение

Для примера ниже приведены несколько потенциальных изображений подводной лодки.

Ниже приведены несколько множеств элементов снимка, которые не являются потенциальными изображениями подводной лодки:

Префиксные суммы(минимумы, ...)реализация

✓ 2✗ 0—Войти и решать

Гексагон#56233

Поле для игры в новую игру "Гексагон" разбито на шестиугольники (см. рисунок). Игрок, стартуя из некоторого начального шестиугольника, сделал несколько ходов. Каждый ход заключается в премещении фишки в соседний шестиугольник (имеющий с тем, где находилась фишка до начала хода, общую сторону) — тем самым, ход делается вдоль одного из направлений X, Y или Z (см. рисунок). Игрок записал все свои ходы, причем если фишка двигалась вдоль какого-либо направления несколько раз подряд, то в записи это обозначается указанием направления и количества ходов, которые были сделаны.

Напишите программу, которая найдет кратчайший (по количеству совершаемых ходов)путь в начальную клетку из той, где фишка оказалась после ходов игрока.

Входные данные
В первой строке записано число N — количество строк в записи перемещений фишки (1 ≤ N ≤ 100). Далее идет N строк с записью ходов: в каждой строке записана сначала большая буква X, Y или Z, задающая направление, затем пробел, и число, задающее количество ходов в данном направлении (число может быть и отрицательным, если игрок перемещал фишку параллельно оси, но в направлении, противоположном направлению оси). Все числа по модулю не превышают 200.

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

Примеры

№	Входные данные	Выходные данные
1	4 Z -2 Y 3 Z 3 X -1	4 Z -1 Y -1 Z -1 Y -1

Условный оператор

✓ 1✗ 6—Войти и решать

Выборы жрецов#56228

В стране Олимпиадии снова выборы.

Страна состоит из маленьких графств. Графства объединяются в конфедерации. Каждая конфедерация раз в год выбирает себе покровителя – одного из 200 жрецов. Этот ритуал называется Великими Перевыборами Жрецов и выглядит так: конфедерации одновременно подают заявления (одно от конфедерации) в Совет Жрецов о том, кого они хотели бы видеть своим покровителем (если заявление не подано, то считают, что конфедерация хочет оставить себе того же покровителя). После этого все заявки удовлетворяются. Если несколько конфедераций выбирают одного и того же Жреца, то они навсегда объединяются в одну. Таким образом, каждый Жрец всегда является покровителем не более чем одной конфедерации. Требуется написать программу, позволяющую Совету Жрецов выяснить номер Жреца-покровителя каждого графства после Великих Перевыборов. В Совете все графства занумерованы (начиная с 1). Все Жрецы занумерованы числами от 1 до 200 (некоторые из них сейчас могут не быть ничьими покровителями).

Входные данные
В первой строке записано число N – количество графств в стране (1 ≤ N ≤ 5000) – и далее для каждого графства записан номер Жреца-покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций. Сначала записано число M – количество поданных заявлений, а затем M пар чисел: первое число – номер текущего Жреца-покровителя, второе – номер желаемого Жреца-покровителя.

Все числа во входном файле разделяются пробелами и (или) символами перевода строки.

Выходные данные
Вывести для каждого графства одно число – номер его Жреца-покровителя после Великих Перевыборов. Сначала – для первого графства, затем – для второго и т.д.

Цикл for

✓ 3✗ 3—Войти и решать

Часы с боем#56227

Старинные часы бьют каждые полчаса. Причем в начале каждого часа они бьют столько раз, сколько сейчас часов (по 1 разу – в час ночи и в час дня, по 2 раза – в два часа ночи в два часа дня и т.д., в полночь и в полдень они бьют, соответственно, по 12 раз). И еще 1 раз они бьют в середине каждого часа.

Дан промежуток времени (известно, что прошло строго меньше 24 часов). Напишите программу, определяющую, сколько ударов сделали часы за это время.

Входные данные
В первой строке записан начальный момент времени, во второй строке — конечный. Моменты времени задаются двумя целыми числами, разделяющимися пробелом. Первое число задает часы (от 0 до 23), второе — минуты (от 1 до 59, при этом оно не равно 30).

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

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

✓ 3✗ 5—Войти и решать

Кубическая гостиница#56226

В связи с проведением межпланетного шашечного турнира было принято решение о строительстве орбитальной гостиницы. Она должна была представлять собой большой куб из N×N×N блоков – маленьких кубиков 1×1×1, и каждый блок должен был быть окрашен снаружи со всех сторон в какой-то один цвет. При этом некоторые блоки могли быть покрашены в один и тот же цвет.

Через год были сделаны фотографии гостиницы с каждой из 6 сторон: спереди, слева, сзади, справа, сверху, снизу. За год эксплуатации могло случиться так, что из-за непрочного крепления некоторые блоки, из которых была построена гостиница, оторвались и улетели в открытый космос. Комиссия по восстановлению гостиницы хочет по сделанным снимкам установить максимальное возможное количество оставшихся блоков.

Итак, вам необходимо по видам гостиницы (куба N×N×N, из которого, возможно, выкинуты некоторые кубики 1×1×1) с 6 сторон определить, из какого максимального количества блоков 1×1×1 она может состоять. Может оказаться так, что гостиница состоит из двух или более не связанных между собой частей.

Входные данные
В первой строке входного файла находится число N — размер гостиницы (1≤N≤10). На следующих N строках записаны виды гостиницы с 6 сторон (в следующем порядке: спереди, слева, сзади, справа, сверху, снизу). Каждый такой вид представляет собой таблицу N×N, в которой различными заглавными латинскими буквами обозначены различные цвета, а символом «.» (точка) — то, что в этом месте можно будет смотреть прямо сквозь гостиницу. Два последовательных вида отделяются друг от друга ровно одним пробелом в каждой из N строк.

Нижняя граница вида сверху соответствует верхней границе вида спереди, а верхняя граница вида снизу — нижней границе вида спереди. Для видов спереди, сзади и с боков верх и низ вида соответствуют верху и низу гостиницы.

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

Выходные данные
Выведите в выходной файл одно число — искомое максимальное количество оставшихся блоков в гостинице.

Перебор с отсечением

✓ 1✗ 0—Войти и решать

Склад#56225

Склад конторы MacroHard представляет собой прямоугольную комнату размером NxM. На складе нарисована разметка, состоящая из линий, параллельных стенам склада, которые разбивают его на NxM квадратов 1x1.

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

Размещать изделия на складе разрешается только так, чтобы хотя бы одна сторона изделия была параллельна какой-то из стен склада, и, вдобавок, все углы изделия находились в точках пересечения линий разметки склада. Рисунки 1,2,3 иллюстрируют неправильное положение изделий, а 4,5 –

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

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

Входные данные
В первой строке входного файла записаны три целых числа: N, M (размеры склада) и K (количество изделий, которые уже находятся на складе). Следующие K строк содержат по 6 целых чисел — координаты углов соответствующего изделия. Система координат введена так, что оси координат параллельны стенам склада и при этом один из углов склада имеет координаты (0,0), а противоположный — (N,M).

Ограничения

1<=N<=4, 1<=M<=4

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

Перебор с отсечением

✓ 1✗ 0—Войти и решать

Узор#56224

В комнате решили сделать паркетный пол. Причем есть задумка выложить на полу некоторый узор.

Плитки паркета, которыми выкладывается пол комнаты, состоят из квадратиков 1x1, каждый из которых может быть либо белым, либо черным. В свою очередь, комната имеет размеры NxM. На плане комнаты указано, какой квадрат комнаты какого цвета должен быть.

Существует несколько форм паркетных плиток:

Квадратики одной паркетной плитки могут быть окрашены по-разному. Может существовать несколько типов плиток одинаковой формы, но окрашенных по-разному. Плитки разных типов могут иметь разную стоимость. Количество плиток каждого типа не ограничено. Плитки разрешается как угодно поворачивать (на углы, кратные 90 градусам). Не разрешается разламывать плитки, а также класть их лицевой стороной вниз.

Изначально, какая-то часть пола может уже быть выложена плиткой.

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

Входные данные
В первой строке входного файла записаны три числа: N, M (размеры комнаты) и K (количество доступных видов плитки). 1≤N≤8, 1≤M≤8, 1≤K≤10. Далее идет описание желаемой раскраски пола. Описание представляет собой N строчек по M чисел в каждой, где 0 обозначает белый цвет, 1 — черный, 2 — то, что квадрат уже выложен плиткой. В последних K строчках находятся описания доступных типов плитки в следующем формате:

<форма> <стоимость> <окраска>

<Форма> — это число от 1 до 4, описывающее форму плитки (см. рисунок выше)

<Стоимость> — это натуральное число, не превосходящее 10000, задающее стоимость одной плитки такого типа

<Окраска> — это от одного до трех чисел 0 или 1. Количество чисел совпадает с количеством квадратиков, из которых состоит плитка. Числа задают цвета квадратиков плитки в том порядке, в каком квадратики пронумерованы на рисунке.

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

Динамическое программирование по профилю

✓ 1✗ 9—Войти и решать

Побег с космической станции#56223

Представьте, что вы состоите на службе во внешней разведке Межгалактического Альянса Республиканских Сил (МАРС). Одному из агентов разведки крупно не повезло, и он был захвачен на засекреченной космической базе. К счастью, внешней разведке МАРС удалось заполучить план этой базы. И вот теперь вам поручено разработать план побега.

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

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

Начальное положение вашего агента известно. Вам необходимо найти кратчайший путь побега (то есть путь, проходящий через минимальное количество отсеков).

Входные данные
В первой строке входного файла записаны числа N и M (2≤N≤100, 2≤M≤100), задающие размеры базы: N — количество строк в плане базы, M — количество столбцов. Во второй строке записаны начальные координаты агента X_A,Y_A (1≤X_A≤N, 1≤Y_A≤M). Первая координата задает номер строки, вторая — номер столбца. Строки нумеруются сверху вниз, столбцы слева направо.

Далее следуют N строк по M чисел, задающих описание стен внутри базы: 1 соответствует стенке, 0 — её отсутствию.

Далее в отдельной строке записано число H (0≤H≤1000) — количество гипертуннелей. В последующих H строках идут описания гипертуннелей. Каждый гипертуннель задается 4 числами: X₁, Y₁, X₂, Y₂ (1≤X₁,X₂≤N; 1≤Y₁,Y₂≤M) — координатами входа и выхода гипертуннеля. Никакие два гипертуннеля не имеют общего входа.

После этого в отдельной строке следует число K (1≤K≤10) — количество выходов с базы. В последующих K строках идут описания выходов с базы. Каждый выход задается двумя координатами X и Y (1≤X≤N; 1≤Y≤M).

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

Выходные данные
Если побег невозможен, выведите единственную строку с надписью "Impossible". В противном случае в первой строке выдайте число L - количество отсеков в кратчайшем пути побега. В последующих L строках последовательно выведите координаты отсеков кратчайшего пути побега. Если решений несколько, то выведите любое из них.

Обход в ширину

✓ 1✗ 0—Войти и решать

Разноцветные треугольники#56222

Выпуклый N-угольник разбит непересекающимися диагоналями на треугольники. (Многоугольник называется выпуклым, если любая его диагональ лежит внутри него.) Требуется покрасить каждую сторону и каждую проведенную диагональ в красный или синий цвет так, чтобы у каждого треугольника были стороны как красного, так и синего цвета.

Требуется привести любую из допустимых раскрасок.

Входные данные
В первой строке записано одно число N (4≤N≤100) - количество вершин многоугольника.

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

Выходные данные
В выходном файле должны быть 2N–3 строки. Каждая строка содержит 3 числа: номера вершин, которые соединяет данная сторона или диагональ и цвет (1 - синий, 2 - красный), в который Вы красите данную сторону или диагональ.

Конструктив реализация

✓ 1✗ 0—Войти и решать

Остаток от деления на цифру#56027

Напишите программу, вычисляющую остаток от деления заданного «длинного» числа на заданную цифру.

Входные данные
В первой строке задана цифра K (1≤K≤9). Во второй строке задано натуральное число N, состоящее из не более чем 250 цифр.

Выходные данные
Выведите остаток от деления N на K.

"Длинная" арифметика

✓ 7✗ 1—Войти и решать

Демо-2025-11#56017

На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 963-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 2000 серийных номеров отведено не более 693 Кбайт памяти. Определите максимально возможную длину серийного номера. В ответе запишите только целое число.

ЕГЭ_информатика

—Войти и решать

Демо-2025-10#56016

С помощью текстового редактора определите, сколько раз встречается сочетание букв "по" или "По" в составе других слов, включая сложные слова, соединенные дефисов, но не как отдельное слово в тексте глав XII и XIV третьей части тома 2 романа Л.Н. Толстого "Война и мир". В ответе укажите только число.

Файл к заданию

ЕГЭ_информатика

—Войти и решать

Демо-2025-09#56015

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

Файл к решению

ЕГЭ_информатика

—Войти и решать