一本道に信号が一つある。 時刻は 0, 1, 2, … のように秒単位の整数である。 信号は時刻 0 から青 G 秒、赤 R 秒を順に繰り返す。 つまり時刻 t を G + R で割った余りが G より小さければ青、そうでなければ赤である。 車が n 台あり、i 番の車は時刻 aᵢ に信号の前に来て列の最後に並ぶ。 到着時刻は a₁ ≤ a₂ ≤ … ≤ aₙ で、同じ時刻に来た車は番号の小さい車が前に並ぶ。 青の時刻ごとに列の先頭の車一台だけが信号を通り、赤の時刻には誰も通れない。 列が空なら、到着したその時刻に通ることもできる。 一行目に、車ごとに通った時刻を番号順に空白区切りで出力せよ。 二行目に、いちばん長く待った車の番号と待った時間（通った時刻 − 到着時刻）を空白区切りで出力せよ。 いちばん長く待った車が複数あるなら、番号がいちばん小さい車を出力する。 一行目に n、G、R、二行目に a₁ … aₙ が空白区切りで与えられる。
入力
1 ≤ n ≤ 5,000、1 ≤ G, R ≤ 10⁹、0 ≤ a₁ ≤ … ≤ aₙ ≤ 10⁹
出力
二行。 一行目は通った時刻 n 個、二行目は車の番号と待った時間
例 1 · stdin
6 3 2
0 0 1 4 4 9
stdout
0 1 2 5 6 10
5 2
例 2 · stdin
1 1 1000000000
1
stdout
1000000001
1 1000000000
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
一秒ずつ時計を進めてまねると、赤が 10 億秒のとき何兆回も回すことになります。 車は並んだ順にしか通らないので、車ごとに「通れるいちばん早い時刻」を直接求めます：到着時刻と前の車が通った時刻 + 1 のうち遅いほうを t とし、m = t % (G + R) が G 以上（赤）なら t に (G + R) − m を足して次の周期の始めへ飛びます。 罠は四つ：① 余りがちょうど G の時刻はもう赤です — m > G で聞くとその一秒を青とみなします。 ② 前の車と同じ秒には通れないので prev + 1 です（prev だと一秒に二台）。 ③ 周期 G + R は 2×10⁹ までで int（約 21 億）に入らず、通った時刻は 5×10¹² まで行きます — Java・C#・C・C++ は long/long long で受けます。 Python はあふれず、JavaScript・TypeScript・Craykon は数が double なので 2^53 以内なら正確です。 ④ いちばん長く待った車が複数なら前の番号なので > で比べます（>= だと後ろの車）。 余りの % は八つの言語すべてで同じ記号で、ここでは負の数がないので言語ごとに違う負の余りの規則も気にしなくて大丈夫です。 Craykon は二つの値を一行に書くとき (best + 1) + " " + … のように文字列でつなぎます。
Pythonmain.py · 20 行
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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
첫줄 = コンソール.数読み();n = 첫줄[0];g = 첫줄[1];r = 첫줄[2];a = コンソール.数読み();period = g + r;passed = [];// 앞 차가 지나간 시각(아직 없으면 -1)prev = -1;それぞれ (arrive の中 a){ // 도착한 뒤, 그리고 앞 차가 지나간 다음 초부터 t = 数学.大きい方(arrive, prev + 1); m = t % period; もし (m >= g) { // 빨강이면 다음 주기의 처음까지 기다린다 t += period - m; } passed.追加(t); prev = t;}// 가장 오래 기다린 차의 자리(같으면 앞 번호)best = 0;繰り返す (i = 0; i < n; i++){ もし (passed[i] - a[i] > passed[best] - a[best]) { best = i; }}コンソール.書く(passed);コンソール.書く(best + 1 + " " + (passed[best] - a[best]));