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 
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 |
1 |
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);
}
}
Input
3 10
3 3 3
3 10
5 6 4
Output
2