images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:44:44

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2192. Контакт

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

"Ладога" вошла в полосу густых туманов. На палубе было неинтересно, сыро, в каютах – скучно. Поэтому все кресла и диваны в кают-компании были заняты экскурсантами. Одни играли в шахматы, другие – в шашки, третьи читали. Хоттабыч, Волька и Женька играли в игру «Контакт». Правила этой игры следующие. Один игрок (ведущий) загадывает секретное слово и говорит остальным игрокам первую букву этого слова. Каждый раунд кто-то из игроков, исключая ведущего, придумывает слово, начинающееся с открытых к этому моменту букв. Количество букв в этом слове должно быть больше, чем количество открытых букв секретного слова. Игрок дает описание этого слова, не называя его. Если ведущий по описанию в течении некоторого времени угадывает это слово, то раунд проигран. Если есть другой игрок, который угадает слово по описанию, то раунд выигран, и ведущий должен сказать следующую букву в слове. Слова повторно использовать нельзя. Если угадывающий игрок дает описание для секретного слова, то игра заканчивается. Также игра заканчивается, если открыты все буквы секретного слова.
Хоттабыч, Волька и Женька используют для игры слова из некоторого словаря, но так как джинн был заперт в кувшине несколько тысяч лет, то он не все слова может угадать по их описанию. В настоящий момент Хоттабыч является ведущим. Он может взять в качестве секретного любое слово из словаря, даже незнакомое ему. Волька и Женька знают, какие слова может угадать Хоттабыч по описанию, а какие – нет, и могут это использовать для ускорения угадывания слова.
Напишите программу, которая по списку слов определяет минимальное количество раундов в худшем случае.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10000`) – количество слов. Далее следует `N` строк, каждая из которых содержит слово из строчных латинских букв длиной от 2 до 100 после которого через пробел записана одна цифра 0 или 1. Цифра 0 означает, что Хоттабыч не сможет назвать слово по его описанию, 1 – что сможет. Все слова начинаются с одной и той же буквы.
Вывести одно целое число – минимальное количество раундов игры в худшем случае.

Пример ввода

7
cheater 1
cheburashka 0
centurion 0
centaur 1
center 1
celebration 1
cell 1

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

4
loading