A paper dictionary prints the first and the last word of each page at the top of that page.
These two words are called guide words.
The words on p pages of a dictionary are given, shuffled within each page.
The order of words is decided by character codes.
Compare two words character by character from the front: the word whose first differing character has the smaller code comes earlier, and if one word is exactly the beginning of the other, the shorter word comes earlier.
Among the character codes, the hyphen (-) is the smallest, then the uppercase letters A to Z, then the lowercase letters a to z.
First find, for each page, its earliest word and its latest word, that is, its guide words.
Then q words to look up are given, and for each of them find the number of the page where it would have to appear.
If a word is the same as or later than the earliest word of page i, and the same as or earlier than the latest word of page i, then the page where it would have to appear is page i.
Input
The first line contains the number of pages p (1 ≤ p ≤ 100).
The i-th of the next p lines contains the number of words k on page i followed by the k words, separated by single spaces (1 ≤ k ≤ 50).
A word is a string of length 1 to 15 made only of uppercase letters, lowercase letters, and hyphens (-).
All words in the dictionary are different.
Every word on page i comes earlier than every word on page i+1.
The next line contains the number of words to look up q (1 ≤ q ≤ 1,000).
Each of the next q lines contains one word to look up.
A word to look up is also a string of length 1 to 15 made of the same characters, and it may be a word that is not in the dictionary.
Output
On the i-th of the first p lines, print the earliest word and the latest word of page i separated by a single space.
For a page with only one word, print that word twice.
On the next q lines, print for each word to look up the number of the page where it would have to appear, one per line in the given order.
If there is no such page, print 0.
Example 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
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
Languages differ in how they compare strings and in how they pick the earliest of several.
In Python, <, <=, min() and max() work on strings as they are and compare by code. You can even chain comparisons, as in first <= w <= last.
In JavaScript and TypeScript, < between strings is also code order. But Math.min("b", "a") is NaN (a type error in TypeScript), so you find the earliest word with a loop. localeCompare uses locale order, so it puts "IT" and "Ice" the other way round from <.
In Java and C#, < on strings is a compile error. Java looks at the sign of a.compareTo(b), and Collections.min() uses the same order. In C#, string.CompareOrdinal(a, b) is code order, while string.Compare, CompareTo and LINQ's Min() and Max() use culture order.
C looks at the sign of strcmp(a, b); C++ uses < on std::string directly and can find both ends at once with minmax_element.
In Craykon, < between strings is also code order.
Trap one: the chained comparison. In JavaScript, first <= w <= last runs without an error, but the first comparison becomes true or false, and when that value is compared with the word, the word turns into the number NaN, so the result is false. It prints 0 for all six words to look up in example 1. TypeScript stops this expression with a type error, and Craykon with a compile error.
Trap two: culture order. Page 1 of example 1, Io IT Ice, is IT, Ice, Io in code order (uppercase T comes before lowercase c). C#'s Min() and Max() see the order Ice, Io, IT, so they print Ice IT instead of IT Io.
Trap three: comparing while ignoring case. Comparing with Java's compareToIgnoreCase also gives Ice IT on that line.
Trap four: a word equal to a guide word. Io and app in example 1 are guide words themselves, so comparing with < instead of <= gives 0. The same goes for zebra on page 3, which has only one word.
Trap five: starting over on each page. If the variable holding the earliest word is not started over on each page, the one from page 1 stays, because every word on later pages comes later. Page 2 of example 1 comes out as IT cat instead of app cat.
Pythonmain.py · 26 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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;}
Craykonmain.cray · 41 lines
쪽수 = Console.ReadLine().ToNumber();첫낱말들 = [];끝낱말들 = [];for (i = 0; i < 쪽수; i++){ 칸들 = Console.ReadLine().Trim().Split(); // 문자열끼리 <는 코드 순서다 첫낱말 = 칸들[1]; 끝낱말 = 칸들[1]; for (j = 2; j < 칸들.Count; j++) { if (칸들[j] < 첫낱말) { 첫낱말 = 칸들[j]; } if (칸들[j] > 끝낱말) { 끝낱말 = 칸들[j]; } } 첫낱말들.Add(첫낱말); 끝낱말들.Add(끝낱말); Console.WriteLine(첫낱말 + " " + 끝낱말);}찾을수 = Console.ReadLine().ToNumber();for (j = 0; j < 찾을수; j++){ 낱말 = Console.ReadLine().Trim(); 쪽 = 0; for (i = 0; i < 쪽수; i++) { // 첫낱말들[i] <= 낱말 <= 끝낱말들[i]처럼 이어 쓰면 컴파일 오류다 if (첫낱말들[i] <= 낱말 && 낱말 <= 끝낱말들[i]) { 쪽 = i + 1; break; } } Console.WriteLine(쪽);}