Ferry Loading II

From Progteam

Revision as of 20:11, 18 September 2007 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by Mfv2.


Ferry Loading II
Problem Number 2336
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;	
		}
	}


}
Personal tools