|
Олимпиады прошлых лет
|
||||||||||||||||||||||||||||||
|
Олимпиада проводится при поддержке Компьютерного супермаркета "НИКС" и компании Genius
Информационная поддержка:
журнал "Мир ПК"
II Всероссийская заочная олимпиада школьников по информатике, 2007/08 учебный год
Задача J. SMS
| Имя входного файла: | j.in |
| Имя выходного файла: | j.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
SMS-сообщения на мобильном телефоне марки MOBILO набираются только заглавными английскими буквами. Для набора буквы нужно нажать кнопку, на которой эта буква написана, при этом если эта буква написана первой, то кнопку нужно нажать один раз, если второй - то два раза и т.д. Устройство клавиатуры телефона приведено на рисунке.
Таким образом, чтобы набрать слово SMS, нужно нажать следующие кнопки:
<PQRS> <PQRS> <PQRS> <PQRS> <MNO> <PQRS> <PQRS> <PQRS> <PQRS>
Для набора двух букв, которые находятся на одной кнопке, при наборе нужно сделать паузу между их вводом. Например, чтобы набрать BA, нужно два раза нажать кнопку <ABC>, затем сделать паузу и затем нажать кнопку <ABC> еще раз.
Если на кнопке написано три буквы, то как только эта кнопка нажата три раза подряд, последняя из написанных на ней букв сразу же добавляется в сообщение, а дальнейшие нажатия на эту кнопку воспринимаются как ввод следующей буквы. То же самое, если на кнопке написано 4 буквы. Таким образом, 4-х кратное нажатие на кнопку <ABC>, затем пауза, и затем нажатие на эту кнопку еще раз приведет к вводу текста CAA.
К сожалению, в силу произошедшего глюка, телефон стал иногда игнорировать паузы при вводе, а, иногда, наоборот, вести себя так, как будто была пауза тогда, когда паузы не было. Например, при вводе слова MOSCOW могло в итоге (как один из вариантов) получиться слово OMSCMNW.
Вы получили SMS-сообщение, набранное на этом телефоне. Известно, что изначально оно состояло из N символов. Напишите программу, которая определит количество вариантов исходных сообщений, которые при вводе могли превратиться в то, что вы получили (если вариантов окажется 0, то это будет означать, что у телефона сломалось что-то еще).
Формат входных данных
Сначала записана длина исходного сообщения N (1≤N≤80). Вторая строка содержит полученное SMS-сообщение - последовательность не более чем из 80 заглавных латинских букв.
Формат выходных данных
Выведите одно число - количество вариантов исходного сообщения.
Примеры
| j.in | j.out |
4 MAMA |
1 |
2 WWW |
2 |
10 MAMA |
0 |