# Ferry Loading II

### From Progteam

Sorter: | Uncategorized |
---|---|

Source: | Waterloo local 2003.01.25 |

Link: | http://acm.pku.edu.cn/JudgeOnline/problem?id=2336 |

**Ferry Loading II** is problem number 2336 on the Peking University ACM
site.

## Algorithm

This problem uses a simple greedy algorithm to get the all the cars over. We know that we want the last ferry to be run at full capacity to ensure the minimum time possible. Therefore, the first ferry should be run with the [total cars]%[capacity] (or at capacity if [total cars]%[capacity] == 0), and every subsequent run at full capacity. We then need only to fill in the code for minor details for calculating the total time and we have an acceptable solution.

## Solution

*This is ugly contest code, please feel free to clean up the solution to make it easier to understand!*

/********************************************** * Peking 2336: Ferry Loading II * Note: this is BAD quality contest code * mfv2 - 2007-09-10 *********************************************/ import java.util.*; public class Main { static int capacity = 0; static int tripTime = 0; static int curTime = 0; static int totalCars = 0; static int[] arrivals; static int curCar = 0; static int trips = 0; static Scanner sc; public static void main(String[] args) { sc = new Scanner(System.in); int cases = sc.nextInt(); while(cases-- > 0) { curTime = 0; curCar = 0; capacity = sc.nextInt(); tripTime = sc.nextInt(); arrivals = new int[sc.nextInt()]; totalCars = arrivals.length; trips = 0; doStuff(); } } static void doStuff() { for (int i = 0; i < arrivals.length; i++) { arrivals[i] = sc.nextInt(); } //take first total%capacty cars or capacity curCar = (totalCars % capacity == 0) ? capacity : totalCars%capacity; curTime += tripTime + arrivals[curCar - 1]; trips++; if (curCar == totalCars) { System.out.println(curTime + " " + trips); return; } curTime += tripTime; //return trip is added AFTER checking if all cars moved over //take next capacity cars, repeat. while(curCar < totalCars) { curCar += capacity; if (arrivals[curCar - 1] >= curTime) { //Add time in between runs curTime += (arrivals[curCar - 1]-curTime); } curTime += tripTime; trips++; if (curCar == totalCars) { System.out.println(curTime + " " + trips); return; } curTime += tripTime; } } }