#111226

Темы: [Хеш]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача F ]

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

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

Первая строка входного файла содержит два натуральных числа N – число актеров и M – количество действий в спектакле (1 < N ≤ 100000, 1 ≤ M ≤ 100 000). В каждой из следующих M строк сначала записано количество актеров K_i, участвующих в i–ом действии (1 ≤ K_i ≤ N, K₁ + K₂ + ... + K_M ≤ 100 000), а затем K_i различных натуральных чисел, не превосходящих N, обозначающих фамилии этих актеров. Соседние числа в каждой строке разделены пробелом.

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

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

Примечание

В первом примере три актера участвуют в спектакле с тремя действиями. В первом действии участвуют два актера с номерами 1 и 2. Так как актеров всего трое, то после первого акта становится понятно, какой портрет соответствует актеру с номером 3, поэтому третье число строки выходного файла равно 1. Во втором действии участвуют два актера с номерами 3 и 2. Поскольку только второй актер участвовал и в первом, и во втором действиях, то его портрет можно определить после второго действия. А так как портретов всего три, то после второго действия можно установить, что последний портрет соответствует актеру номер 1. Третье действие на ответ не влияет.

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

(оценивается в 30 баллов) Количество актеров N не превосходит 100, количество действий M не превосходит 100, K₁ + K₂ + ... + K_M ≤ 100.
(оценивается в 30 баллов) Количество актеров N не превосходит 10 000, количество действий M не превосходит 10 000, K₁ + K₂ + ... + K_M ≤ 10 000.
(оценивается в 40 баллов) Количество актеров N не превосходит 100 000, количество действий M не превосходит 100 000, K₁ + K₂ + ... + K_M ≤ 100 000.

Примеры

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

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

2 2 1

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

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

0 3 0 0 0

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

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

1 3 2 3

#111227

Ордынское войско

Темы: [Перебор] [Динамическое программирование: последовательности]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача H ]

Готовясь к бою, хан Гирей пронумеровал всех воинов своего войска натуральными числами от 1 до N. Поскольку воины умеют сражаться, но не умеют считать, при любом построении в шеренгу они выстраиваются в произвольном порядке. Одного или несколько воинов, стоящих в шеренге, будем называть отрядом. Отряд назовем правильным, если номера этих воинов в том порядке, в котором они стоят в шеренге, образуют упорядоченную по возрастанию последовательность чисел. Среди всех правильных отрядов хан Гирей выбирает ударный отряд – самый большой по количеству воинов. Так, в шеренге 1 3 2 4 из четырех воинов ударными являются отряды 1 3 4 и 1 2 4, а отряд 1 4 – один из правильных, но не ударный. Некоторые воины являются личными телохранителями хана Гирея. Требуется составить программу, определяющую количество таких шеренг, в которых телохранители хана образуют ударный отряд.

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

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

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

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

Примечание

В первом примере войско состоит из пяти воинов. Ударный отряд должен состоять из трех воинов с номерами 1, 3 и 4. Этому условию удовлетворяют следующие 11 шеренг: (1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4).

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

(оценивается в 40 баллов) 1 ≤ N ≤ 8.
(оценивается в 10 баллов) 9 ≤ N ≤ 10.
(оценивается в 10 баллов) N = 11.
(оценивается в 10 баллов) N = 12.
(оценивается в 10 баллов) N = 13.
(оценивается в 10 баллов) N = 14.
(оценивается в 10 баллов) N = 15.

Примеры

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

5
3
1 3 4

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

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

3
3
1 2 3

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

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

1
1
1

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

#111562

Ёжик в тумане

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача G ]

Ёжик спустился в туман и оказался в прямоугольной долине размером N на M метров, по которой бродит Лошадь. Ёжик хочет ее найти. Будем считать, что в каждый момент времени и Ёжик, и Лошадь находятся в одной из N × M клеток. Туман настолько густой, что Лошадь не видно, даже если она находится в той же самой клетке , что и Ёжик. К счастью Ёжик обладает очень острым слухом и может понять, в каком направлении сместилась Лошадь. Он также может позвать Лошадь, и, если она находится в одной клетке с Ёжиком, то Лошадь его услышит и обязательно отзовется.

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

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

Протокол взаимодействия

Сначала программа-решение должна прочитать из стандартного потока ввода натуральные числа N и M, записанные в первой строке, а из второй строки координаты начального местоположения Ёжика – два натуральных числа: x₀ – номер столбца, y₀ – номер строки (1 ≤ x₀ ≤ M, 1 ≤ y₀ ≤ N). Числа в каждой строке разделены пробелом. Затем программа-решение начинает взаимодействие с программой, моделирующей поведение лошади, в соответствии со следующим протоколом:

1. Программа выводит в стандартный поток вывода одну строку, описывающую ход Ёжика, которая содержит три числа: его перемещение в виде указания смещения по горизонтали dx (dx = –1, 0 или 1) и по вертикали dy (dy = –1, 0 или 1), а также число 1, если Ёжик зовет Лошадь в клетке, в которую он при этом попадет, или 0 – если не зовет. Вывод должен завершаться переводом строки и сбросом буфера потока вывода. Для этого используйте

flush(output) в паскале или Delphi;
fflush(stdout) или cout.flush() в С/C++;
Console.out.flush() в Visual Basic.

2. После этого программа должна считать из стандартного потока ввода ответ программы, сообщающей о действии Лошади. Ответ состоит из трех чисел, расположенных в одной строке через пробел. Первое число ответа может быть равно 0 или 1, где

0 означает, что Ёжик не пытался позвать Лошадь либо позвал, но Лошади в его клетке нет. В этом случае следующие два числа обозначают очередное смещение Лошади по горизонтали dx (dx = –1, 0 или 1) и по вертикали dy (dy = –1, 0 или 1), при этом хотя бы одно из значений dx или dy равно нулю;
1 означает, что Ёжик позвал Лошадь, и она действительно оказалась в той же клетке, что и он. В этом случае другие два числа равны 0, и программа-решение должна закончить свою работу.
Программа-решение не должна делать более 10 000 ходов.

Пример взаимодействия

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

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


0 0 1
1 -1 0
1 0 1

Примечание

Ёжик находился в клетке (1, 2). Сначала он попробовал позвать Лошадь в той же клетке (вывод: 0 0 1), но Лошади там не оказалось, и она сместилась вправо (ввод: 0 1 0). Ёжик сместился по диагонали, но Лошадь звать не стал (вывод: 1 –1 0), а Лошадь осталась на месте (ввод: 0 0 0). Ежик сместился вправо и позвал Лошадь (вывод: 1 0 1). Лошадь оказалась в той же клетке и отозвалась (ввод: 1 0 0). Значит, изначально Лошадь находилась в клетке (2, 1), а встретились они в клетке (3, 1). Ёжик при этом сделал три хода и дважды запросил местоположение Лошади.

В данной задаче две подзадачи. Каждый тест в обеих подзадачах оценивается отдельно. Оценка за тест вычисляется по формуле min{10, round(10 × (J / S)²)}, где 10 – оценка в баллах за тест, S – количество ходов, которое потребовалось программе-решению, чтобы обнаружить Лошадь, J – количество ходов, которое требуется заданному эталонному решению при том же начальном положении Ёжика. Округление ведется по правилам математики.

(оценивается в 40 баллов) 2 ≤ N, M ≤ 10.
(оценивается в 60 баллов) 2 ≤ N, M ≤ 30. В этой подзадаче количество запросов о том, есть ли Лошадь в текущей клетке, не должно превышать N × M.