ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2011

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Старенькая Nokia

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
У Миши есть старенькая Nokia и много друзей. Так много, что Мише постоянно приходится тратить кучу времени на поиск нужного номера.
Имена друзей в телефонном справочнике упорядочены по алфавиту. От текущего имени в списке можно перейти к следующему с помощью кнопки «вниз», а к предыдущему — с помощью кнопки «вверх». Кроме того, список зациклен, то есть нажатие кнопки «вверх» для самого первого имени в справочнике переводит на последнее имя в нём, а нажатие кнопки «вниз» для последнего имени переводит на первое имя.
Когда Миша открывает справочник, в нём видны имена всех друзей, а текущим является первое по алфавиту имя. Если начать набирать некоторое слово на клавиатуре телефона, то в справочнике будут отображаться только имена, начинающиеся на уже введённую последовательность букв. Текущим в этом случае также станет имя, идущее раньше остальных в алфавитном порядке. Если после этого стереть последнюю введённую букву, позиция в справочнике не изменится, а доступными станут все имена, начинающиеся на более короткую строку. Если стереть все буквы, то доступными станут все записи в справочнике, а текущее имя не изменится. Если после некоторого нажатия должна появиться последовательность букв, на которую не начинается ни одно имя, то телефон издаст неприятный звук и последняя введённая буква не появится на экране.
На одно нажатие кнопки у Миши уходит ровно одна секунда. Первая буква на кнопке набирается за одно нажатие, вторая за два и т.д. Клавиатура телефона выглядит так:
abcdef
ghijklmno
pqrstuvwxyz
Дан список имён друзей Миши. Для каждого имени вычислите минимальное время, за которое Миша сможет выбрать это имя в списке.

Исходные данные

В первой строке дано целое число n — количество записей в телефонном справочнике Миши (1 ≤ n ≤ 105). Далее в n строках записано по одному непустому слову из строчных латинских букв. Слова перечислены в алфавитном порядке. Все записи в справочнике различны. Суммарная длина всех слов не превосходит 105.

Результат

Выведите n чисел через пробел. i-е число должно равняться минимальному времени нахождения i-го имени в справочнике.

Пример

исходные данныерезультат
5
a
aaa
aab
b
d
0 1 2 2 1
Автор задачи: Михаил Рубинчик
Источник задачи: Уральская региональная командная олимпиада по программированию 2011
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1882. Старенькая Nokia