외길에 신호등이 하나 있다. 시각은 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()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
1초씩 시계를 돌리며 따라 하면 빨강이 10억 초일 때 몇조 번을 돌아야 해요. 차는 줄 선 차례대로만 지나가니, 차마다 '지나갈 수 있는 가장 이른 시각'을 바로 구하면 돼요: 도착 시각과 앞 차가 지나간 시각 + 1 가운데 늦은 쪽을 t로 잡고, m = t % (G + R)이 G 이상(빨강)이면 t에 (G + R) − m을 더해 다음 주기의 처음으로 건너뛰어요. 함정 넷: ① 나머지가 딱 G인 시각은 이미 빨강이에요 — m > G로 물으면 그 1초를 초록으로 쳐요. ② 앞 차와 같은 초에는 못 지나가니 prev + 1이에요(prev면 한 초에 두 대). ③ 주기 G + R은 2×10⁹까지라 int(약 21억)에 안 들어가고, 지나간 시각은 5×10¹²까지 가요 — Java·C#·C·C++는 long/long long으로 받아요. Python은 넘치지 않고, JavaScript·TypeScript·크레이콘은 수가 double이라 2^53 안이면 정확해요. ④ 가장 오래 기다린 차가 여럿이면 앞 번호라서 >로 바꿔요(>=면 뒤 차). 나머지 %는 여덟 언어 모두 같은 기호이고, 여기서는 수가 음수가 아니라서 언어마다 다른 음수 나머지 규칙도 걱정 없어요. 크레이콘은 두 값을 한 줄에 쓸 때 (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]));