ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 2018. The Debut Album

My explanation
Posted by Vladimir Putin 12 Jul 2019 04:29
I defined three functions:
C(i) - the number of ways to make the album if it consists of only i songs.
A(i) - the number of ways ending in 1.
B(i) - the number of ways ending in 2.

C(i) = A(i) + B(i)

A(i) = 1 if i <= 1
     = C(i-1) if  1< i <=a
     = C(i-1) - B(i-a-1) i>a

Notice that if i <= a there's no way to have more than a 1's, so we call C(i-1) and 'append' 1 at position i. The number of ways to do this reminds the same as C(i-1).

If i>a you could have an invalid string of 1's. To counter this, we call B(i-a-1) to know exactly how many sequences would be invalid if we 'append' a 1 at position i. When i=a+1, there's only one invalid string resulting of appending 1 at a+1, the sequence consisting of only 1's.

B is analogous to A (calls A instead of B and uses b instead of a).

Edited by author 12.07.2019 04:31