比较嵌套条件空值 nullP0301

按规则顺序比较商品

家电卖场的比较助手会告诉顾客两件商品中哪一件更好。
商品共 n 件，编号从 1 到 n，每件商品有编号从 1 到 k 的 k 个栏，每栏写着一个测量值（整数）。
没有测量的栏里写的不是数而是 x。
给出 r 条比较规则，按重要程度从高到低排列。
一条规则 "f d e" 表示看第 f 栏。
d 为 H 时测量值大的更好，d 为 L 时测量值小的更好。
e 是允许误差。
不会有两条规则看同一栏。
比较两件商品时，从第一条规则开始依次这样判断。
如果两件商品的这一栏都是 x，这条规则算平手。
如果只有一件是 x，不管 d 是什么，有测量值的那件更好。
如果两件都有测量值，并且两个测量值的差（大数减小数）不超过 e，这条规则算平手。
如果差大于 e，d 为 H 时测量值大的那件更好，d 为 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

stdout

main.py 编程语言运行版本

输入(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，排除 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 sys  def 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, 0  lines = 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 8 static 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]);    }}