Проблема оказалась простой. Как обычно просмотр решений был гораздо интереснее.
Больше всего понравилось одно из решений на С++. Это было самое быстрое решение. Понравилось настолько что приведу его...
int euler_191()
{
int O,Oa,Oaa,L,La,Laa,SO,SL,Result;
O=1;
Oa=1;
L=1;
SO=2;
SL=1;
for (i=2, i<=30,i++)
{
Oaa=Oa;
Oa=O;
O=SO;
Laa=La;
La=L;
L=SL+SO;
SO=O+Oa+Oaa;
SL=L+La+Laa;
}
return SO+SL;
}
Думаю оно не очень понятно...поэтому обьяснение.
here are only 6 states in which strings can exist, divided into two groups. Three of those states are those where the strings don't contain any LATE occurence. The other three are those where the strings already contain one LATE occurence. Within each group, one state is when the string does not end with an absence, another when the string ends with only one absence, and the third when the string ends with two absences. Let's denote them as O, Oa, Oaa, L, La and Laa. Let's denote the sums of these two groups as SO and SL.
The initial states after the first day would be O=1, Oa=1 and L=1(all other states =0). The initial sums would be SO=2 and SL=1.
a) If absent on the following day, all strings in state Oa would become Oaa strings and all strings in state O would become Oa strings. Similarly, all strings in state La would become Laa strings and all strings in state L would become La strings.
b) If late on the following day, all strings in group O would become L strings.
c) If neither late nor absent on the following day, all strings in group O would become O strings (O=SO), and all strings in group L would become L strings in addition to (b) above such that L=SL+SO.
The following algo should produce the answer within 1 ms with most (if not all) programming languages. zeycus and logopetria have already posted similar algos in their own programming language.
Также понравилось рекурсивное решение.
int blah(int d, int a, bool l)
{
return d == 0 ? 1 : (blah(d - 1, 0, l) + (a >= 2 ? 0 : blah(d - 1, a + 1, l)) + (l ? 0 : blah(d - 1, 0, true)));
}