Speeding Ticket

Speeding Ticket

https://usaco.org/index.php?page=viewproblem2&cpid=568


import java.io.*;
import java.util.*;
public class SpeedingTicket {
    public static void main(String[] args) throws IOException {
        // initialize file I/O
        BufferedReader br = new BufferedReader(new FileReader("speeding.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("speeding.out")));

        // read in the first line, store n and m
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // speedLimits[K] will store the speed limit of the section of road
        // starting at mile K and ending at mile K+1.
        int[] speedLimits = new int[100];
        int currentMile = 0;

        for(int i = 0; i < n; i++) {
            // read in length and speed limit of segment i of the road
            st = new StringTokenizer(br.readLine());
            int lengthOfSegment = Integer.parseInt(st.nextToken());
            int speedLimit = Integer.parseInt(st.nextToken());
            // update the speed limit for the given segment
            for(int j = 0; j < lengthOfSegment; j++) {
                speedLimits[currentMile] = speedLimit;
                currentMile++;
            }
        }

        // travelSpeed[K] will store the speed that Bessie traveled at for
        // the section of road starting at mile K and ending at mile K+1.
        int[] travelSpeed = new int[100];
        currentMile = 0;
        for(int i = 0; i < m; i++) {
            // read in length and speed that Bessie drove
            st = new StringTokenizer(br.readLine());
            int lengthOfSegment = Integer.parseInt(st.nextToken());
            int speedLimit = Integer.parseInt(st.nextToken());
            // update the speed traveled for the given segment
            for(int j = 0; j < lengthOfSegment; j++) {
                travelSpeed[currentMile] = speedLimit;
                currentMile++;
            }
        }

        // maxOver will store the maximum amount over the speed limit that Bessie traveled.
        int maxOver = 0;
        for(int i = 0; i < 100; i++) {
            // compute the amount over the speed limit Bessie traveled
            int amountExceeded = travelSpeed[i] - speedLimits[i];
            // update maxOver if we have exceeded it
            if(amountExceeded > maxOver) {
                maxOver = amountExceeded;
            }
        }

        // print the answer!
        pw.println(maxOver);

        // close output stream
        pw.close();
        br.close();
    }
}

Algorithm Description of the Simulation

To solve this problem, we use simulation to model the road and Bessie’s journey mile by mile. Simulation helps break down the problem into smaller, manageable parts, allowing us to compare Bessie’s speed with the speed limit for every mile of the 100-mile road. Here’s how you can implement the solution step-by-step:

1. Read and Parse Input

Start by reading the input values:

  • First, note how many segments describe the road and how many segments describe Bessie’s journey.
  • For each road segment, record its length (in miles) and its speed limit.
  • For each segment of Bessie’s journey, record its length (in miles) and her driving speed.

2. Represent the Road Mile by Mile

To simulate the road and Bessie’s journey:

  1. Divide the entire 100-mile road into individual miles.
  2. Assign a speed limit to each mile based on the input road segments:
    • For example, if a segment is 40 miles long with a speed limit of 75 mph, assign 75 mph to all 40 miles in that segment.
  3. Similarly, assign Bessie’s driving speed to each mile based on her journey segments:
    • For example, if she drives 50 miles at 65 mph, assign 65 mph to all 50 miles in that segment.

This step ensures that you have a detailed view of both the speed limits and Bessie’s speeds for every single mile.

3. Compare Speeds for Each Mile

Now that you have a detailed representation of the road:

  1. For each mile (from 0 to 99), compare Bessie’s driving speed with the speed limit for that mile.
  2. Calculate how much Bessie exceeds the speed limit:

Excess Speed=Bessie s Speed−Speed LimitExcess Speed=Bessie s Speed−Speed Limit

  1. If Bessie does not exceed the speed limit for a particular mile, record zero for that mile.

4. Track Maximum Speed Violation

As you compare speeds for each mile:

  1. Keep track of the largest excess speed (if any).
  2. Update this value whenever you find a new maximum violation.

For example:

  • If at one mile Bessie is driving 5 mph over the limit and at another she is driving 7 mph over, update your maximum violation to 7.

5. Output the Result

Once you finish comparing speeds for all 100 miles:

  • The largest excess speed recorded is your answer.
  • If Bessie never exceeds the speed limit on any part of her journey, output 0.

How Simulation Solves This Problem

Simulation works by modeling the problem in small steps—in this case, mile by mile—rather than trying to solve it all at once. Here’s why simulation is effective in this problem:

  1. Breaking Down Segments: Both the road’s speed limits and Bessie’s driving speeds are given in segments of varying lengths. By simulating each mile individually, we can handle these segments easily without worrying about their varying lengths.
  2. Direct Comparisons: Once we assign values to every mile (speed limits and driving speeds), we can directly compare them without needing to process segments again.
  3. Accuracy: Simulation ensures that no part of the road or journey is overlooked because every single mile is accounted for.
  4. Flexibility: This approach can handle any number of segments and any configuration of speeds or lengths as long as they sum up to 100 miles.

By following these steps and using simulation, you can systematically determine whether Bessie exceeded the speed limit and by how much!

Type of Simulation: Static Simulation

  • The problem involves simulating the speed limits of a road and Bessie’s driving speeds across 100 miles.
  • The simulation is static because it does not involve time-dependent or iterative changes over time. Instead, it processes the data in a fixed manner by comparing the speed limit and Bessie’s speed for each mile.
  • The simulation directly calculates the maximum speed violation by iterating through a predefined set of road segments and driving segments without dynamic updates or interactions.
Scroll to Top