Editorial for UTS Open '15 #3 - Pogo
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Just output .
This one's tricky:
Base cases are all except that
. The answer to the problem is
.
A diagram would be useful here but I am too lazy to draw one, so I will describe in words what each function represents:
is the number of ways to satisfy the conditions if you're at the beginning of a line of length
, with every tile behind you already visited.
is similar, but exactly one tile right behind you is unvisited.
is similar, but exactly two tiles right behind you are unvisited.
is similar, but in addition to those two tiles, there might be another group of two tiles behind them, and another two, and another two, etc. Also, there might be a group of one tile at the end of that whole chain.
is similar to
, but you can choose whether to start at the first tile or the second.
Complexity:
Comments