Easy splitting


Submit solution

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.

Sample Input

4 10
5 3 4 5

Sample Output

2

Comments


  • 0
    XanaX  commented on Jan. 9, 2021, 9:39 p.m.

    ahh I get stuck .. moncef can I get some help!


  • 0
    Mexudi20  commented on Dec. 13, 2020, 2:21 p.m.

    "cannot change the order of elements a" means that I cannot put the first 5 and the last 5 in the same list?


    • 0
      HamzaBamohammed  commented on Dec. 13, 2020, 5:57 p.m. edited

      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}) )\)