Problem Descriptin
source:https://uva.onlinejudge.org/external/126/12608.html
Garbage truck is collecting garbage on its route starting at the dump and collecting garbage from pick up points in order (closest first). Garbage truck returns to the dump and empties its contents if it either
Given the weight limit that truck can carry and the list of pick up points with garbage weights, what is the distance that the truck will cover following the rules above?
Input
Input starts with an integer T on the first line, the number of test cases. Each case starts with the line with two integers W and N, the weight limit and the number of pick up points, respectively.
Then N lines follow, each containing integers xi and wi , the distance from the dump and the weight of the garbage at the pick up point respectively.
Constraints are as given: 1 ≤ W ≤ 1000, 1 ≤ N ≤ 1000, 0 < xi ≤ 100, 000, 1 ≤ wi ≤ W. Distances are distinct and given in order, i.e. for each i < j, xi < xj .
Output
For each test case output an integer on a line — the distance covered by the garbage truck.
Sample Input
3
2 2
1 1
2 2
6 3
1 1
2 2
3 3
3 3
1 2
2 2
3 1
Sample Output
8
6
10
Solution:
source:https://uva.onlinejudge.org/external/126/12608.html
Garbage truck is collecting garbage on its route starting at the dump and collecting garbage from pick up points in order (closest first). Garbage truck returns to the dump and empties its contents if it either
- is full or
- cannnot load the garbage at the current point because it will put the load over the weight limit (the truck driver has no way of knowing the weight of the garbage at a particular pick up point until the truck reaches that point) or
- there are no more pick up points left
Given the weight limit that truck can carry and the list of pick up points with garbage weights, what is the distance that the truck will cover following the rules above?
Input
Input starts with an integer T on the first line, the number of test cases. Each case starts with the line with two integers W and N, the weight limit and the number of pick up points, respectively.
Then N lines follow, each containing integers xi and wi , the distance from the dump and the weight of the garbage at the pick up point respectively.
Constraints are as given: 1 ≤ W ≤ 1000, 1 ≤ N ≤ 1000, 0 < xi ≤ 100, 000, 1 ≤ wi ≤ W. Distances are distinct and given in order, i.e. for each i < j, xi < xj .
Output
For each test case output an integer on a line — the distance covered by the garbage truck.
Sample Input
3
2 2
1 1
2 2
6 3
1 1
2 2
3 3
3 3
1 2
2 2
3 1
Sample Output
8
6
10
Solution:
#include <algorithm> #include <cstdio> #include <cmath> #include<stdio.h> #include<stdlib.h> using namespace std; int main() { long long int w,n,t,i,j,di,wt,cwt,tdi; scanf("%lld",&t); for(i=1;i<=t;i++) { scanf("%lld %lld",&w,&n); cwt=0;tdi=0; for(j=1;j<=n;j++) { scanf("%lld %lld",&di,&wt); if((cwt+wt)>w) { tdi+=di; cwt=0; } if((cwt+wt)==w) { tdi+=di; cwt=0; di=0; } else cwt+=wt; } tdi+=di; printf("%lld\n",tdi*2); } return 0; }
No comments:
Post a Comment
Write your comment - Share Knowledge and Experience