家電売り場の比較アシスタントが、二つの商品のどちらが良いかを教える。 商品は n 個で 1 番から n 番までの番号があり、商品ごとに 1 番から k 番までの k 個の欄に測定値（整数）が書かれている。 測定していない欄には数の代わりに x が書かれている。 比較の基準が r 個、重要な順に与えられる。 基準一つ "f d e" は f 番の欄を見るという意味である。 d が H なら測定値が大きいほうが良く、L なら測定値が小さいほうが良い。 e は許容誤差である。 同じ欄を見る基準が二回出ることはない。 二つの商品を比べるときは、最初の基準から順に次のように調べる。 二つの商品ともその欄が x なら、この基準では引き分けである。 片方だけが x なら、d が何であっても測定値があるほうが良い。 両方に測定値があり、二つの測定値の差（大きい数から小さい数を引いた値）が e 以下なら、この基準では引き分けである。 差が e より大きければ、d が H のときは測定値が大きいほうが、L のときは測定値が小さいほうが良い。 引き分けなら次の基準に進み、良いほうが決まったらそこで止める。 質問が q 個与えられ、質問一つ "a b" は a 番の商品と b 番の商品を比べよという意味である（a と b が同じこともある）。 質問ごとに一行に、良いほうの商品の番号と、勝負を決めた基準が何番目の基準か（最初の基準が 1）を空白一つで区切って出力せよ。 すべての基準で引き分けなら 0 だけを出力する。
入力
一行目に n、k、r、q が空白で区切られて与えられる。 次の n 行に 1 番の商品から順に k 個の欄の値（整数または x）が空白一つで区切られて与えられる。 次の r 行に基準 "f d e" が、次の q 行に質問 "a b" が一行に一つずつ与えられる。 2 ≤ n ≤ 1,000、1 ≤ k ≤ 8、1 ≤ r ≤ k、1 ≤ q ≤ 10,000、-2,000,000,000 ≤ 測定値 ≤ 2,000,000,000、1 ≤ f ≤ k、d は H または L、0 ≤ e ≤ 1,000,000,000、1 ≤ a, b ≤ n
出力
q 行。 各行は「良いほうの商品の番号、勝負を決めた基準の順番」または 0
例 1 · stdin
4 3 3 5
300 45 x
320 48 7
300 60 7
300 44 x
2 L 5
3 H 1
1 H 0
1 2
1 3
1 4
2 3
4 2
stdout
2 2
1 1
0
2 1
2 2
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
二つの値を比べた結果は「前が良い・後ろが良い・引き分け」の三つで、そこに「値がない」まで割り込みます。 だから聞く順番が大事です：① 両方ないか、② 片方だけないか、③ 差が誤差の内か、④ どちらが大きいか。 向きは (u > v) == high のように「大きいほうが u か」と「大きいほうが良いか」が同じかどうかで一度に聞けます。 落とし穴その一：測定値は ±20 億なので 32 ビットの int に入りますが、二つの値の差は 40 億まで行ってあふれます。 Java の Math.abs(u - v) と C# の int の引き算はエラーなしに一周して、でたらめな小さい数になり（20 億 −（−20 億）が −294,967,296）、C・C++ では未定義動作です。 Java・C# は long、C・C++ は long long で受けて引き、C の abs は int 用なので llabs を使います。 Python の整数には上限がなく、JS・TS・Craykon の数は 2^53 まで正確なのでそのままで大丈夫です。 落とし穴その二：「値がない」をとても小さい数で代用すると、H の基準では合いますが、L の基準（小さいほど良い）ではないほうが勝ってしまいます。 「ない」は別に持ちます：Python None、JS・TS null（TS は number | null なので、取り除く前に引くとコンパイルエラー）、C# long?、C++ std::optional<long long>、Craykon なし、Java・C は値があるかを記す配列を別に持ちます。 「ない」を取り除かずに比べると言語ごとに違います：Python の None < 5 は TypeError、Java は Long が null なら NullPointerException、Craykon は「なし（値がない）では計算できません」と止まります。 黙って通るほうが危険です：JS は null を 0 に変えて比べ（null < 5 は真）、C# の long? は片方が null なら < も > も偽で、C++ の optional は空のほうをいつも小さいとします。 落とし穴その三：境界です。 差がちょうど e のときは引き分けなので <= であって < ではありません。 落とし穴その四：JS で split で分けた文字列を数に変えないと、u - v は数に変わって計算されますが、u > v は文字の順で比べるので "10" > "9" が偽になります。 Python は文字列どうしを引くと TypeError、Craykon も「- の計算は数どうしでしかできません」と止まるのですぐ分かります。 落とし穴その五：出力するのは基準が見る欄の番号 f ではなく、その基準が何番目かです。
Pythonmain.py · 33 行
import sysdef compare(x, y, rules): """(앞선 쪽, 가른 기준의 차례)를 돌려준다. 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0.""" for j, (f, high, e) in enumerate(rules, 1): u, v = x[f], y[f] if u is None and v is None: # 둘 다 값이 없으면 이 기준은 비긴다 continue if u is None: # 값이 없는 쪽이 진다(방향과 상관없이) return -1, j if v is None: return 1, j if abs(u - v) <= e: # 차이가 허용 오차 이하이면 비긴다 continue return (1 if (u > v) == high else -1), j return 0, 0lines = sys.stdin.read().split("\n")n, k, r, q = map(int, lines[0].split())items = [[None if t == "x" else int(t) for t in line.split()] for line in lines[1 : 1 + n]]rules = []for line in lines[1 + n : 1 + n + r]: f, d, e = line.split() rules.append((int(f) - 1, d == "H", int(e)))out = []for line in lines[1 + n + r : 1 + n + r + q]: a, b = map(int, line.split()) side, j = compare(items[a - 1], items[b - 1], rules) out.append("0" if side == 0 else f"{a if side > 0 else b} {j}")print("\n".join(out))
JavaScriptmain.js · 31 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, k, r, q] = lines[0].split(" ").map(Number);// 값이 없는 칸은 null. Number("x")는 NaN이라 따로 가른다const items = lines.slice(1, 1 + n).map((line) => line.trim().split(" ").map((t) => (t === "x" ? null : Number(t))));const rules = lines.slice(1 + n, 1 + n + r).map((line) => { const [f, d, e] = line.trim().split(" "); return { f: Number(f) - 1, high: d === "H", e: Number(e) };});// [앞선 쪽, 가른 기준의 차례]: 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0function compare(x, y) { for (let j = 0; j < rules.length; j++) { const { f, high, e } = rules[j]; const u = x[f]; const v = y[f]; if (u === null && v === null) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (u === null) return [-1, j + 1]; // 값이 없는 쪽이 진다(방향과 상관없이) if (v === null) return [1, j + 1]; if (Math.abs(u - v) <= e) continue; // 차이가 허용 오차 이하이면 비긴다 return [u > v === high ? 1 : -1, j + 1]; } return [0, 0];}const out = [];for (const line of lines.slice(1 + n + r, 1 + n + r + q)) { const [a, b] = line.split(" ").map(Number); const [side, j] = compare(items[a - 1], items[b - 1]); out.push(side === 0 ? "0" : `${side > 0 ? a : b} ${j}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 41 行
import { readFileSync } from "node:fs";interface Rule { f: number; // 볼 칸(0부터) high: boolean; // 클수록 좋은가 e: number; // 허용 오차}const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, k, r, q]: number[] = lines[0].split(" ").map(Number);// 값이 없는 칸은 null. 타입이 number | null이라 null을 거르지 않고 빼면 컴파일러가 막는다const items: (number | null)[][] = lines .slice(1, 1 + n) .map((line: string) => line.trim().split(" ").map((t: string): number | null => (t === "x" ? null : Number(t))));const rules: Rule[] = lines.slice(1 + n, 1 + n + r).map((line: string): Rule => { const [f, d, e]: string[] = line.trim().split(" "); return { f: Number(f) - 1, high: d === "H", e: Number(e) };});// [앞선 쪽, 가른 기준의 차례]: 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0function compare(x: (number | null)[], y: (number | null)[]): [number, number] { for (let j = 0; j < rules.length; j++) { const { f, high, e }: Rule = rules[j]; const u: number | null = x[f]; const v: number | null = y[f]; if (u === null && v === null) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (u === null) return [-1, j + 1]; // 값이 없는 쪽이 진다(방향과 상관없이) if (v === null) return [1, j + 1]; if (Math.abs(u - v) <= e) continue; // 차이가 허용 오차 이하이면 비긴다 return [u > v === high ? 1 : -1, j + 1]; } return [0, 0];}const out: string[] = [];for (const line of lines.slice(1 + n + r, 1 + n + r + q)) { const [a, b]: number[] = line.split(" ").map(Number); const [side, j]: [number, number] = compare(items[a - 1], items[b - 1]); out.push(side === 0 ? "0" : `${side > 0 ? a : b} ${j}`);}console.log(out.join("\n"));
JavaMain.java · 60 行
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()); int k = Integer.parseInt(st.nextToken()); int r = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[][] value = new long[n][k]; // 두 값의 차이가 40억까지라 long boolean[][] has = new boolean[n][k]; // 값이 있는 칸인가("x"면 false) for (int i = 0; i < n; i++) { st = new StringTokenizer(in.readLine()); for (int c = 0; c < k; c++) { String t = st.nextToken(); has[i][c] = !t.equals("x"); if (has[i][c]) value[i][c] = Long.parseLong(t); } } int[] field = new int[r]; boolean[] high = new boolean[r]; long[] tol = new long[r]; for (int j = 0; j < r; j++) { st = new StringTokenizer(in.readLine()); field[j] = Integer.parseInt(st.nextToken()) - 1; high[j] = st.nextToken().equals("H"); tol[j] = Long.parseLong(st.nextToken()); } StringBuilder sb = new StringBuilder(); for (int t = 0; t < q; t++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int winner = 0; // 앞선 상품 번호(끝까지 비기면 0) int decided = 0; // 가른 기준의 차례 for (int j = 0; j < r && winner == 0; j++) { int f = field[j]; boolean hasA = has[a - 1][f], hasB = has[b - 1][f]; if (!hasA && !hasB) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (!hasA || !hasB) { // 값이 없는 쪽이 진다(방향과 상관없이) winner = hasA ? a : b; } else { long u = value[a - 1][f], v = value[b - 1][f]; if (Math.abs(u - v) <= tol[j]) continue; // 차이가 허용 오차 이하이면 비긴다 winner = (u > v) == high[j] ? a : b; } decided = j + 1; } if (winner == 0) sb.append("0\n"); else sb.append(winner).append(' ').append(decided).append('\n'); } System.out.print(sb); }}
C#Main.cs · 57 行
using System;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Trim().Split(' '); int n = int.Parse(head[0]), k = int.Parse(head[1]), r = int.Parse(head[2]), q = int.Parse(head[3]); // long?는 값이 없을 수 있는 long이다("x"면 null). 두 값의 차이가 40억까지라 int로는 모자란다 var items = new long?[n][]; for (int i = 0; i < n; i++) { string[] w = Console.ReadLine().Trim().Split(' '); items[i] = new long?[k]; for (int c = 0; c < k; c++) items[i][c] = w[c] == "x" ? (long?)null : long.Parse(w[c]); } var field = new int[r]; var high = new bool[r]; var tol = new long[r]; for (int j = 0; j < r; j++) { string[] w = Console.ReadLine().Trim().Split(' '); field[j] = int.Parse(w[0]) - 1; high[j] = w[1] == "H"; tol[j] = long.Parse(w[2]); } var sb = new StringBuilder(); for (int t = 0; t < q; t++) { string[] w = Console.ReadLine().Trim().Split(' '); int a = int.Parse(w[0]), b = int.Parse(w[1]); int winner = 0; // 앞선 상품 번호(끝까지 비기면 0) int decided = 0; // 가른 기준의 차례 for (int j = 0; j < r && winner == 0; j++) { long? u = items[a - 1][field[j]], v = items[b - 1][field[j]]; if (u == null && v == null) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (u == null || v == null) { winner = u != null ? a : b; // 값이 없는 쪽이 진다(방향과 상관없이) } else { if (Math.Abs(u.Value - v.Value) <= tol[j]) continue; // 차이가 허용 오차 이하이면 비긴다 winner = (u.Value > v.Value) == high[j] ? a : b; } decided = j + 1; } if (winner == 0) sb.Append("0\n"); else sb.Append(winner).Append(' ').Append(decided).Append('\n'); } Console.Write(sb.ToString()); }}
C++main.cpp · 58 行
#include <cstdlib>#include <iostream>#include <optional>#include <string>#include <vector>using namespace std;struct Rule { int f; // 볼 칸(0부터) bool high; // 클수록 좋은가 long long e; // 허용 오차};int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k, r, q; cin >> n >> k >> r >> q; // optional은 값이 없을 수 있는 칸이다("x"면 nullopt). 두 값의 차이가 40억까지라 long long vector<vector<optional<long long>>> items(n, vector<optional<long long>>(k)); for (auto& row : items) { for (auto& cell : row) { string token; cin >> token; if (token != "x") cell = stoll(token); } } vector<Rule> rules(r); for (Rule& rule : rules) { char dir; cin >> rule.f >> dir >> rule.e; rule.f--; rule.high = dir == 'H'; } while (q--) { int a, b; cin >> a >> b; int winner = 0; // 앞선 상품 번호(끝까지 비기면 0) int decided = 0; // 가른 기준의 차례 for (int j = 0; j < r && winner == 0; j++) { const optional<long long>& u = items[a - 1][rules[j].f]; const optional<long long>& v = items[b - 1][rules[j].f]; if (!u && !v) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (!u || !v) { // 값이 없는 쪽이 진다(방향과 상관없이) winner = u ? a : b; } else { if (llabs(*u - *v) <= rules[j].e) continue; // 차이가 허용 오차 이하이면 비긴다 winner = (*u > *v) == rules[j].high ? a : b; } decided = j + 1; } if (winner == 0) cout << "0\n"; else cout << winner << ' ' << decided << '\n'; } return 0;}
Cmain.c · 53 行
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 1000#define MAXK 8static long long value[MAXN][MAXK]; /* 두 값의 차이가 40억까지라 long long */static int has[MAXN][MAXK]; /* 값이 있는 칸인가("x"면 0) */static int field[MAXK], high[MAXK];static long long tol[MAXK];int main(void) { int n, k, r, q; if (scanf("%d %d %d %d", &n, &k, &r, &q) != 4) return 0; for (int i = 0; i < n; i++) { for (int c = 0; c < k; c++) { char token[16]; scanf("%15s", token); has[i][c] = strcmp(token, "x") != 0; if (has[i][c]) value[i][c] = atoll(token); } } for (int j = 0; j < r; j++) { char dir[4]; scanf("%d %3s %lld", &field[j], dir, &tol[j]); field[j]--; high[j] = dir[0] == 'H'; } for (int t = 0; t < q; t++) { int a, b; scanf("%d %d", &a, &b); int winner = 0; /* 앞선 상품 번호(끝까지 비기면 0) */ int decided = 0; /* 가른 기준의 차례 */ for (int j = 0; j < r && winner == 0; j++) { int f = field[j]; int hasA = has[a - 1][f], hasB = has[b - 1][f]; if (!hasA && !hasB) continue; /* 둘 다 값이 없으면 이 기준은 비긴다 */ if (!hasA || !hasB) { /* 값이 없는 쪽이 진다(방향과 상관없이) */ winner = hasA ? a : b; } else { long long u = value[a - 1][f], v = value[b - 1][f]; if (llabs(u - v) <= tol[j]) continue; /* 차이가 허용 오차 이하이면 비긴다 */ winner = (u > v) == high[j] ? a : b; } decided = j + 1; } if (winner == 0) printf("0\n"); else printf("%d %d\n", winner, decided); } return 0;}
Craykonmain.cray · 81 行
// [앞선 쪽, 가른 기준의 차례]: 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0견주기(x, y, rules){ 繰り返す (j = 0; j < rules.個数; j++) { f = rules[j][0]; high = rules[j][1]; u = x[f]; v = y[f]; もし (u == なし && v == なし) { 次へ; } もし (u == なし) { 返す [-1, j + 1]; } もし (v == なし) { 返す [1, j + 1]; } もし (数学.絶対値(u - v) <= rules[j][2]) { 次へ; } もし (u > v == high) { 返す [1, j + 1]; } 返す [-1, j + 1]; } 返す [0, 0];}첫줄 = コンソール.数読み();n = 첫줄[0];r = 첫줄[2];q = 첫줄[3];items = [];繰り返す (i = 0; i < n; i++){ 칸들 = []; それぞれ (t の中 コンソール.行読み().分ける()) { もし (t == "x") { 칸들.追加(なし); // 값이 없는 칸. 빈값으로 빼거나 견주면 멈추므로 먼저 걸러야 한다 } でなければ { 칸들.追加(t.数に()); } } items.追加(칸들);}rules = []; // [볼 칸(0부터), 클수록 좋은가, 허용 오차]繰り返す (j = 0; j < r; j++){ w = コンソール.行読み().分ける(); rules.追加([w[0].数に() - 1, w[1] == "H", w[2].数に()]);}繰り返す (t = 0; t < q; t++){ 쌍 = コンソール.数読み(); 결과 = 견주기(items[쌍[0] - 1], items[쌍[1] - 1], rules); もし (결과[0] == 0) { コンソール.書く(0); } でなければ もし (결과[0] > 0) { コンソール.書く(쌍[0] + " " + 결과[1]); } でなければ { コンソール.書く(쌍[1] + " " + 결과[1]); }}