Easy splitting

Points: 100 (partial)
Time limit: 1.0s
Python 3 5.0s
Memory limit: 256M

Authors:
Problem type

For future Arena rounds we're discussing the possibility to add solutions hacking to contests : each contestant will be assigned to exactly one room where they can see solutions of every other contestant in that room, the sum of ratings of contestants in a room cannot exceed $$M$$.

We want you to write the algorithm that distributes contestants to rooms : You will given a list of $$n$$ positive integers $$a_1,...,a_n$$ denoting the ratings of contestants, arranged in a circle ($$a_n$$ is adjacent to $$a_1$$), and a positive integer $$M$$.

You want to split the integers into contiguous lists such that each $$a_i$$ belongs to exactly one list and the sum of elements of each list is at most $$M$$. Your task is to find the minimum number of such lists in a splitting.

Note that you cannot change the order of elements $$a_i$$.

Input Specification

The first line contains $$2$$ integers $$n,M$$ ($$2\leq n\leq 10^6$$, $$1\leq M\leq 10^{18}$$)

The next line contains $$N$$ space separated integers $$a_1,...,a_n$$ ($$1\leq a_i\leq M$$)

Output Specification

Print one integer - the minimum number of lists in a valid splitting.

Scoring

• (3 point) $$a_i=1$$.
• (6 points) $$1\leq n\leq 1000$$.
• (6 points) $$M=n$$ and $$a_1,...,a_n$$ is a permutation of $$1,...n$$.
• (8 points) $$a_{i+1}\leq a_i$$ for $$1\leq i\leq n-1$$.
• (7 points) No additional constraints.

4 10
5 3 4 5

Sample Output

2

No. I think that it means you can't swap two different elements $$a_i$$ and $$a_j$$, in other words you can't change the ordre of the cycle $$(a_1,...,a_n)$$, but you can start it from any element since an $$n$$-cycle may have $$n$$ representations $$((a_1,...,a_n) = (a_2,...,a_n,a_1) = (a_n,a_1,...,a_{n-1}) )$$