町が n 個あり、1 番から n 番まで番号が付いている。 町の間に道が m 本あり、1 本の道 "a b" は a 番の町と b 番の町をつなぐ。 道は両方向に通れる。 同じ 2 つの町をつなぐ道が複数あることがあり、それらは別々の道として扱う。 町ごとに、その町に接する道に順番を付ける。 入力で先に現れた道が前で、その町に接する道のうち入力でいちばん先に現れた道が、その町の 1 番目の道である。 道案内のメモが q 枚ある。 1 枚のメモには、出発する町 s と k 個の指示 c₁, c₂, …, c_k が書かれている。 旅人は s 番の町から出発し、指示を前から 1 つずつたどる。 指示 c に従うとは、今いる町の c 番目の道を通って、その道の向こう側の町へ行くことである。 今いる町に接する道が c 本より少なければ、その指示には従えない。 旅人はその町で止まり、残りの指示をすべて捨てる。 メモごとに 1 行に、旅人が最後にいる町の番号と従った指示の数を空白 1 つで区切って出力せよ。
入力
1 行目に n と m が空白 1 つで区切られて与えられる。 続く m 行に、道が 1 行に 1 本ずつ "a b" で与えられる。 その次の行に q が与えられ、続く q 行に、メモが 1 行に 1 枚ずつ "s k c₁ c₂ … c_k" の形で空白 1 つずつで区切られて与えられる。 2 ≤ n ≤ 50、1 ≤ m ≤ 200、1 ≤ a, b ≤ n、a ≠ b、1 ≤ q ≤ 50、1 ≤ s ≤ n、1 ≤ k ≤ 50、1 ≤ c ≤ 200
道のリストを「町ごとの、接する道の向こう側の町のリスト」（隣接リスト）に変えておくと、指示 1 つを roads[town][c - 1] の 1 回でたどれます。 例では 1 番の町が 2, 3、3 番の町が 2, 1, 4 です。 言語ごとに分かれるのは「空のリスト n + 1 個」の作り方です。 落とし穴 1：Python [[]] * (n + 1) と JS・TS new Array(n + 1).fill([]) は、空のリストを n + 1 個作るのではなく、同じ 1 つのリストを n + 1 回指します。 すべての町の道が 1 つのリストに混ざり、例が 2 3、2 4、3 2 になります。 Python は [[] for _ in range(n + 1)]、JS・TS は Array.from({ length: n + 1 }, () => []) と書きます。 C++ vector<vector<int>> roads(n + 1) と Craykon 新リスト(n + 1, []) は場所ごとに別のリストを作ってくれ（ただし 新リスト(n, 辞書()) のように辞書で埋めると、すべての場所が同じ 1 つの辞書を指します）、Java と C# はループで場所ごとに new ArrayList<>()、new List<int>() を入れます。 C には伸びるリストがないので、roads[51][200] の配列と、町ごとの道の数を数える配列を使います。 落とし穴 2：道 "a b" を a 番の町にだけ書くと、b 番の町からはその道が見えません。 例が 3 1、2 0、4 0 になります。 落とし穴 3：c 番目の道は、0 から数えるリストでは c - 1 番です。 roads[town][c] で読むと 1 つ後ろの道を通り、例の最初のメモのように最後の道を選ぶとリストの外を読みます。 Python は IndexError で止まります。 落とし穴 4：道が足りない指示で止まらずにその指示だけを飛ばすと、例の 2 枚目のメモが最後の指示までたどられて 1 3 になります。 道が足りるかどうかをまったく確かめないと、JS・TS は配列の外を読んでもエラーなしに undefined を返すので町の番号が undefined になり、その次の指示でようやく TypeError で止まります。 1 行に数がいくつ来るか分からないメモの行は、Python・JS のように入力全体を空白で切っておいて順に読むと楽ですが、そのときは止まった後も読む位置を k だけ進めないと次のメモがずれます。 C と C++ も残りの指示を最後まで読んで捨てます。
Pythonmain.py · 31 行
import sysdata = sys.stdin.read().split()pos = 0n, m = int(data[0]), int(data[1])pos = 2# roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로# [[]] * (n + 1)로 만들면 모든 칸이 같은 목록 하나를 가리키므로 칸마다 새 목록을 만든다roads = [[] for _ in range(n + 1)]for _ in range(m): a, b = int(data[pos]), int(data[pos + 1]) pos += 2 roads[a].append(b) # 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].append(a)q = int(data[pos])pos += 1out = []for _ in range(q): town, k = int(data[pos]), int(data[pos + 1]) pos += 2 followed = 0 for j in range(k): c = int(data[pos + j]) if c > len(roads[town]): # 그런 길이 없으면 거기서 멈춘다 break town = roads[town][c - 1] # c번째 길은 0부터 세면 c - 1번 followed += 1 pos += k # 버린 지시까지 건너뛴다 out.append(f"{town} {followed}")print("\n".join(out))
JavaScriptmain.js · 30 行
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);let pos = 0;const n = data[pos++];const m = data[pos++];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// new Array(n + 1).fill([])로 만들면 모든 칸이 같은 배열 하나를 가리키므로 칸마다 새 배열을 만든다const roads = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < m; i++) { const a = data[pos++]; const b = data[pos++]; roads[a].push(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push(a);}const q = data[pos++];const out = [];for (let i = 0; i < q; i++) { let town = data[pos++]; const k = data[pos++]; let followed = 0; for (let j = 0; j < k; j++) { const c = data[pos + j]; if (c > roads[town].length) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } pos += k; // 버린 지시까지 건너뛴다 out.push(`${town} ${followed}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 32 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((s: string): boolean => s !== "").map(Number);let pos = 0;const n: number = data[pos++];const m: number = data[pos++];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// new Array(n + 1).fill([])로 만들면 모든 칸이 같은 배열 하나를 가리키므로 칸마다 새 배열을 만든다const roads: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 0; i < m; i++) { const a: number = data[pos++]; const b: number = data[pos++]; roads[a].push(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push(a);}const q: number = data[pos++];const out: string[] = [];for (let i = 0; i < q; i++) { let town: number = data[pos++]; const k: number = data[pos++]; let followed = 0; for (let j = 0; j < k; j++) { const c: number = data[pos + j]; if (c > roads[town].length) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } pos += k; // 버린 지시까지 건너뛴다 out.push(`${town} ${followed}`);}console.log(out.join("\n"));
JavaMain.java · 45 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;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 m = Integer.parseInt(st.nextToken()); // roads.get(v) = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // 바깥 목록에 칸마다 new ArrayList<>()를 하나씩 넣어야 한다 List<List<Integer>> roads = new ArrayList<>(); for (int v = 0; v <= n; v++) { roads.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); roads.get(a).add(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads.get(b).add(a); } int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { st = new StringTokenizer(in.readLine()); int town = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int followed = 0; for (int j = 0; j < k; j++) { int c = Integer.parseInt(st.nextToken()); if (c > roads.get(town).size()) break; // 그런 길이 없으면 거기서 멈춘다 town = roads.get(town).get(c - 1); // c번째 길은 0부터 세면 c - 1번 followed++; } out.append(town).append(' ').append(followed).append('\n'); } System.out.print(out); }}
C#Main.cs · 47 行
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int n = int.Parse(first[0]); int m = int.Parse(first[1]); // roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // new List<int>[n + 1]만 하면 칸이 모두 null이라서 칸마다 new List<int>()를 넣어야 한다 var roads = new List<int>[n + 1]; for (int v = 0; v <= n; v++) { roads[v] = new List<int>(); } for (int i = 0; i < m; i++) { string[] p = Console.ReadLine().Trim().Split(' '); int a = int.Parse(p[0]); int b = int.Parse(p[1]); roads[a].Add(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].Add(a); } int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] p = Console.ReadLine().Trim().Split(' '); int town = int.Parse(p[0]); int k = int.Parse(p[1]); int followed = 0; for (int j = 0; j < k; j++) { int c = int.Parse(p[2 + j]); if (c > roads[town].Count) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } sb.Append(town).Append(' ').Append(followed).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 37 行
#include <iostream>#include <vector>using namespace std;int main() { int n, m, q; cin >> n >> m; // roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // vector<vector<int>>는 칸마다 따로 빈 vector를 만들어 준다 vector<vector<int>> roads(n + 1); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; roads[a].push_back(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push_back(a); } cin >> q; for (int i = 0; i < q; i++) { int town, k, followed = 0; bool stopped = false; cin >> town >> k; for (int j = 0; j < k; j++) { int c; cin >> c; // 멈춘 뒤에도 남은 지시는 읽어서 버려야 다음 쪽지가 밀리지 않는다 if (stopped) continue; if (c > (int)roads[town].size()) { // 그런 길이 없으면 거기서 멈춘다 stopped = true; continue; } town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } cout << town << ' ' << followed << '\n'; } return 0;}
Cmain.c · 39 行
#include <stdio.h>#define MAXN 50#define MAXM 200int main(void) { int n, m, q; /* roads[v][i] = v번 마을의 (i + 1)번째 길 건너편 마을, count[v] = v번 마을에 닿은 길의 수 */ /* C에는 늘어나는 목록이 없어서, 한 마을에 길이 모두 몰려도 되도록 칸을 넉넉히 잡는다 */ static int roads[MAXN + 1][MAXM]; static int count[MAXN + 1]; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); roads[a][count[a]++] = b; /* 길은 양쪽으로 다니므로 두 마을 모두에 적는다 */ roads[b][count[b]++] = a; } scanf("%d", &q); for (int i = 0; i < q; i++) { int town, k, followed = 0, stopped = 0; scanf("%d %d", &town, &k); for (int j = 0; j < k; j++) { int c; scanf("%d", &c); /* 멈춘 뒤에도 남은 지시는 읽어서 버려야 다음 쪽지가 밀리지 않는다 */ if (stopped) continue; if (c > count[town]) { /* 그런 길이 없으면 거기서 멈춘다 */ stopped = 1; continue; } town = roads[town][c - 1]; /* c번째 길은 0부터 세면 c - 1번 */ followed++; } printf("%d %d\n", town, followed); } return 0;}
Craykonmain.cray · 34 行
첫줄 = コンソール.数読み();n = 첫줄[0];m = 첫줄[1];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// 새목록(개수, [])은 칸마다 따로 빈 목록을 만들어 준다roads = 新リスト(n + 1, []);繰り返す (i = 0; i < m; i++){ 길 = コンソール.数読み(); roads[길[0]].追加(길[1]); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[길[1]].追加(길[0]);}q = コンソール.数読み()[0];out = [];繰り返す (i = 0; i < q; i++){ 쪽지 = コンソール.数読み(); town = 쪽지[0]; k = 쪽지[1]; followed = 0; 繰り返す (j = 0; j < k; j++) { c = 쪽지[2 + j]; もし (c > roads[town].個数) { 抜ける; } town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed += 1; } out.追加(town + " " + followed);}コンソール.書く(out.つなぐ("\n"));