2015 Dec Bronze Problem 2 Speeding Ticket

Official Problem Statement

Speeding Ticket

Problem

Farmer John has installed a new system on the road in front of his farm in order to help enforce speed limits. The system tracks the speed of drivers by taking pictures of cars as they travel along the road.

There are N (1 ≤ N ≤ 100) segments of the road, each with a known length L_i (1 ≤ L_i ≤ 100) and a legal speed limit S_i (1 ≤ S_i ≤ 100) that all drivers must obey. Bessie the cow is recorded travelling along the road; her speeds for each segment are known as B_i (1 ≤ B_i ≤ 100).

Bessie is issued a speeding ticket if she exceeds the speed limit on any segment of the road. The severity of the ticket is equal to the amount by which Bessie was driving over the speed limit at the point where she was fastest relative to the speed limit. In other words, the ticket's severity is max(B_i - S_i) over all segments where she was speeding.

Your task is to determine the severity of Bessie's speeding ticket.

Solution

To solve this problem, we need to iterate through each segment of the road and find the maximum amount that Bessie's speed exceeded the speed limit.

We first read the input data, storing the lengths and speed limits for each road segment. We then do the same for Bessie's speeds. Next, we initialize a variable to store the maximum speed over the limit that Bessie was driving.

We loop through each road segment, comparing Bessie's speed to the speed limit. If Bessie's speed exceeds the limit, we update the maximum speed over the limit if necessary.

After checking all road segments, the maximum speed over the limit is the severity of Bessie's speeding ticket. If Bessie never exceeded the speed limit, the ticket's severity is 0.

We can implement this solution in any programming language that supports basic array manipulation and arithmetic operations. The time complexity is O(N), where N is the number of road segments, as we need to examine each segment exactly once.

Code

C++

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main() {
    ifstream input("speeding.in");
    ofstream output("speeding.out");
    
    int n, m;
    input >> n >> m;
    
    vector<int> speedLimits(100, 0);
    int currentMile = 0;
    
    for (int i = 0; i < n; i++) {
        int segmentLength, speedLimit;
        input >> segmentLength >> speedLimit;
        
        for (int j = 0; j < segmentLength; j++) {
            speedLimits[currentMile++] = speedLimit;
        }
    }
    
    vector<int> bessieSpeeds(100, 0);
    currentMile = 0;
    
    for (int i = 0; i < m; i++) {
        int segmentLength, speed;
        input >> segmentLength >> speed;
        
        for (int j = 0; j < segmentLength; j++) {
            bessieSpeeds[currentMile++] = speed;
        }
    }
    
    int maxSpeedOverLimit = 0;
    for (int i = 0; i < 100; i++) {
        int exceededSpeed = bessieSpeeds[i] - speedLimits[i];
        maxSpeedOverLimit = max(maxSpeedOverLimit, exceededSpeed);
    }
    
    output << maxSpeedOverLimit << endl;
    output.close();

    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Speeding {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("speeding.in"));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("speeding.out")));
        
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());
        
        int[] speedLimits = new int[100];
        int currentMile = 0;
        
        for (int i = 0; i < n; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int segmentLength = Integer.parseInt(tokenizer.nextToken());
            int speedLimit = Integer.parseInt(tokenizer.nextToken());
            
            for (int j = 0; j < segmentLength; j++) {
                speedLimits[currentMile++] = speedLimit;
            }
        }
        
        int[] bessieSpeeds = new int[100];
        currentMile = 0;
        
        for (int i = 0; i < m; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int segmentLength = Integer.parseInt(tokenizer.nextToken());
            int speed = Integer.parseInt(tokenizer.nextToken());
            
            for (int j = 0; j < segmentLength; j++) {
                bessieSpeeds[currentMile++] = speed;
            }
        }
        
        int maxSpeedOverLimit = 0;
        for (int i = 0; i < 100; i++) {
            int exceededSpeed = bessieSpeeds[i] - speedLimits[i];
            maxSpeedOverLimit = Math.max(maxSpeedOverLimit, exceededSpeed);
        }
        
        writer.println(maxSpeedOverLimit);
        writer.close();
    }
}

Python

with open("speeding.in", "r") as input:
    n, m = map(int, input.readline().split())
    
    speed_limits = [0] * 100
    current_mile = 0
    
    for _ in range(n):
        segment_length, speed_limit = map(int, input.readline().split())
        for _ in range(segment_length):
            speed_limits[current_mile] = speed_limit
            current_mile += 1
    
    bessie_speeds = [0] * 100
    current_mile = 0
    
    for _ in range(m):
        segment_length, speed = map(int, input.readline().split())
        for _ in range(segment_length):
            bessie_speeds[current_mile] = speed
            current_mile += 1
    
    max_speed_over_limit = 0
    for i in range(100):
        exceeded_speed = bessie_speeds[i] - speed_limits[i]
        max_speed_over_limit = max(max_speed_over_limit, exceeded_speed)
    
with open("speeding.out", "w") as output:
    output.write(str(max_speed_over_limit) + "\n")