#50

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

Темы: [Очередь] [Задачи на моделирование]

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

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

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

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

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

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

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

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

Примеры

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

1 3 5 7 9
2 4 6 8 0

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

second 5

#57

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

Темы: [Очередь]

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

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

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

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

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

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

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

Примеры

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

size
push 1
size
push 2
size
push 3
size
exit

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

0
ok
1
ok
2
ok
3
bye

#58

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

Темы: [Очередь]

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

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

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

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

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

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

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

Примеры

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

push 1
front
exit

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

ok
1
bye

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

size
push 1
size
push 2
size
push 3
size
exit

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

0
ok
1
ok
2
ok
3
bye

#59

Очередь неограниченного размера

Темы: [Очередь]

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

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

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

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

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

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

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

Примеры

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

push 1
front
exit

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

ok
1
bye

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

size
push 1
size
push 2
size
push 3
size
exit

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

0
ok
1
ok
2
ok
3
bye

#598

Маджонг

Темы: [Задачи на моделирование] [Очередь]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2007, 1 тур, Задача A ]

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

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

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

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

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

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

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

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

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

Примеры

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

1 2
1 1

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

1
1

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

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

2
2 1