OJ Board

Code: Select all

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class Main
{
	public static void main(String[] args) throws Exception
	{
		ArrayList<String> lines = new ArrayList<String>();
		String line = "";
		try
		{
			line = readLine(512);

		} catch (Exception e)
		{
		}
		HashMap<Double, Double> stations = new HashMap<Double, Double>();
		double tripLength = 0;
		double tankSize = 0;
		double mpg = 0;
		double priceAtHome = 0;
		int counter = 1;
		int stationCount = 0;
		while (!line.contains("-"))
		{
			if (!line.equals(""))
			{
				lines.add(line);
			}
			try
			{
				line = readLine(512);
			}
			catch (Exception e)
			{
			}
		}
		Iterator<String> it = lines.iterator();
		while (it.hasNext())
		{
			line = it.next();
			Scanner scan = new Scanner(line);
			if (entryCount(line) == 1)
			{
				//This is the first line of a block
				if (stations.size() > 0 & stations.size() == stationCount)
				{
					Double minimum = solve(tripLength, tankSize, mpg, priceAtHome, stations);
					System.out.println("Data Set #" + counter);
					if ((minimum * 100) < 10000)
					{
						System.out.println("minimum cost = $" + minimum + "0");
					}
					else
					{
						System.out.println("minimum cost = $" + minimum);
					}
					counter++;
					stations = new HashMap<Double, Double>();
					tripLength = 0;
					tankSize = 0;
					mpg = 0;
					priceAtHome = 0;
					tripLength = scan.nextDouble();
				}
				else
				{
					tripLength = scan.nextDouble();
				}
			}
			else if (entryCount(line) == 4)
			{
				//The parameters for the car
				tankSize = scan.nextDouble();
				mpg = scan.nextDouble();
				priceAtHome = scan.nextDouble();
				stationCount = scan.nextInt();
			}
			else if (entryCount(line) == 2)
			{
				double distance = scan.nextDouble();
				double price = scan.nextDouble();
				stations.put(distance, price);				
			}
		}
		Double minimum = solve(tripLength, tankSize, mpg, priceAtHome, stations);
		System.out.println("Data Set #" + counter);
		if ((minimum * 100) < 10000)
		{
			System.out.println("minimum cost = $" + minimum + "0");
		}
		else
		{
			System.out.println("minimum cost = $" + minimum);
		}
	}

	public static int entryCount(String line)
	{
		Scanner scan = new Scanner(line);
		int counter = 0;
		while(scan.hasNext())
		{
			counter++;
			scan.next();
		}
		return counter;
	}

	public static Double solve(double length, double tank, 
			double mpg, double priceAtHome, 
			HashMap<Double, Double> stations)
	{
		Double range = mpg * tank;
		if (range < length)
		{
			double distanceRemaining = length;
			double total = 0;
			double point = 0;

			while (distanceRemaining > range)
			{
				Set<Map.Entry<Double, Double>> set = stations.entrySet();
				Iterator<Map.Entry<Double, Double>> it = set.iterator();

				double minimum = 100000000;
				double distance = 0;

				while (it.hasNext())
				{
					Map.Entry<Double, Double> station = it.next();
					double cost = station.getValue() * (station.getKey() - point) / mpg;
					if (station.getKey() > point)
					{
						if (range + point >= station.getKey())
						{
							int stationsInFront = stationsInFront(stations, station.getKey());
							if ((station.getKey() - point) > (range / 2) || stationsInFront == 0)
							{
								if (cost < minimum)
								{
									if (station.getKey() >= (length - distanceRemaining))
									{
										minimum = cost;
										distance = station.getKey();
									}
								}
							}
						}

					}
				}


				minimum += 200;
				minimum = Math.ceil(minimum);
				minimum /= 100;

				distanceRemaining -= distance;
				point = distance;
				total += minimum;
			}

			return total + 20;
		}
		else
		{
			return priceAtHome;
		}
	}

	public static int stationsInFront(HashMap<Double, Double> stations, double distance)
	{
		Iterator<Map.Entry<Double, Double>> it = stations.entrySet().iterator();
		int count = 0;
		while (it.hasNext())
		{
			Map.Entry<Double, Double> station = it.next();
			if (station.getKey() > distance)
			{
				count++;
			}
		}
		return count;
	}
	static String readLine(int maxLg) throws IOException
	{
		byte[] lin = new byte[maxLg];
		int lg = 0, car = -1;
		while (lg < maxLg)
		{
			car = System.in.read();
			if (car < 0 || car == '\r' | car == '\n')
				break;
			lin[lg++] += car;
		}
		if (car < 0 && lg == 0)
			return null;
		return new String(lin, 0, lg);
	}
}