A-series#13033

A-series (Editorial)

Author:

Lucian Bicsi

Solved by:

First to solve:

KhNURE_Lacrimosa

Let's look at the smallest size, . What if b_N < a_N? Clearly, the condition on the number of pieces of size is satisfied, and there is no need to cut any A(N-1) piece to obtain additional s. As we can't transform smaller pieces into larger ones, we can just forget about size .

What if b_N>a_N? It means that we have to cut piece A(N-1) at least need = \lceil \frac{b_N-a_N}{2} \rceil times. And, similarly to the first paragraph, it's meaningless to make more such cuts.

So we have to add to the answer and subtract from a_{N-1}, denoting that we cut of those (even if a_{N-1} becomes negative), and forget about size after that.

Let's continue doing this. For each from N-1 to , find how many cuts of piece do we need to make to get enough A(i+1) pieces, add it to the answer, and adjust the number of pieces of paper accordingly.

In the end, we will have to consider only the pieces of size . If a_0 will be at least as big as b_0, output the answer we were summing up. Otherwise, output .