Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2719

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2719

How Many Trips Will Noel Make?

 

By Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

It's almost all ready! The gifts are wrapped, the routes are traced, the reindeer are fed and Noel is happy. It's nearly the time to leave, and Noel must deliver N gifts this Christmas.

The only problem is that all of these gifts may be too heavy to be loaded on a single trip.

To solve this problem, Noel stipulated the maximum weight that the sum of the gifts' weight can have on each trip, and now he wants to find out how many trips he will have to make.

Given the number of gifts, the maximum allowed weight for each trip, and the weight of the gifts, find out how many trips it will take to deliver all the gifts. Notice that the gifts must be delivered on the same order they are given on the input description.

 

Input

 

There will be T test cases.

Each test case starts with two integers N and M, indicating how many gifts must be delivered and what is the maximum weight allowed for each trip, respectively (1 <= N <= 10*, or 1 <= N <= 10000**, 1 <= M <= 1000).

Following there will be N integers pi, each representing the weight of a gift (1 <= pi <= M, for every 1 <= i <= N).

* Will happen in approximately 90% of the test cases.
** Will happen in approximately 10% of the test cases.

 

Output

 

For each test case print one row, containing one integer K, representing the amount of trips Noel will have to make.

 

 

 

Input Sample Output Sample

2
3 10
3 3 3
3 10
5 6 4

1
2

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>

#define true 1
#define false 0

typedef unsigned short us;

int main (void)
{

    int t, n, m, i;

    scanf("%d", &t);

    while (t--)
    {

        scanf("%d %d", &n, &m);

        us viagens = 1;
        us peso, soma = 0;
        for (i = 0; i  <  n; ++i)
        {

            scanf("%hd", &peso);
            soma += peso;
            if (soma > m)
                ++viagens, soma = peso;

        }

        printf("%d\n", viagens);

    }

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2
3 10
3 3 3
3 10
5 6 4

Output

x
+
cmd
1
2
Advertisements

Demonstration


Previous
#2718 Beecrowd Online Judge Solution 2718 Christmas Lights Solution in C, C++, Java, Js and Python
Next
#2721 Beecrowd Online Judge Solution 2721 Indecision of Reindeers Solution in C, C++, Java, Js and Python