紙の辞書は、ページごとにいちばん上にそのページの最初の単語と最後の単語を書いておく。 この二つの単語を見出しの単語と呼ぶ。 辞書の p ページに載っている単語が、ページごとにばらばらの順で与えられる。 単語の前後は文字コードの順で決める。 二つの単語を前から一文字ずつ比べて、最初に違う文字のコードが小さいほうが前であり、一方の単語がもう一方の先頭部分とまったく同じなら短いほうが前である。 文字コードはハイフン(-)がいちばん小さく、その次が大文字 A〜Z、その次が小文字 a〜z である。 まずページごとに、そのページでいちばん前の単語といちばん後ろの単語、つまり見出しの単語を求める。 そのあと調べる単語が q 個与えられるので、単語ごとにその単語が載っているはずのページ番号を求める。 調べる単語が i ページのいちばん前の単語と同じかそれより後ろで、i ページのいちばん後ろの単語と同じかそれより前なら、その単語が載っているはずのページは i ページである。
入力
1 行目にページ数 p が与えられる(1 ≤ p ≤ 100)。 続く p 行の i 行目に、i ページの単語数 k と単語 k 個が空白一つで区切って与えられる(1 ≤ k ≤ 50)。 単語は英大文字、英小文字、ハイフン(-)だけからなる長さ 1 以上 15 以下の文字列である。 辞書の単語はすべて互いに異なる。 i ページのどの単語も、i+1 ページのどの単語より前である。 次の行に調べる単語の数 q が与えられる(1 ≤ q ≤ 1,000)。 続く q 行に調べる単語が 1 行に一つずつ与えられる。 調べる単語も同じ文字からなる長さ 1 以上 15 以下の文字列で、辞書にない単語のこともある。
出力
最初の p 行の i 行目に、i ページのいちばん前の単語といちばん後ろの単語を空白一つで区切って出力する。 単語が一つしかないページは、その単語を二回出力する。 続く q 行に、調べる単語ごとに載っているはずのページ番号を与えられた順に 1 行に一つずつ出力する。 そのようなページがなければ 0 を出力する。
例 1 · stdin
3
3 Io IT Ice
4 cat apple banana app
1 zebra
6
apple
Io
app
ant
zebra
Ice
stdout
IT Io
app cat
zebra zebra
2
1
2
0
3
1
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
文字列の前後を比べる方法と、いくつかの中からいちばん前のものを選ぶ方法が言語ごとに違います。 Python は <、<= と min()、max() が文字列にそのまま使えて、コード順で比べます。 first <= w <= last のように比較をつなげて書くこともできます。 JavaScript・TypeScript も文字列どうしの < はコード順です。 ただし Math.min("b", "a") は NaN なので(TypeScript では型エラー)、いちばん前の単語はループで自分で探します。 localeCompare はロケール順なので、"IT" と "Ice" の前後が < と逆になります。 Java と C# は文字列に < を使うとコンパイルエラーです。 Java は a.compareTo(b) の符号を見ます。 Collections.min() も同じ順を使います。 C# は string.CompareOrdinal(a, b) がコード順で、string.Compare、CompareTo、LINQ の Min()・Max() はカルチャ順です。 C は strcmp(a, b) の符号を見ます。 C++ は std::string に < をそのまま使い、minmax_element で両端を一度に求められます。 Craykon も文字列どうしの < はコード順です。 罠その一: つなげて書いた比較です。 JavaScript で first <= w <= last はエラーなしで動きますが、前の比較が先に true か false になり、その値を単語と比べるときに単語が数に変わって NaN になるので false になります。 例 1 の調べる単語六つすべてに 0 を出力します。 TypeScript はこの式を型エラーで、Craykon はコンパイルエラーで止めてくれます。 罠その二: カルチャ順です。 例 1 の 1 ページ Io IT Ice はコード順で IT、Ice、Io です(大文字 T が小文字 c より前)。 C# の Min()・Max() は Ice、Io、IT の順と見るので、IT Io ではなく Ice IT を出力します。 罠その三: 大文字と小文字を区別しない比較です。 Java の compareToIgnoreCase で比べても同じ行で Ice IT になります。 罠その四: 見出しの単語と同じ単語です。 例 1 の Io と app は見出しの単語そのものなので、<= ではなく < で比べると 0 になります。 単語が一つしかない 3 ページの zebra も同じです。 罠その五: ページごとのやり直しです。 いちばん前の単語を入れる変数をページごとに新しく始めないと、後ろのページの単語はどれももっと後ろなので 1 ページのものがそのまま残ります。 例 1 の 2 ページが app cat ではなく IT cat になります。
Pythonmain.py · 26 行
import syslines = sys.stdin.read().split("\n")p = int(lines[0])firsts = []lasts = []out = []for i in range(1, p + 1): words = lines[i].split()[1:] # 문자열 비교(<, min, max)는 글자 코드 순서다 first = min(words) last = max(words) firsts.append(first) lasts.append(last) out.append(first + " " + last)q = int(lines[p + 1])for j in range(q): w = lines[p + 2 + j].strip() page = 0 for i in range(p): if firsts[i] <= w <= lasts[i]: # 파이썬은 비교를 이어 쓸 수 있다 page = i + 1 break out.append(str(page))print("\n".join(out))
JavaScriptmain.js · 32 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const p = Number(lines[0]);const firsts = [];const lasts = [];const out = [];for (let i = 1; i <= p; i++) { const words = lines[i].trim().split(" ").slice(1); // 문자열끼리 <는 코드 순서다(Math.min은 문자열에 쓸 수 없다) let first = words[0]; let last = words[0]; for (const w of words) { if (w < first) first = w; if (w > last) last = w; } firsts.push(first); lasts.push(last); out.push(first + " " + last);}const q = Number(lines[p + 1]);for (let j = 0; j < q; j++) { const w = lines[p + 2 + j].trim(); let page = 0; for (let i = 0; i < p; i++) { if (firsts[i] <= w && w <= lasts[i]) { page = i + 1; break; } } out.push(String(page));}console.log(out.join("\n"));
TypeScriptmain.ts · 34 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const p: number = Number(lines[0]);const firsts: string[] = [];const lasts: string[] = [];const out: string[] = [];for (let i = 1; i <= p; i++) { const words: string[] = lines[i].trim().split(" ").slice(1); // 문자열끼리 <는 코드 순서다(Math.min은 문자열을 받지 않는다) let first: string = words[0]; let last: string = words[0]; for (const w of words) { if (w < first) first = w; if (w > last) last = w; } firsts.push(first); lasts.push(last); out.push(first + " " + last);}const q: number = Number(lines[p + 1]);for (let j = 0; j < q; j++) { const w: string = lines[p + 2 + j].trim(); let page: number = 0; for (let i = 0; i < p; i++) { if (firsts[i] <= w && w <= lasts[i]) { page = i + 1; break; } } out.push(String(page));}console.log(out.join("\n"));
JavaMain.java · 40 行
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 p = Integer.parseInt(br.readLine().trim()); String[] firsts = new String[p]; String[] lasts = new String[p]; StringBuilder sb = new StringBuilder(); for (int i = 0; i < p; i++) { String[] parts = br.readLine().trim().split(" "); // 문자열에는 <가 없다: compareTo가 코드 순서로 견준다 String first = parts[1]; String last = parts[1]; for (int j = 2; j < parts.length; j++) { if (parts[j].compareTo(first) < 0) first = parts[j]; if (parts[j].compareTo(last) > 0) last = parts[j]; } firsts[i] = first; lasts[i] = last; sb.append(first).append(' ').append(last).append('\n'); } int q = Integer.parseInt(br.readLine().trim()); for (int j = 0; j < q; j++) { String w = br.readLine().trim(); int page = 0; for (int i = 0; i < p; i++) { if (firsts[i].compareTo(w) <= 0 && w.compareTo(lasts[i]) <= 0) { page = i + 1; break; } } sb.append(page).append('\n'); } System.out.print(sb); }}
C#Main.cs · 45 行
using System;using System.Text;class Program{ static void Main() { int p = int.Parse(Console.ReadLine().Trim()); string[] firsts = new string[p]; string[] lasts = new string[p]; StringBuilder sb = new StringBuilder(); for (int i = 0; i < p; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); // CompareOrdinal이 코드 순서다(Compare, CompareTo, Min()은 문화권 순서) string first = parts[1]; string last = parts[1]; for (int j = 2; j < parts.Length; j++) { if (string.CompareOrdinal(parts[j], first) < 0) first = parts[j]; if (string.CompareOrdinal(parts[j], last) > 0) last = parts[j]; } firsts[i] = first; lasts[i] = last; sb.Append(first).Append(' ').Append(last).Append('\n'); } int q = int.Parse(Console.ReadLine().Trim()); for (int j = 0; j < q; j++) { string w = Console.ReadLine().Trim(); int page = 0; for (int i = 0; i < p; i++) { if (string.CompareOrdinal(firsts[i], w) <= 0 && string.CompareOrdinal(w, lasts[i]) <= 0) { page = i + 1; break; } } sb.Append(page).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 40 行
#include <algorithm>#include <iostream>#include <string>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int p; cin >> p; vector<string> firsts(p), lasts(p); for (int i = 0; i < p; i++) { int k; cin >> k; vector<string> words(k); for (auto& w : words) cin >> w; // std::string의 <는 코드 순서다 auto [lo, hi] = minmax_element(words.begin(), words.end()); firsts[i] = *lo; lasts[i] = *hi; cout << firsts[i] << ' ' << lasts[i] << '\n'; } int q; cin >> q; for (int j = 0; j < q; j++) { string w; cin >> w; int page = 0; for (int i = 0; i < p; i++) { if (firsts[i] <= w && w <= lasts[i]) { page = i + 1; break; } } cout << page << '\n'; } return 0;}
Cmain.c · 38 行
#include <stdio.h>#include <string.h>static char firsts[100][16];static char lasts[100][16];int main(void) { int p; if (scanf("%d", &p) != 1) return 1; for (int i = 0; i < p; i++) { int k; char w[16]; if (scanf("%d", &k) != 1) return 1; for (int j = 0; j < k; j++) { if (scanf("%15s", w) != 1) return 1; /* strcmp는 부호만 믿는다: 음수면 앞, 양수면 뒤 */ if (j == 0 || strcmp(w, firsts[i]) < 0) strcpy(firsts[i], w); if (j == 0 || strcmp(w, lasts[i]) > 0) strcpy(lasts[i], w); } printf("%s %s\n", firsts[i], lasts[i]); } int q; if (scanf("%d", &q) != 1) return 1; for (int j = 0; j < q; j++) { char w[16]; if (scanf("%15s", w) != 1) return 1; int page = 0; for (int i = 0; i < p; i++) { if (strcmp(firsts[i], w) <= 0 && strcmp(w, lasts[i]) <= 0) { page = i + 1; break; } } printf("%d\n", page); } return 0;}