A store's comparison helper tells which of two products is better.
There are n products numbered 1 to n, and each product has k fields numbered 1 to k, each holding a measurement (an integer).
A field that was not measured holds x instead of a number.
You are given r comparison rules, most important first.
A rule "f d e" looks at field f. If d is H the larger measurement is better, and if d is L the smaller measurement is better. e is the tolerance.
No two rules look at the same field.
To compare two products, go through the rules in order, starting with the first.
If both products have x in that field, they tie on this rule.
If only one has x, the product that has a measurement is better, whatever d is.
If both have measurements and their difference (the larger minus the smaller) is e or less, they tie on this rule.
If the difference is more than e, the product with the larger measurement is better when d is H, and the one with the smaller measurement is better when d is L.
On a tie, move on to the next rule; once one product is better, stop there.
You are given q questions; a question "a b" asks you to compare product a with product b (a and b may be the same).
For each question print one line with the number of the better product and the position of the rule that decided it (the first rule is 1), separated by one space.
If the products tie on every rule, print just 0.
Input
The first line gives n, k, r and q separated by spaces. Each of the next n lines gives the k field values (an integer or x) of one product, starting with product 1, separated by single spaces. The next r lines each give a rule "f d e", and the next q lines each give a question "a b". 2 ≤ n ≤ 1,000, 1 ≤ k ≤ 8, 1 ≤ r ≤ k, 1 ≤ q ≤ 10,000, -2,000,000,000 ≤ measurement ≤ 2,000,000,000, 1 ≤ f ≤ k, d is H or L, 0 ≤ e ≤ 1,000,000,000, 1 ≤ a, b ≤ n
Output
q lines. Each line is "number of the better product, position of the deciding rule", or 0
Example 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
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Comparing two values has three outcomes — first is better, second is better, tie — and 'no value' cuts in on top of that. So the order of the questions matters: ① are both missing, ② is just one missing, ③ is the difference within the tolerance, ④ which is larger. The direction can be asked in one go with (u > v) == high: is 'u is the larger one' the same as 'larger is better'? Trap one: the measurements are within ±2 billion, so they fit a 32-bit int, but the difference of two of them reaches 4 billion and overflows. Java Math.abs(u - v) and C# int subtraction wrap around without any error and give a wrong small number (2 billion − (−2 billion) becomes −294,967,296), and in C and C++ it is undefined behaviour. Read into long in Java and C#, long long in C and C++, and since C's abs is for int, use llabs. Python integers have no limit, and JS, TS and Craykon numbers are exact up to 2^53, so they just work. Trap two: standing in for 'no value' with a very small number is right for an H rule but makes the missing side win an L rule (smaller is better). Keep 'missing' separate: Python None, JS and TS null (in TS the type is number | null, so subtracting before you rule out null is a compile error), C# long?, C++ std::optional<long long>, Craykon null, and in Java and C a separate array that records whether a value is there. Comparing without ruling out the missing value differs by language: Python None < 5 is a TypeError, Java throws NullPointerException when a Long is null, and Craykon stops with "Can't calculate with null". The quiet ones are more dangerous: JS turns null into 0 for the comparison (null < 5 is true), with C# long? both < and > are false when either side is null, and a C++ optional always counts the empty side as smaller. Trap three: the boundary. A difference of exactly e is a tie, so it is <=, not <. Trap four: in JS, if you do not convert the strings from split into numbers, u - v is still computed as numbers but u > v compares character by character, so "10" > "9" is false. In Python subtracting strings is a TypeError and Craykon stops, saying - works on numbers only, so there it shows up at once. Trap five: what you print is not the field number f that the rule looks at but the position of the rule in the list.
Pythonmain.py · 33 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
// [앞선 쪽, 가른 기준의 차례]: 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0견주기(x, y, rules){ for (j = 0; j < rules.Count; j++) { f = rules[j][0]; high = rules[j][1]; u = x[f]; v = y[f]; if (u == null && v == null) { continue; } if (u == null) { return [-1, j + 1]; } if (v == null) { return [1, j + 1]; } if (Mathf.Abs(u - v) <= rules[j][2]) { continue; } if (u > v == high) { return [1, j + 1]; } return [-1, j + 1]; } return [0, 0];}첫줄 = Console.ReadNumbers();n = 첫줄[0];r = 첫줄[2];q = 첫줄[3];items = [];for (i = 0; i < n; i++){ 칸들 = []; foreach (t in Console.ReadLine().Split()) { if (t == "x") { 칸들.Add(null); // 값이 없는 칸. 빈값으로 빼거나 견주면 멈추므로 먼저 걸러야 한다 } else { 칸들.Add(t.ToNumber()); } } items.Add(칸들);}rules = []; // [볼 칸(0부터), 클수록 좋은가, 허용 오차]for (j = 0; j < r; j++){ w = Console.ReadLine().Split(); rules.Add([w[0].ToNumber() - 1, w[1] == "H", w[2].ToNumber()]);}for (t = 0; t < q; t++){ 쌍 = Console.ReadNumbers(); 결과 = 견주기(items[쌍[0] - 1], items[쌍[1] - 1], rules); if (결과[0] == 0) { Console.WriteLine(0); } else if (결과[0] > 0) { Console.WriteLine(쌍[0] + " " + 결과[1]); } else { Console.WriteLine(쌍[1] + " " + 결과[1]); }}