まっすぐな散歩道を数直線と見て、数直線のすべての整数の位置に目印の石が一つずつ置いてある。 散歩道のわきに街灯が n 本立っている。 街灯ごとに、散歩道の上でその街灯にいちばん近い点の位置 x、街灯から散歩道までの距離 d、光が届く距離 r が与えられる。 位置 p の石とこの街灯の間の距離は (p - x)² + d² の平方根である。 この距離が r 以下なら、その石はこの街灯の光を受ける。 街灯ごとに、その街灯の光を受ける石のうちいちばん小さい位置といちばん大きい位置を求める。 また、一本の街灯の光を受ける石の数を街灯ごとに数えたとき、その中でいちばん大きい値を求める。
入力
1 行目に街灯の数 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 である。
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()、Craykon の 数学.平方根() は実数の平方根で、負の数を入れるとエラーなしで NaN を返します。 実数の平方根は切り捨てて整数にしたあと、s * s が超えないことと (s + 1) * (s + 1) が超えることを整数でもう一度確かめておくと、誤差の心配がなくなります。 罠その一: 負の数の平方根です。 例 1 の三本目の街灯は d = 6、r = 5 なので r² - d² が -11 で、光が散歩道に届きません。 先に分けておかないと Python は ValueError で止まります。 罠その二: NaN を整数に変えることです。 Java では (long) Math.sqrt(-11) がエラーなしで 0 になります。 そのため 3 行目が - ではなく -7 -7 になります。 C・C++ で NaN を整数に変えるのは未定義の動作です。 罠その三: そのまま出力される NaN です。 JavaScript は 3 行目に 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 と Craykon の数は 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);}コンソール.書く(최대);