eolymp
bolt
Try our new interface for solving problems
Məsələlər

Мудрецы

Мудрецы

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Каждый вечер M колпаков раскрашиваются в один из K разных цветов. Таким образом M_i колпаков раскрашены в i-й цвет (i = 1..K). Мудрецам эти данные известны. Пока мудрецы спят, каждому из них на голову цепляют один из колпаков, а оставшиеся прячут. Когда мудрецы просыпаются, они садятся в круг, так чтобы каждый из них видел колпаки всех остальных, и начинают думать о цвете своего колпака. Это выглядит таким образом. Каждый мудрец пишет на листочке, знает ли он цвет своего колпака. После этого все демонстрируют свои листочки. Если кто-то написал, что знает цвет – процедура заканчивается, и все идут на завтрак. Если никто не смог определить цвет, то мудрецы начинают думать снова, операция с листочками повторяется.

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

Giriş verilənləri

Первая строка содержит целые числа N (1 N 10^6) - количество мудрецов, M (N M 10^6) - количество колпаков, и K (1 K 10^6) - количество разных цветов. Вторая строка содержит K целых чисел, каждое из которых задает количество колпаков определенного цвета. Третья строка состоит из N целых чисел, которые представляют цвета колпаков каждого из мудрецов. Цвета пронумерованы от 1 до K.

Çıxış verilənləri

Первая строка должна содержать упорядоченные по возрастанию номера мудрецов, которое первыми догадаются о цвете своего колпака. Вторая строка должна содержать одно число, которое определяет, сколько раз для этого будут продемонстрированы листочки. Если узнать об этом невозможно, то единственная строка должна содержать цифру 0 (ноль).

Пояснение: Пусть в королевстве всего три мудреца, два из которых имеют белый колпак (цвет 1) и один – черный (цвет 2). При этом еще один белый и один черный колпаки спрятаны. На первом этапе никто не сможет определить цвет своего колпака. На втором этапе каждый из владельцев белого колпака будет размышлять так: "Если б я имел черный колпак, то коллега, который имеет белый, догадался бы о цвете своего колпаку еще на первом шаге, однако этого не произошло, поэтому мой колпак белый!". А владелец черного колпака все еще не сможет определиться. Т.е., первыми догадаются мудрецы 1 и 2 с белыми колпаками и листочки для этого будут продемонстрированы два раза.

Nümunə

Giriş verilənləri #1
3 5 2
3 2
1 1 2
Çıxış verilənləri #1
1 2
2
Müəllif Andrey Stasuk
Mənbə 2007 XX All-Ukrainian Informatics Olympiad, Kremenchuk, April 10 - 16, Round 2