191. Prize Strings.md

191. Prize Strings

Question

A particular school offers cash rewards to children with good attendance and punctuality. If they are absent for three consecutive days or late on more than one occasion then they forfeit their prize. During an n-day period a trinary string is formed for each child consisting of L's (late), O's (on time), and A's (absent). How many "prize" strings exist over a 30-day period?

Solution

This is a relatively quick one. Proud of myself. xD

The prize exists if there are not more than two consecutive absent days and 0 or 1 L late days.

1. L = 0

Strings only contain any-length O (on-time days), A (one absent day) and AA (two consecutive absent days)

String Length N	Number of Strings Ended with A	Number of Strings Ended with AA	Number of Strings Ended with O	Total Number of Strings f(N)
1	1	0	1	2
2	1	1	2	4
3	2	1	4	7
4	4	2	7	13
...	...	...	...	...
N	x	y	z	x + y + z
N+1	z	x	x + y + z	2x + y + 2z

2. L = 1

The one and only late day can be the 1st or 2nd or n-th day. If the late day is the (i+1)-th day, i.e. s[i] == 'L', then the total number of strings is f(i) * f(N - i - 1)

def p191(N = 30):
    f = {0: 1}
    n, x, y, z = 1, 1, 0, 1
    for n in range(1, N + 1):
        f[n] = x + y + z
        x, y, z = z, x, x + y + z
    return f[N] + sum(f[i] * f[N - i - 1] for i in range(N))