곧은 산책로를 수직선으로 보면, 수직선의 모든 정수 위치에 표지석이 하나씩 놓여 있다.
산책로 옆에 가로등 n개가 서 있다.
가로등마다 산책로에서 그 가로등과 가장 가까운 점의 위치 x, 가로등에서 산책로까지의 거리 d, 빛이 닿는 거리 r가 주어진다.
위치 p의 표지석과 이 가로등 사이의 거리는 (p - x)² + d²의 제곱근이다.
이 거리가 r 이하이면 그 표지석은 이 가로등의 빛을 받는다.
가로등마다 그 가로등의 빛을 받는 표지석 가운데 가장 작은 위치와 가장 큰 위치를 구한다.
그리고 가로등 하나의 빛을 받는 표지석 수를 가로등마다 셌을 때 그 가운데 가장 큰 값을 구한다.
입력
첫 줄에 가로등의 수 n이 주어진다(1 ≤ n ≤ 1,000).
다음 n개 줄에 가로등 하나의 정수 x, d, r가 빈칸 하나로 띄워 주어진다.
-1,000,000,000 ≤ x ≤ 1,000,000,000, 0 ≤ d ≤ 30,000,000, 1 ≤ r ≤ 30,000,000이다.
출력
처음 n개 줄에 가로등마다 주어진 순서대로, 그 가로등의 빛을 받는 표지석의 가장 작은 위치와 가장 큰 위치를 빈칸 하나로 띄워 출력한다.
빛을 받는 표지석이 하나뿐이면 그 위치를 두 번 출력한다.
빛을 받는 표지석이 없으면 그 줄에 - 하나만 출력한다.
마지막 줄에 가로등 하나의 빛을 받는 표지석 수 가운데 가장 큰 값을 출력한다.
어느 가로등도 표지석을 비추지 못하면 마지막 줄에 0을 출력한다.
수는 쉼표 없이 출력한다.
예시 1 · stdin
5
0 3 5
10 5 5
-7 6 5
2 1 2
0 60000 100000
stdout
-4 4
10 10
-
1 3
-80000 80000
160001
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
r² - d²의 제곱근을 내림한 값 s를 구하면 빛을 받는 표지석은 x - s부터 x + s까지예요. 이 제곱근을 구하는 방법과 음수를 넣었을 때 일어나는 일이 언어마다 달라요.
Python은 math.isqrt()가 정수 제곱근을 정수 계산만으로 구해요. 음수를 넣으면 ValueError로 멈추고, math.sqrt()도 음수에서 ValueError예요.
JavaScript·TypeScript의 Math.sqrt(), Java의 Math.sqrt(), C#의 Math.Sqrt(), C·C++의 sqrt(), 크레이콘의 수학.제곱근()은 실수 제곱근이고, 음수를 넣으면 오류 없이 NaN을 돌려줘요.
실수 제곱근은 내림해서 정수로 바꾼 다음, s * s가 넘지 않는지와 (s + 1) * (s + 1)이 넘는지를 정수로 한 번 더 확인해 두면 오차 걱정이 없어요.
함정 하나: 음수의 제곱근이에요. 예시 1의 셋째 가로등은 d = 6, r = 5라서 r² - d²이 -11이고, 빛이 산책로에 닿지 않아요. 먼저 가르지 않으면 Python은 ValueError로 멈춰요.
함정 둘: NaN을 정수로 바꾸기예요. Java에서 (long) Math.sqrt(-11)은 오류 없이 0이 돼요. 그래서 셋째 줄에 - 대신 -7 -7이 나와요. C·C++에서 NaN을 정수로 바꾸는 것은 정해지지 않은 동작이에요.
함정 셋: 그대로 출력되는 NaN이에요. JavaScript는 셋째 줄에 NaN NaN을 출력하고, Math.max에 NaN이 섞여 마지막 줄도 NaN이 돼요.
함정 넷: 제곱의 넘침이에요. 예시 1의 다섯째 가로등은 r = 100,000이라 r²이 10,000,000,000으로 32비트 정수를 넘어요. C#에서 int로 제곱하면 오류 없이 다른 수가 되어 -80000 80000이 아니라 -45880 45880이 나와요. Java, C, C++도 64비트 정수로 제곱해야 해요. JavaScript와 크레이콘의 수는 9,007,199,254,740,992까지 정확해서 이 문제의 제곱(최대 900,000,000,000,000)을 그대로 담아요.
함정 다섯: 딱 닿는 가로등이에요. 둘째 가로등은 d = r = 5라서 r² - d²이 0이고, 바로 앞 표지석 하나(위치 10)가 빛을 받아요. 0 이하를 어둡다고 보면 10 10 대신 -이 나와요.
함정 여섯: 반올림이에요. 넷째 가로등은 r² - d²이 3이고 제곱근은 약 1.73이에요. 내림하면 1이라 1 3이 답인데, 반올림하면 2가 되어 0 4가 나와요.
Pythonmain.py · 18 줄
import sysfrom math import isqrtlines = sys.stdin.read().split("\n")n = int(lines[0])out = []best = 0for i in range(1, n + 1): x, d, r = map(int, lines[i].split()) rest = r * r - d * d # (p - x)²이 넘지 않아야 하는 값 if rest < 0: # 음수의 제곱근은 구할 수 없다: 먼저 가른다 out.append("-") continue s = isqrt(rest) # 정수 제곱근(내림) out.append(f"{x - s} {x + s}") best = max(best, 2 * s + 1)out.append(str(best))print("\n".join(out))
JavaScriptmain.js · 20 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const out = [];let best = 0;for (let i = 1; i <= n; i++) { const [x, d, r] = lines[i].trim().split(" ").map(Number); const rest = r * r - d * d; // (p - x)²이 넘지 않아야 하는 값 if (rest < 0) { // Math.sqrt(음수)는 오류 없이 NaN이다: 먼저 가른다 out.push("-"); continue; } let s = Math.floor(Math.sqrt(rest)); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; out.push(`${x - s} ${x + s}`); best = Math.max(best, 2 * s + 1);}out.push(String(best));console.log(out.join("\n"));
TypeScriptmain.ts · 22 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const out: string[] = [];let best: number = 0;for (let i = 1; i <= n; i++) { const [x, d, r]: number[] = lines[i].trim().split(" ").map(Number); const rest: number = r * r - d * d; // (p - x)²이 넘지 않아야 하는 값 if (rest < 0) { // Math.sqrt(음수)는 오류 없이 NaN이다: 먼저 가른다 out.push("-"); continue; } let s: number = Math.floor(Math.sqrt(rest)); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; out.push(`${x - s} ${x + s}`); best = Math.max(best, 2 * s + 1);}out.push(String(best));console.log(out.join("\n"));
JavaMain.java · 31 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); long best = 0; for (int i = 0; i < n; i++) { String[] parts = br.readLine().trim().split(" "); long x = Long.parseLong(parts[0]); long d = Long.parseLong(parts[1]); long r = Long.parseLong(parts[2]); long rest = r * r - d * d; // long으로 제곱해야 넘치지 않는다 if (rest < 0) { // Math.sqrt(음수)는 NaN이고 (long) NaN은 0이다: 먼저 가른다 sb.append("-\n"); continue; } long s = (long) Math.sqrt((double) rest); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; sb.append(x - s).append(' ').append(x + s).append('\n'); best = Math.max(best, 2 * s + 1); } sb.append(best).append('\n'); System.out.print(sb); }}
C#Main.cs · 33 줄
using System;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); StringBuilder sb = new StringBuilder(); long best = 0; for (int i = 0; i < n; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); long x = long.Parse(parts[0]); long d = long.Parse(parts[1]); long r = long.Parse(parts[2]); long rest = r * r - d * d; // long으로 제곱해야 넘치지 않는다 if (rest < 0) { // Math.Sqrt(음수)는 NaN이다: 먼저 가른다 sb.Append("-\n"); continue; } long s = (long)Math.Sqrt((double)rest); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; sb.Append(x - s).Append(' ').Append(x + s).Append('\n'); best = Math.Max(best, 2 * s + 1); } sb.Append(best).Append('\n'); Console.Write(sb); }}
C++main.cpp · 29 줄
#include <algorithm>#include <cmath>#include <iostream>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; long long best = 0; for (int i = 0; i < n; i++) { long long x, d, r; cin >> x >> d >> r; long long rest = r * r - d * d; // long long으로 제곱해야 넘치지 않는다 if (rest < 0) { // sqrt(음수)는 NaN이고, NaN을 정수로 바꾸는 것은 정해지지 않은 동작이다 cout << "-\n"; continue; } long long s = static_cast<long long>(sqrt(static_cast<double>(rest))); while (s * s > rest) s--; // 실수 제곱근의 오차에 대비한 정수 확인 while ((s + 1) * (s + 1) <= rest) s++; cout << x - s << ' ' << x + s << '\n'; best = max(best, 2 * s + 1); } cout << best << '\n'; return 0;}
Cmain.c · 25 줄
#include <math.h>#include <stdio.h>int main(void) { int n; if (scanf("%d", &n) != 1) return 1; long long best = 0; for (int i = 0; i < n; i++) { long long x, d, r; if (scanf("%lld %lld %lld", &x, &d, &r) != 3) return 1; long long rest = r * r - d * d; /* long long으로 제곱해야 넘치지 않는다 */ if (rest < 0) { /* sqrt(음수)는 NaN이고, NaN을 정수로 바꾸는 것은 정해지지 않은 동작이다 */ printf("-\n"); continue; } long long s = (long long)sqrt((double)rest); while (s * s > rest) s--; /* 실수 제곱근의 오차에 대비한 정수 확인 */ while ((s + 1) * (s + 1) <= rest) s++; printf("%lld %lld\n", x - s, x + s); if (2 * s + 1 > best) best = 2 * s + 1; } printf("%lld\n", best); return 0;}
Craykonmain.cray · 28 줄
가로등수 = 콘솔.줄읽기().수로변환();최대 = 0;반복 (i = 0; i < 가로등수; i++){ 칸들 = 콘솔.줄읽기().공백제거().나누기(); 위치 = 칸들[0].수로변환(); 떨어진거리 = 칸들[1].수로변환(); 닿는거리 = 칸들[2].수로변환(); 남은 = 닿는거리 * 닿는거리 - 떨어진거리 * 떨어진거리; // (p - x)²이 넘지 않아야 하는 값 만약 (남은 < 0) { // 수학.제곱근(음수)는 오류 없이 NaN이다: 먼저 가른다 콘솔.쓰기("-"); 건너뛰기; } 반 = 수학.내림(수학.제곱근(남은)); 동안 (반 * 반 > 남은) { 반--; // 실수 제곱근의 오차에 대비한 정수 확인 } 동안 ((반 + 1) * (반 + 1) <= 남은) { 반++; } 콘솔.쓰기(위치 - 반 + " " + (위치 + 반)); 최대 = 수학.큰수(최대, 2 * 반 + 1);}콘솔.쓰기(최대);