There is one traffic light on a single-lane road. Time is measured in whole seconds 0, 1, 2, ….
Starting at time 0, the light repeats G seconds of green followed by R seconds of red.
That is, time t is green if the remainder of t divided by G + R is less than G, and red otherwise.
There are n cars, and car i reaches the light at time aᵢ and joins the end of the line.
Arrival times satisfy a₁ ≤ a₂ ≤ … ≤ aₙ, and cars arriving at the same time line up with the smaller number in front.
At each green time exactly one car, the one at the front of the line, passes the light; at red times no one passes.
If the line is empty, a car may pass at the very time it arrives.
On the first line, print the time each car passes, in car-number order, separated by spaces.
On the second line, print the number of the car that waited longest and its waiting time (pass time − arrival time), separated by a space.
If several cars waited longest, print the one with the smallest number.
The first line gives n, G and R, and the second line gives a₁ … aₙ, separated by spaces.
Input
1 ≤ n ≤ 5,000, 1 ≤ G, R ≤ 10⁹, 0 ≤ a₁ ≤ … ≤ aₙ ≤ 10⁹
Output
Two lines: the n pass times, then a car number and its waiting time
Example 1 · stdin
6 3 2
0 0 1 4 4 9
stdout
0 1 2 5 6 10
5 2
Example 2 · stdin
1 1 1000000000
1
stdout
1000000001
1 1000000000
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Ticking the clock one second at a time takes trillions of steps when red lasts a billion seconds. Cars pass only in line order, so compute each car's 'earliest possible pass time' directly: take t as the later of its arrival time and the previous car's pass time + 1, and if m = t % (G + R) is at least G (red), add (G + R) − m to jump to the start of the next cycle. Four traps: (1) the time where the remainder is exactly G is already red — asking m > G counts that second as green. (2) A car cannot pass in the same second as the car ahead, hence prev + 1 (with prev, two cars pass in one second). (3) The cycle G + R reaches 2×10⁹, which does not fit in int (about 2.1 billion), and pass times reach 5×10¹² — Java, C#, C and C++ read them as long/long long. Python does not overflow, and JavaScript, TypeScript and Craykon use doubles, exact below 2^53. (4) Ties for the longest wait go to the smaller number, so compare with > (>= picks the later car). The remainder % is the same symbol in all eight languages, and since no number here is negative, the languages' different rules for negative remainders do not matter. Craykon writes two values on one line by joining strings, as in (best + 1) + " " + ….
Pythonmain.py · 20 lines
n, g, r = map(int, input().split())a = list(map(int, input().split()))period = g + rpassed = []prev = -1 # 앞 차가 지나간 시각(아직 없으면 -1)for arrive in a: t = max(arrive, prev + 1) # 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 m = t % period if m >= g: # 빨강이면 다음 초록(다음 주기의 처음)까지 기다린다 t += period - m passed.append(t) prev = tbest = 0 # 가장 오래 기다린 차의 자리(같으면 앞 번호)for i in range(n): if passed[i] - a[i] > passed[best] - a[best]: best = iprint(" ".join(map(str, passed)))print(best + 1, passed[best] - a[best])
JavaScriptmain.js · 19 lines
const [n, g, r, ...a] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const period = g + r;const passed = [];let prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1)for (const arrive of a) { let t = Math.max(arrive, prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 const m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed.push(t); prev = t;}let best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호)for (let i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i;}console.log(passed.join(" "));console.log(`${best + 1} ${passed[best] - a[best]}`);
TypeScriptmain.ts · 21 lines
import { readFileSync } from "node:fs";const [n, g, r, ...a]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const period = g + r;const passed: number[] = [];let prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1)for (const arrive of a) { let t = Math.max(arrive, prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 const m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed.push(t); prev = t;}let best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호)for (let i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i;}console.log(passed.join(" "));console.log(`${best + 1} ${passed[best] - a[best]}`);
JavaMain.java · 38 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); long g = Long.parseLong(st.nextToken()); long r = Long.parseLong(st.nextToken()); long period = g + r; // 2×10⁹까지라 int를 넘는다 long[] a = new long[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); long[] passed = new long[n]; long prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1) for (int i = 0; i < n; i++) { long t = Math.max(a[i], prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 long m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed[i] = t; prev = t; } int best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호) StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i; if (i > 0) out.append(' '); out.append(passed[i]); } out.append('\n').append(best + 1).append(' ').append(passed[best] - a[best]); System.out.println(out); }}
C#Main.cs · 33 lines
using System;using System.Linq;class Program{ static void Main() { long[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); int n = (int)first[0]; long g = first[1], r = first[2]; long period = g + r; // 2×10⁹까지라 int를 넘는다 long[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray(); long[] passed = new long[n]; long prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1) for (int i = 0; i < n; i++) { long t = Math.Max(a[i], prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 long m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed[i] = t; prev = t; } int best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호) for (int i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i; } Console.WriteLine(string.Join(" ", passed)); Console.WriteLine($"{best + 1} {passed[best] - a[best]}"); }}
C++main.cpp · 28 lines
#include <algorithm>#include <iostream>#include <vector>int main() { int n; long long g, r; std::cin >> n >> g >> r; const long long period = g + r; // 2×10⁹까지라 int를 넘는다 std::vector<long long> a(n), passed(n); for (long long& x : a) std::cin >> x; long long prev = -1; // 앞 차가 지나간 시각(아직 없으면 -1) for (int i = 0; i < n; i++) { long long t = std::max(a[i], prev + 1); // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 long long m = t % period; if (m >= g) t += period - m; // 빨강이면 다음 주기의 처음까지 기다린다 passed[i] = t; prev = t; } int best = 0; // 가장 오래 기다린 차의 자리(같으면 앞 번호) for (int i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i; std::cout << (i ? " " : "") << passed[i]; } std::cout << "\n" << best + 1 << " " << passed[best] - a[best] << "\n";}
Cmain.c · 28 lines
#include <stdio.h>static long long a[5000], passed[5000];int main(void) { int n; long long g, r; scanf("%d %lld %lld", &n, &g, &r); long long period = g + r; /* 2×10⁹까지라 int를 넘는다 */ for (int i = 0; i < n; i++) scanf("%lld", &a[i]); long long prev = -1; /* 앞 차가 지나간 시각(아직 없으면 -1) */ for (int i = 0; i < n; i++) { long long t = a[i] > prev + 1 ? a[i] : prev + 1; /* 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 */ long long m = t % period; if (m >= g) t += period - m; /* 빨강이면 다음 주기의 처음까지 기다린다 */ passed[i] = t; prev = t; } int best = 0; /* 가장 오래 기다린 차의 자리(같으면 앞 번호) */ for (int i = 0; i < n; i++) { if (passed[i] - a[i] > passed[best] - a[best]) best = i; printf(i ? " %lld" : "%lld", passed[i]); } printf("\n%d %lld\n", best + 1, passed[best] - a[best]); return 0;}
Craykonmain.cray · 35 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];g = 첫줄[1];r = 첫줄[2];a = Console.ReadNumbers();period = g + r;passed = [];// 앞 차가 지나간 시각(아직 없으면 -1)prev = -1;foreach (arrive in a){ // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 t = Mathf.Max(arrive, prev + 1); m = t % period; if (m >= g) { // 빨강이면 다음 주기의 처음까지 기다린다 t += period - m; } passed.Add(t); prev = t;}// 가장 오래 기다린 차의 자리(같으면 앞 번호)best = 0;for (i = 0; i < n; i++){ if (passed[i] - a[i] > passed[best] - a[best]) { best = i; }}Console.WriteLine(passed);Console.WriteLine(best + 1 + " " + (passed[best] - a[best]));