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

Объединенная армия#38867

Для борьбы с могучими рейнджерами Рита Репульса и Лорд Зедд решили объединить Глиняный и Зедд патрули. Для более эффективного нападения на Энджел Гроув они хотят построить свою армию в две шеренги. Количество солдат в первой шеренге равно количеству солдат во второй.
Рита любит два вопроса:

«Правда ли, что ровно x из твоих соседей из Зедд патруля?»
«Правда ли, что ровно y из твоих соседей из Глиняного патруля?»

Соседями в данном построении являются солдаты слева и справа в той же шеренге, а также солдат, который стоит на той же позиции, но в другой шеренге. Рита выбрала либо один из этих вопросов либо оба, и задала каждому солдату. Всем солдатам были заданы вопросы с одними и теми же значениями x и/или y.
Зордан с помощью своей магической силы все это время наблюдал за процессом построения. Он был очень удивлен тем, что ответы всех солдат были положительными. Однако, он помнит, что солдаты из Зедд патруля всегда говорят правду, а солдаты из Глиняного патруля обязательно солгут хотя бы на один вопрос.
Так как солдаты из Зедд патруля наиболее опасны по мнению Зордана, исходя из ответов, он хочет узнать какое наименьшее и наибольшее количество солдат из Зедд патруля могло быть в объединенной армии. Он обратился к вам за помощью!

Входные данные
В единственной строке входного файла содержатся три целых числа k, x, y — количество солдат в одной шеренге и числа из вопросов (1 ≤ k ≤ 10⁵; -1 ≤ x, y ≤ 3).
Если x = -1, это означает, что Рита не задавала первый вопрос.
Если y = -1, это означает, что Рита не задавала второй вопрос.
Гарантируется, что Рита задала хотя бы один вопрос.

Выходные данные
Если для данных k, x и y не существует ни одного способа построения, выведите -1.
Иначе, первая строка выходного файла должна содержать одно число — наименьшее возможное количество солдат из Зедд патруля в армии.
В следующих двух строках должно содержаться по k символов «0» и «1» — описание шеренг:

«0» означает, что в построении на соответствующей позиции стоит солдат из Глиняного патруля.
«1» — солдат из Зедд патруля.

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

Примеры

№	Входные данные	Выходные данные
1	2 0 -1	2 01 10 2 01 10
2	5 1 2	0 00000 00000 4 01010 01010
3	1 2 2	0 0 0 0 0 0
4	10 0 3	5 0100010010 0001000100 8 0101010100 0010101010

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

Мегазорды#38866

Мегазорд — необходимая вещь для защиты Земли. Для сборки одного мегазорда, необходимо ровно три зорда: зеленый, красный и синий.
Зеленому, красному и синему рейнджеру стало интересно, сколько у них есть различных способов собрать мегазорд. Для каждого рейнджера известен набор зордов, которыми он обладает. У зеленого рейнджера есть зеленые зорды, у красного рейнджера — красные, а у синего — синие.
При сборке мегазорда необходимо соблюдать три правила:

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

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

Входные данные
В первой строке входного файла заданы числа g, r и b — количество зордов у зеленого, красного и синего рейнджера соответственно (1 ≤ g, r, b ≤ 10⁵).
В следующей строке находится g чисел x_i — номера моделей, которые есть у зеленого рейнджера (0 ≤ x_i ≤ 10⁹).
В следующей строке находится r чисел y_i — номера моделей, которые есть у красного рейнджера (0 ≤ y_i ≤ 10⁹).
В следующей строке находится b чисел z_i — номера моделей, которые есть у синего рейнджера (0 ≤ z_i ≤ 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	3 3 2 101 11 52 11 23 23 31 13	3

Замечание
Различные мегазорды из первого примера: 101 + 11 + 13, 52 + 23 + 31, 52 + 23 + 31. Последний мегазорд встречается дважды, так как красный ренжер мог взять либо второй, либо третий зорд. Обратите внимание, что собрать мегазорд 11+11+13 нельзя, так как при этом одна и та же модель будет использована дважны.

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

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

Рейнджеры в автобусе#38865

Не каждый день могучие рейнджеры надевают свои костюмы. Сами посудите: как нелепо они бы смотрелись, скажем, в общественном транспорте, если бы не снимали их!
Это создаёт определённые трудности злодеям, которые хотят выследить их. Вот и сегодня Рита Репульса не может их поймать, потому что не знает, как они выглядят без костюмов.
Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и Рита знает, кто на какое место сел и в каком порядке. Кроме того, ей известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:

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

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

Входные данные
В первой строке заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ min(2 · 10⁵, 2n)).
В следующих k строках описаны пассажиры в том порядке, в котором они заходили в автобус.
В i-й из этих строк заданы числа x_i и y_i — место, на которое сел i-й пассажир (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2), x_i — это номер ряда, y_i = 1, если это место слева от прохода, и y_i = 2, если справа.
Все места, на которые сели пассажиры, различны.

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

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1 1 2 3 2 2 1	3 1 2 4 1 2 0 1 3 4 1 2 3 4

Замечание

На этой картинке показаны места, на которые садились пассажиры в примере.

Задачи на моделирование Линейные алгоритмы

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

Закупка болтов и гаек - 04#38863

Магазин производит закупку болтов (bolt), гаек (nut), гвоздей (pin), шайб (shim) и винтов (screw), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	`6 1650 600 screw 750 bolt 750 shim 450 pin 300 nut 150 bolt`	`2 0`

ЕГЭ_информатика Использование сортировки

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

Закупка болтов и гаек - 03#38862

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	`6 1650 600 screw 750 bolt 750 nut 450 pin 300 nut 150 bolt`	`2 0`

ЕГЭ_информатика Использование сортировки

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

Закупка болтов и гаек - 02#38861

Магазин производит закупку болтов (bolt) и гаек (nut), на которую выделена определённая сумма денег. У метизного завода есть в наличии различные модификации этих изделий по розничной цене. При покупке менеджер руководствуется следующими правилами:

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

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

Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода (1 <= N <= 10⁵) и M - сумма выделенных на закупку денег (в рублях) (1 <= M <= 10⁹). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	`6 6500 1500 nut 500 nut 3500 bolt 3000 bolt 2500 nut 1000 bolt`	`2 500`

ЕГЭ_информатика Использование сортировки

✓ 12✗ 1101 100средняяВойти и решать

Закупка болтов и гаек - 01#38860

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

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

Входные данные
Программа получает на вход несколько строк. В первой строке расположены два числа через пробел: N - общее количество болтов и гаек у метизного завода и M - сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и тип изделия (bolt - болт, nut - гайка). Все данные в строках отделены одним пробелом.

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

Примеры

№	Входные данные	Выходные данные
1	`6 6500 1500 bolt 500 bolt 3500 nut 3000 nut 2500 bolt 1000 nut`	`2 500`

ЕГЭ_информатика Использование сортировки

✓ 33✗ 1481 000средняяВойти и решать

Переключение между окнами#38849

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

При запуске нового приложения оно добавляется в начало списка.

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

Входные данные
В первой строке вводится целое число n – количество действий пользователя ( 1 ≤ n ≤ 1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

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

Примеры

№	Входные данные	Выходные данные
1	6 Run Mozilla Firefox Run Free Pascal Alt+Tab Run Miranda IM Alt+Tab+Tab Alt+Tab+Tab+Tab	Mozilla Firefox Free Pascal Mozilla Firefox Miranda IM Free Pascal Free Pascal

Задачи на моделирование Список

✓ 68✗ 178900средняяВойти и решать

Кинотеатр#38847

Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид, Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо, затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна и сказала, что ребята сели неправильно – надо пересесть. Она предложила сначала заполнить все первые места от первого ряда к последнему, затем все вторые места и т. д.

Определите, сколько школьников после такой пересадки останется на своем месте.

Например, если n = 3 и m = 3, то в первом случае дети сядут так:

1   2   3
4   5   6
7   8   9
а во втором – так:
1   4   7
2   5   8
3   6   9
Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.

Входные данные
Вводятся два целых числа n и m (1 ≤ n, m ≤ 10⁹ ).

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

Примеры

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

НОД и алгоритм Евклида

✓ 170✗ 335600лёгкаяВойти и решать

Коровы#38846

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

Входные данные
В первой строке входного файла записано число досок N (0 <= N <= 1000). Далее для каждой доски записаны координаты кочек - концов доски (-2³¹ <= X_i,Y_i <= 2³¹). Затем записаны координаты начальной и конечной точек (точки различны и доски, их соединяющей нет). Все числа во входном файле целые.

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

Примеры

№	Входные данные	Выходные данные
1	8 0 0 1 0 1 0 2 1 1 0 2 -1 2 1 3 0 2 -1 3 0 1 0 4 0 3 0 4 0 0 0 3 0 0 0 4 0	2

Потоки

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

Премьер министр#38845

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

Входные данные
В первой строке входного файла находятся числа N - количество российских городов, соединенных железными дорогами в единую сеть и М - количество железнодорожных перегонов, соединяющих пары городов (1 <= N <= 20000, 1 <= M <= 200000). Города имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя городами проходит соответствующая железнодорожная ветка. В последней строке находятся два целых числа S и Е (1 <= S != E <= N) - номера Москвы и Владивостока по версии РЖД.

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

Примеры

№	Входные данные	Выходные данные
1	3 2 1 2 2 3 3 1	1 2

Обход в глубину

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

Одностороннее движение#38844

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

Входные данные
В первой строке входного файла находятся числа N - количество площадей в городе и М - количество улиц их соединяющих (1 <= N <= 20000, 1 <= M <= 200000). Площади имеют номера от 1 до N. В каждой из следующих M строк находится пара натуральных чисел, описывающая между какими двумя площадями проходит соответствующая улица (две площади соединяются не более чем одной улицей).

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

Примеры

№	Входные данные	Выходные данные
1	10 16 2 6 3 7 6 5 5 9 5 4 1 2 9 8 6 4 2 10 3 8 7 9 1 4 2 4 10 5 1 6 6 10	1 4

Обход в глубину

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

Бусинки#38843

Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер - целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых контуров не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой. Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре.

Входные данные
В первой строке записано число N (1 ≤ N ≤ 2500) - количество бусинок . В последующих N - 1 строках по два целых числа - номера, соединенных бусинок.

Выходные данные
Вывести одно число - искомое количество бусинок.

Примеры

№	Входные данные	Выходные данные
1	2 1 2	2
2	5 2 1 2 3 2 4 2 5	3

Обход в глубину

✓ 70✗ 284800средняяВойти и решать

Спелестология#38838

Спелестологический клуб «Залезь и посмотри» часто привлекается к поиску заблудившихся в каменоломнях незадачливых путешественников. Заблудившиеся в темноте и тесноте паникуют, хаотично перемещаются, ходят кругами и осложняют этим поисковые работы. Гораздо удобнее было бы, если бы потерявшиеся сидели в каком-нибудь зале и никуда не двигались.
Каменоломни представляют собой набор из N залов, занумерованных числами от 1 до N и M проходов между ними. Проходы могут быть как двусторонними, так и односторонними (например, с сильным вертикальным уклоном). Ни один проход не соединяет зал сам с собой. Пара залов может соединяться максимум одним проходом. Гарантируется, что двигаясь только по односторонним проходам, нельзя попасть в тот зал, из которого вышли путешественники.
Чтобы избежать хождения заблудившихся по кругу, члены клуба решили нанести на двусторонние проходы специальные аварийные стрелки так, чтобы идя по этим стрелкам нельзя было попасть в уже посещенное место, откуда бы ни началось движение и, в итоге, потерявшиеся оказались бы в одном из залов, из которого нельзя уйти, двигаясь по стрелочкам — там их и найдут спелестологи.
Для каждого двустороннего прохода определите допустимое направление движения.

Формат входных данных
В первой строке входных данных задается два числа N (2 ≤ N ≤ 100000) и M (1 ≤ M ≤ 100000) — количество залов и проходов между ними.
В следующих M строках задаются описания проходов. Каждое описание состоит из трёх чисел A, B и D (1 ≤ A, B ≤ N). Числа A и B задают номера соединенных проходом залов. Если D = 1, то проход односторонний из зала A в зал B. Если D = 2, то проход двусторонний.

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

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 1 2 4 2 2 3 1 3 4 1 4 1 2	2 4 1 4

Обход в глубину

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

Ананасы на Шешинеру#38832

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

Алиса хочет хочет отправить как можно большее число ананасов. Капитан Полосков решил ей помочь и с радостью согласился слетать на своем космическом корабле. Но есть один нюанс: на некоторых космических маршрутах можно дозаправить корабль, не превышающий максимально установленный вес. А заправлять корабль в пути нужно всегда, иначе он просто не долетит. Поэтому если корабль заполнить ананасами по максимуму, то, его не получится дозаправить в пути и поэтому не удастся воспользоваться самым коротким маршрутов, и придётся лететь через другие планеты. Может случиться даже так, что корабль не успеет долететь до Шешинеры вовремя, и ананасы испортятся.
Итак, сколько же ананасов можно погрузить в космический корабль, чтобы доставить груз вовремя?

Входные данные
Программа получает на вход несколько строк. В первой строке находятся числа n (1 <= n <= 500) и m - количество планет и количество космических маршрутов между планетми, соответственно. В следующих m строках записана информация о маршрутах. Каждый маршрут описывается в отдельной строке следующим образом. Сначала указаны номера планет, которые соединяются космическим маршрутом, потом время, которое тратится на перелет по этому маршруту, и, наконец, максимальный космического корабля, который можно заправить на этом маршруте. Известно, что все космические маршруты соединяют различные планеты, причем для каждой пары планет есть не более одного маршрута, непосредственно их соединяющий. Все числа разделены одним или несколькими пробелами.

Планеты нумеруются числами от 1 до n. Планеты Земля имеет номер 1, а планета Шешинера - номер n. Время перелета по маршруту задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что один ананас весит 100 грамм, а пустой корабль - 3 тонны.

Выходные данные
Выведите одно число - максимальное количество ананасов, которое можно доставить, потратив не более 24часов.

Примеры

№	Входные данные	Выходные данные
1	3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099	2

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

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

Найти Дэйва#38831

Беззработный Дэйв от скуки соорудил в собственной гостиной лабиринт из картонных коробок. Лабиринт содержит K входов. Когда его подружка Энни вернулась, лабиринт невероятным образом разросся изнутри, а сам горе-изобретатель там заблудился и не может выбраться.
Единственное, что нашла Энни в комнате это карту лабиринта, который имеет размеры NхM клеток. На карте было обозначено место, в котором находится Дэйв (как так вышло никто не знает). Клетки лабиринта либо пустые, по которым можно пройти, либо в них находится стена и по ним проходить нельзя. У клетки может быть до 4-х смежных клеток, в которую можно пройти из текущей.
Энни пригласила вас помочь ей определить, с какого входа нужно начать свой путь, чтобы побыстрее дойти до Дейва. Если таких входов несколько, Энни пойдет со входа с наименьшим номером.

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

Программа получает на вход несколько строк. В первой строке - 2 числа N и M (1<= N, M <= 100, NxM <= 100), размеры лабиринта. Далее следует N строк по M символов в каждой - описание лабиринта. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с Дэйвом.
В (N+2)-й строке находится число K (1<=K<=NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. В i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1<=xi<=N,1<=yi<=M).
Координаты входов попарно различны, все входы расположены в пустых клетках. Ни один из входов не находится в клетке с Дэйвом.

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

Выведите одно число - номер входа (нумерация начинается с 1). Если до Дэйва невозможно добраться, выведите -1.

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	1
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

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

✓ 13✗ 291 000средняяВойти и решать

Игрушечный лабиринт#38829

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

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

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

В первой строке входного файла записаны числа N и M – размеры лабиринта (целые положительные числа, не превышающие 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.

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

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

Примеры

№	Входные данные	Выходные данные
1	4 5 0 0 0 0 1 0 1 1 0 2 0 2 1 0 0 0 0 1 0 0	3

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

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

При каком наименьшем х?#38813

Значение выражения \( 27^7 - 3^{11} + 36 - x\) записали в троичной системе счисления, при этом сумма цифр в записи оказалась равной b (вводится с клавиатуры, 0 < b < 100). Напишите программу, которая выводит на экран минимальное натуральное значение x. Гарантируется, что ответ существует.

Задача на реализацию Системы счисления

✓ 119✗ 391700средняяВойти и решать

Сколько таких цифр? Решаем программой#38811

Результат арифметического выражения \(9^9 – 3^9 + 9^{19} – 19 \) записали в троичной системе счисления. Напишите программу, которая определит количество цифр "2", "1" и "0"в результирующем числе. Выведите ответ в одной строке, через пробел, в указанном порядке.

Задача на реализацию Разные системы счисления

✓ 331✗ 642200лёгкаяВойти и решать

Экспресс тест#38798

В данной задаче вам предлагается автоматизировать оценку результата экспресс теста.
Вам дана двухцветная картинка размером 10×20. Для обозначения цветов используются символы «#» и «.». Тест
считается отрицательным, если на картинке изображена одна вертикальная полоска и положительным, если три. В любом
другом случае тест считается испорченным.
Полоской будем считать область картинки 10×k, состоящую из символов «#», где k может быть произвольным. При этом
все соседние клетки с этой областью должны быть «.». Полоска может находиться на границе картинки.

Входные данные
В первой строке входных данных задано число t - число тестов (1 ≤ t ≤ 30). В следующих t⋅10+(t−1) строках заданы картинки
тестов. Соседние картинки разделены пустыми строками. После последней картинки, пустой строки нет.
Каждая картинка состоит из 10 строк по 20 символов, каждый из которых либо «#», либо «.».

Выходные данные
Для каждой картинки выведите результат теста в отдельной строке:
Negative - если тест отрицательный;
Positive - если тест положительный;
Incorrect - если тест испорчен.

Примеры

№	Входные данные	Выходные данные
1	4 .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........#.......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..##......#.....###. ..##......#.....###. ..##......#.....###. ..##......#.....###. ..#.......#.....###. ..#.......#.....###. ..##......#.....###. ..#.......#.....###.	Negative Incorrect Positive Incorrect

№

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

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

4
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........

.........##.........
.........##.........
.........##.........
.........#..........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........
.........##.........

..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.
..#.......#.....###.

..#.......#.....###.
..#.......#.....###.
..##......#.....###.
..##......#.....###.
..##......#.....###.
..##......#.....###.
..#.......#.....###.
..#.......#.....###.
..##......#.....###.
..#.......#.....###.

Negative
Incorrect
Positive
Incorrect

Алгоритмы обработки Задача на реализацию Задачи на моделирование

✓ 13✗ 33800средняяВойти и решать