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

После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".

Остался непрояснённым только размер сцены. Сцена размера \(K\) может выдержать \(K\) коров, танцующих одновременно. \(N\) коров в стаде (\(1 \leq N \leq 10,000\)) пронумерованы последовательно \(1 \ldots N\) в порядке, в котором они должны появиться на сцене во время танца. Каждая корова \(i\) планирует танцевать определённое время \(d(i)\). Изначально коровы \(1 \ldots K\) появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова \(K+1\) немедленно начинает танцевать и т.д. Поэтому всегда \(K\) коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени \(T\).

Понятно, что чем больше значение \(K\), тем меньше время \(T\). Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница \(T_{max}\), указывающая максимально возможное значение величины \(T\). Ваша задача - определить минимально возможное подходящее значение \(K\).

ФОРМАТ ВВОДА (файл cowdance.in):

Первая строка ввода содержит \(N\) и \(T_{max}\), где \(T_{max}\) - целое число, не более 1 000 000.

Следующие \(N\) строк задают длительности танцев \(d(1) \ldots d(N)\) для коров \(1 \ldots N\). Каждое из \(d(i)\) - целое число в интервале \(1 \ldots 100,000\).

Гарантируется, что если \(K=N\), шоу закончится вовремя.

ФОРМАТ ВЫВОДА (файл cowdance.out):

Выведите наименьшее возможное значение \(K\) такое, что танцевальное шоу закончится не более чем через \(T_{max}\) единиц времени.

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

66149#66149

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля, Маша, Саша и Наташа. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила ребятам сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть_2».
Правила игры оказались следующими:

·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;
·каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, по порядку слева-направо (первый игрок, второй игрок, третий и четвёртый), далее происходит определение победителей:
- если карты одной масти, то побеждает тот, у кого картабыла наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
- если карты разных мастей, то побеждает тот, у когомасть выше по значению (порядок мастей по возрастанию: червы, бубны, трефы, пики);
- если карт высшей масти несколько, то рассматриваетсяопределение наибольшего значения среди этих карт (например, выложили 10 червы, 8 бубны, 7 трефы, 8 трефы, то карты разных мастей, потому выбирается наибольшая масть – в данном случае трефы, таких карт две, среди них самая наибольшая 8 трефы, потому побеждает игрок 4);
·победитель забирает четыре карты в свою колоду по порядку,кладя сперва карту первого игрока под низ колоды, затем второго, третьего, четвёртого;
·побеждает тот игрок, который заберёт все картыпротивников.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого будут все 52 карты), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока, у второго, третьего, четвёртого.
Входные данные:
на первых 13 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты второго игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты третьего игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты четвёртого игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

c – червы;
b – бубны;
t – трефы;
p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

t – туз;
v – валет;
d – дама;
k – король.

Например:

(t,10) – десятка треф;
(c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) минимум у двух игроков останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока, у второго, у третьего, у четвёртого на одной строке через пробел (например, 48 3 1 0).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

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

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

66148#66148

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

каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, далее происходит определение, кто заберёт карты:

- если карты одной масти, то забирает карты тот, у когокарта была наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
- если карты разных мастей, то забирает карты тот, у когомасть выше по значению (порядок мастей по возрастанию: пики, червы, бубны, трефы);

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

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого не будет карт), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока и сколько у второго.
Входные данные:
на первых 26 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 26 строках подаются карты второго игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

c – червы;
b – бубны;
t – трефы;
p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

t – туз;
v – валет;
d – дама;
k – король.

Например:

(t,10) – десятка треф;
(c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) у всех останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока и у второго на одной строке через пробел (например, 50 2).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

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

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

65873#65873

Галактическая станция «Вавилон» имеет N (0 < N <= 10) ангаров для космических кораблей.
Цикл предполетной подготовки длится M (0 < M <= 10) суток. Цикл начинается в тот же момент, как корабль залетает в ангар. До окончания цикла корабль не может покинуть ангар и соответственно начать новый рейс.
Сутки на станции составляют 24 часа. Календарь на станции составляет 365 дней, которые не делятся на месяцы.
Вам попали в руки фрагменты станционного журнала (0 < K <= 1000 строк). В нем фиксируются даты и время прибытия кораблей в зону станции, а также заявки на рейсы со станции. Гарантируется, что все страницы относятся к одному году.
Если корабль подлетает к станции, а все ангары заняты, то ему отказывают в обслуживании. Если вылет со станции назначен на тот же час, что и прилет нового корабля, будем считать, что сначала ангар освобождается, а потом новый корабль размещается в пустом ангаре (начало цикла будет считаться с момента прилета).
Если приходит запрос на рейс со станции, то в рейс уходит тот корабль, который готов к вылету. Если таких кораблей несколько, то выбирается тот, который дольше находится на станции. Если готовых к рейсу кораблей нет, то рейс задерживают и ждут, когда появится корабль, который пройдет цикл предполетной подготовки. Если до конца периода кораблей для выполнения рейса не найдется, то заявка считается НЕ задержанной, а отклоненной.
По данным журнала определите скольким кораблям было отказано и сколько рейсов было отклонено в рассматриваемый период.

Входные данные:
В первой строке через пробел три числа N M K.
Дальше K строк в формате
День Час Признак
Где День – это номер дня от начала года; Час – час события; Признак это 1, если корабль прилетает, -1, если это запрос на вылет.
Выходные данные:
Два целых числа, каждое на новой строке:
– количество отказов в обслуживании;
– количество отклоненных заявок.

Примечание
В журнале 9 записей.
1) 1 9 1
2) 8 12 -1
3) 6 15 -1
4) 6 12 -1
5) 2 18 1
6) 5 6 1
7) 6 12 1
8) 7 12 -1
9) 2 21 1
Корабли, прибывшие 1-го в 9:00 и 2-го в 18:00, были поставлены в два ангара, имеющиеся на станции (1-ая и 5-ая строки журнала).
6-го числа в 12:00 1-ый ангар покинул корабль по заявке из 4-ой строки журнала. В тот же момент его место занял корабль с 7-ой строки.
На момент прилета кораблей из 6-ой и 9-ой строк оба ангара были заняты. Эти корабли получили отказ.
Выполнение заявок с 3-ей и 8-ой строк журнала было задержано, так как не было готовых к вылету кораблей.
Заявка со 2-ой строки была отклонена, так как в ангарах и на подлете в рассматриваемый интервал времени кораблей не было.

Жадный алгоритм Очередь

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

Летовецкая дуэль#60946

В деревне Летовецк, где живут мудрые старцы и их ученики, существует древняя игра, которая называется "Летовецкая дуэль". В этой игре два игрока сражаются друг с другом, используя стопку из 10 уникальных карточек, каждая из которых имеет значение от 0 до 9. Карточки раздаются поровну: каждому игроку достаётся по 5 карточек.

Правила игры просты:

Игроки одновременно открывают верхнюю карточку своей стопки.
Тот, чья крточка старше, забирает обе вскрытые карточки и кладёт их под низ своей стопки. При этом сначала кладётся карточка первого игрока, затем карточка второго.
Игра продолжается до тех пор, пока у одного из игроков не закончатся карточки. Этот игрок проигрывает.
Особое правило: карточка со значением 0 побеждает карточку со значением 9, даже если 9 обычно старше 0.

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

Формат входных данных
Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карточек первого игрока, вторая – аналогично 5 карточек второго игрока. Карточки перечислены сверху вниз, то есть каждая строка начинается с той карточки, которая будет открыта первой.

Формат выходных данных
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Очередь

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

Маджонг#55075

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

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

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

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

Задана начальная расстановка фишек на доске. Требуется найти самую длинную последовательность ходов, которую может сделать Петя из заданной позиции.
Входные данные
Первая строка входного файла содержит размеры доски: два целых числа m и n (1 ≤ m, n ≤ 300, хотя бы одно из этих чисел четно). Далее следуют m строк по n
чисел в каждой, j-е число в i-й из этих строк представляет собой номер цвета j-й слева фишки в i-й горизонтали. Цвета пронумерованы натуральными числами от 1 до n*m / 2. На доске ровно две фишки каждого цвета.

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

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

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

Раздача подарков#39396

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

Входные данные
Входная строка содержит числа N ( 1 <= N <= 10000 ) и K ( 1 <= K <= 10000 ), разделённые пробелом.

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

Примеры

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

Очередь

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

Очередь с защитой от ошибок#38603

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

push n
Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из очереди первый элемент. Программа должна вывести его значение.
front
Программа должна вывести значение первого элемента, не удаляя его из очереди.
size
Программа должна вывести количество элементов в очереди.
clear
Программа должна очистить очередь и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

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

Выходные данные
Требуется вывести протокол работы очереди, по одному сообщению на строке

Примеры

№	Входные данные	Выходные данные
1	push 1 front exit	ok 1 bye
2	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

Очередь

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

Простая очередь#38602

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

push n
Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из очереди первый элемент. Программа должна вывести его значение.
front
Программа должна вывести значение первого элемента, не удаляя его из очереди.
size
Программа должна вывести количество элементов в очереди.
clear
Программа должна очистить очередь и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

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

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

Примеры

№	Входные данные	Выходные данные
1	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

Очередь

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

Игра в пьяницу#38596

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

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

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

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

Входные данные
Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карт первого игрока, вторая – аналогично 5 карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.

Выходные данные
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Примеры

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

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

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

Комфортабельные коровы#38142

Пастбище Фермера Юрика может рассматриваться как огромная 2D-решётка ячеек (шахматная доска). Изначально пастбище пустое.

Фермер Юрик добавит N (\(1<=N<=10^5\)) коров на пастбище одну за другой. i-ая корова займёт ячейку (x_i,y_i), которая отличается от ячеек, занятых всеми другими коровами (\(0<=x_i,y_i<=1000\)).

Корова называется "комфортабельной", если она имеет ровно трёх соседей по горизонтали и вертикали. Комфортабельные коровы дают меньше молока, поэтому Фермер Юрик хочет добавлять коров пока нет комфортабельных (включая ту которую он добавит). Заметим, что добавляемые коровы не обязательно должны иметь координаты x и y в интервале \(0…1000\).

Для каждого i в интервале \(1…N\), выведите минимальное количество коров, которое он должен добавить, чтобы не осталось комфортабельных коров, если считать, что на пастбище находятся только коровы \(1…i\).

Входные данные
Первая строка содержит целое число N. Каждая из следующих N строк содержит по 2 разделённых пробелом целых числа (x, y), указывающих координаты ячейки с коровой.

Выходные данные
Минимальное количество коров, которое Фермер Юрик должен добавить, для каждого i в интервале \(1…N\), на отдельной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	9 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2 4 1	0 0 0 1 0 0 1 2 4	Для i=4, Фермер Юрик должен добавить корову в позицию (2,1), чтобы сделать корову в позиции (1,1) некомфортабельной. Для i=9, лучшее что Фермер может сделать - добавить коров в позиции (2,0), (3,0), (2,−1), (2,3).

Очередь Разбор случаев

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

Детская карточная игра#34979

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

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

Входные данные: Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карт первого игрока, вторая – аналогично 5 карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.
Выходные данные: Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Примеры

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

Очередь

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

Городской парад#30782

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

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

Входные данные
Первая строка ввода содержит одно целое число N (\(1 <= N <= 100\)) – количество платформ.
Вторая строка содержит N различных целых чисел от 1 до N – номера платформ в порядке прибытия.

Выходные данные
Вывести сообщение "YES", если можно обеспечить правильный порядок платформ, или сообщение "NO", если нельзя.

Примеры

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

Очередь

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

Морской бой - 3#30781

Всем известна увлекательная игра «Морской бой». Сейчас играть в Морской бой можно не только с соседом по парте, но и с компьютером. Игра c компьютером ведется на прямоугольном поле произвольных размеров N×M, где N - количество строк, M - количество столбцов. Приближается чемпионат мира по Морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.

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

Входные данные
Первая строка содержит два целых числа N и M (\(1<= N,M <= 10^3\)), разделённых пробелами. Это размеры игрового поля. Далее идут N строк по M символов - описание игрового поля. Английская буква 'X' обозначает подбитую клетку корабля, 'S' - не подбитую клетку корабля, '-' – свободное водное пространство.

Выходные данные
В ответе выведите через пробел три числа:
- количество целых кораблей;
- количество подбитых кораблей;
- количество уничтоженных кораблей.

Примеры

№	Входные данные	Выходные данные
1	3 8 ---SSS-- XX--S-X- X-S---S-	2 1 1

Очередь

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

Дело в шляпах#25919

Как-то раз в город Шляп заехал известный парикмахер. До его приезда парикмахеры были явно не очень, так как все жители города предпочитали ходить в шляпах. Но наконец-то настало время снять шляпы!

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

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

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

Местного шляпника теперь интересует, каким жителям ему больше не нужно будет делать шляпы, так как они будут ходить с новыми стильными стрижками?

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

В первой строке содержится число N (1 <= N <= 10⁵) количество людей, которые придут к парикмахеру.

Каждая из следующих N строк обозначает пришедшего к парикмахеру жителя и содержит по три числа: фасон шляпы (все фасоны местного шляпника пронумерованы от 1 до 10⁹), момент времени прихода s (1 <= s <= 10⁹), и время на стрижку t (1 <= t <= 10⁹). Строки упорядочены по времени прихода жителей. Гарантируется, что все приходят в разное время. Так как парикмахер очень крут, гарантируется, что он успеет постричь всех жителей до момента времени 2 · 10⁹, даже если бы из очереди никто не уходил.

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

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

Ввод	Вывод
5 1 2 7 2 4 3 2 6 2 1 7 3 3 8 2	1 4 5

Задачи на моделирование Очередь Разбор случаев

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

Легкая, вариант-2#24735

На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.

Перед отправкой ящики упаковывают и сортируют. Упаковка и сортировка ящиков неэффективна и происходит следующим образом:

Ящик под номером i поступает на склад.
Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
Поступающий ящик помещается наверх найденной или сформированной стопки.
Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.

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

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

В первой находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k) — номер размера и номер цвета ящика, который поступит i-м на склад.

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

Требуется вывести одно число — сколько ящиков будут отправлены.

Пример входных и выходных данных

Вывод	Ввод
5 2 1 1 1 2 1 1 1 2 1 1 1	4
5 1 2 1 1 1 2 1 1 1 2 1 1	0

Задачи на моделирование Очередь реализация

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

Легкая, вариант-1#24734

Ящик под номером i поступает на склад.
Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
Поступающий ящик помещается наверх найденной или сформированной стопки.
Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.

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

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

В первой строке находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k) — номер размера и номер цвета ящика, который поступит i-м на склад.

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

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

Пример входных и выходных данных

Ввод	Вывод
5 2 1 1 1 2 1 1 1 2 1 1 1	1
5 1 2 1 1 1 2 1 1 1 2 1 1	5

Очередь реализация

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

Раскраска#21884

Рисунок задан в виде матрицы A, в которой элемент A[y][x] определяет цвет пикселя на пересечении строки y и столбца x. Перекрасить в цвет 2 одноцветную область, начиная с пикселя (x0,y0).

Входные данные
В первой строке задается размер квадратной матрицы n (\(0<n<10\)). Во второй строке заданы координаты точки (x0, y0) - два числа через пробел (0 <= x0, y0 < n) . Далее идут n строк по n неотрицательных чисел в каждой через пробел (каждое число не больше 10).

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

Примеры

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

Источник: К.Ю. Поляков. Учебник. Информатика.

Очередь

✓ 704✗ 1 263600лёгкаяВойти и решать

Длина пути#19885

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.

Формат входных данных
В первой строке входных данных записано число N - количество вершин в графе (1 <= N <= 100). Далее с новой строки записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.

Формат выходных данных
Выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.

Обход в ширину Очередь

✓ 1 224✗ 3 024500лёгкаяВойти и решать

Наибольшее произведение#18715

Дано N целых чисел. Требуется выбрать из них три таких числа, произведение которых максимально.

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

На вход подается сначала число N - количество чисел в последовательности (\(3<=N<=100\)).
Далее идет сама последовательность: N целых чисел, по модулю не превышающих 1000.

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

Выведите три искомых числа в любом порядке.

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

Примеры

№	Входные данные	Выходные данные
1	9 3 5 1 7 9 0 9 -3 10	9 10 9
2	3 -5 -300 -12	-5 -300 -12

Очередь

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