Dhaka Regional ACM ICPC 2016 Mock Contest Solution B - Bus Stopage

B. Bus Stopage

Score: 1

CPU: 1s
Memory: 1200MB

Bus service of Dhaka is life saving for many people. It’s the cheapest way of travel among the city, and it’s even cheaper for the students due to half fare. So many students ride the bus to go to their institutions (schools, colleges or universities).
Government of Bangladesh wants this to be even cheaper for the students. That’s why they are starting a special bus service for school students. This bus service will start from the start of the city and will go to the end (I know it seems weird, but try to imaging Dhaka as a linear city). There are N stoppages among this route and in every stoppage few gets on the bus and few people gets off. This number is always fixed because students don’t change home or school that often. Now the authority has one problem and that is determining the size of the bus. The bus should be as big as that it can accommodate the students at every stoppage. Let’s see an example. Suppose there are 4 stoppages. In first stoppage 5 people gets on the bus. In the second stoppage 4 people gets on and 2 gets off. So when leaving the second stoppage there are in total 7 people in the bus. In the third stoppage 3 people gets on and 4 gets off. So while leaving the third stoppage there are 6 people in the bus and the bus reaches to fourth and final stoppage with these 6 people. So the bus size must be 7 or higher because otherwise it won’t be able to accommodate all the students from the second stoppage.
Given the information about the stoppages, you need to find the minimum size of the bus that’s needed to accommodate all the students.

Input

Input will start with an integer, T, the number test cases. Each case will start with N (2<=N<=20000). Next there will be N-1 lines each with two integers A and B (0<=A,B<=20000), where in the ith line A is the number of people gets on bus and B is the number of people gets off at ith stoppage.

Output

Output a line for each case, “Case T: Size” where T is the case number and Size is the minimum required size of the bus.

Sample

InputOutput
2 4 5 0 4 2 3 4 2 4 0 Case 1: 7 Case 2: 4

















Comments

Post a Comment

Popular posts from this blog

Solution - Codeforces Problem 327B - Hungry Sequence

B. Hungry Sequence Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food. Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of  n  integers. A sequence  a 1 ,  a 2 , ...,  a n , consisting of  n  integers, is  Hungry  if and only if: Its elements are in increasing order. That is an inequality  a i  <  a j  holds for any two indices  i ,  j   ( i  <  j ) . For any two indices  i  and  j   ( i  <  j ) ,  a j  must  not  be divisible by  a i . Iahub is in trouble, so he asks you for help. Find a Hungry sequence with  n  elements. Input The input contains a single integer:  n  ( 1 ≤  n  ≤ 10 5 ). Output Output a line that contains  n  space-separated integers  a 1   a 2 , ...,  a n   (1 ≤  a i  ≤ 10 7 ) , representing a ...
Read more...

Solution - Timus Problem 1293. Eniya

1293. Eniya Time limit: 1.0 second Memory limit: 64 MB It’s restless now on the slips of the intergalactic port’s sixth dock of planet of Torn. No longer then in a month the reconstruction of the small ironclad corvette “Eniya” will be finished. And again this battle ship and its brave team would have to struggle for the control over plutonium mines of Sibelius. The work cannot be stopped even for a second, self-powered laser welders work round the clock. Joints of robots-repairers fuse because of this permanent work. Nevertheless, they can’t stop not for a single moment. Now in all this turmoil it is discovered that corvette’s thermopanels again need an urgent processing with thorium sulphide. It is known that the processing of the one square meter of the panel needs 1 nanogramm of sulphide. In general, it is needed to process  N  rectangular panels, which dimensions are  A  by  B  meters. It is necessary to calculate as fast as possible, how m...
Read more...

Solution - Timus Problem 1409. Two Gangsters

1409. Two Gangsters Time limit: 1.0 second Memory limit: 64 MB Two gangsters Harry and Larry had a rest at countryside. They decided to spend some time shooting, so they put several beer cans (no more than 10) on a log. Harry started to shoot cans one after another from the leftmost to the right and Larry – from the rightmost to the left. At some moment it happened so that they shot one and the same can. Harry got indignant and claimed that Larry owed him a considerable sum of money because Larry deprived him of shooting some more cans. Larry became furious and told Harry that he owed even greater sum of money to Larry because of the same reason. They started to argufy but nobody remembered how many cans there were at the very beginning. And no one of them was going to search cans which was shot. Anyway, each of them remembered exactly how many cans he shot. Determine how many cans were not shot by Harry and how many cans were not shot by Larry. Input The only inp...
Read more...