Решение задачи "Аппарат Констанции" с Codeforces

Без пояснения   Просмотров: 43


Констанция — самая умная девушка в своей деревне, но вот зрением она не блещет.

Однажды она изобрела невероятный аппарат! Когда вы произносите букву, аппарат записывает ее на лист бумаги. Например, если вы произнесете буквы 'c', 'o', 'd' и 'e' в таком порядке, то аппарат запишет «code» на бумаге. Благодаря этому изобретению, она наконец-то может писать письма, не надевая очки.

Однако ее глупый друг Акко решил над ней подшутить. Акко испортил аппарат так, что если произнести 'w', то будет записано «uu» вместо «w», и если произнести 'm', то будет записано «nn» вместо «m». Так как зрение у Констанции довольно плохое, она не заметила, что Акко сделал.

Остальные буквы работают так же, как и прежде — если произнести любую букву, кроме 'w' и 'm', то аппарат просто запишет ее на бумаге.

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

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

Так как данное число могло получиться довольно большим, сообщи мне остаток от его деления на 109+7.

Если не существует ни одной такой строки, что аппарат Констанции мог превратить их в полученное мной сообщение, то выведите 0.

Код

#include<bits/stdc++.h>
using namespace std;

int L[MAX];
int main(){
	string s;
	cin >> s;
	int n = s.size();
	L[0] = L[1] = 1;
	for(int i = 0;i < n; i++){
		L[i + 1] = L[i];
		if(s[i] == 'm' || s[i] == 'w'){
			cout << 0;
			return 0;
		}
		if( (s[i] == 'n' && s[i - 1] == 'n') || (s[i] == 'u' && s[i - 1] == 'u')){
			L[i + 1] = (L[i] + L[i - 1]) % mod;
		}
	}
	cout << L[n];
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться