小川に石が n 個、左から 1 番、2 番、…、n 番と一列に並んでいる。 i 番の石には整数 a_i が書いてある。 i 番の石にいるカエルは、いつも i + a_i 番の石へ跳ぶ。 a_i が負なら左へ、0 ならその場へ跳ぶ。 跳んだ先が 1 より小さいか n より大きければ、カエルは小川から出る。 カエルが一度いた石にまた降りると、同じ道を果てしなく繰り返すので小川から出られない。 出発した石も、いた石に数える。 q 匹のカエルが順に、一匹ずつ別々に出発する。 前のカエルの道は後のカエルとは関係ない。 一行目に n、二行目に a_1 から a_n、三行目に q、四行目にカエルごとの出発する石の番号が空白区切りで与えられる。 カエルごとに一行に、小川から出るなら出るまでに跳んだ回数を出力せよ。 外へ出る最後の一跳びも数える。 出られないなら -1 を出力せよ。
入力
1 ≤ n ≤ 2,000、-n ≤ a_i ≤ n、1 ≤ q ≤ 200、1 ≤ 出発する石の番号 ≤ n
出力
q 行、各行は跳んだ回数または -1
例 1 · stdin
6
2 4 -2 -4 -3 1
5
1 2 4 5 6
stdout
-1
2
1
3
1
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
石の番号は 1 から、八つの言語のリストの添字はどれも 0 からなので、出発するときに一度 i = s - 1 と直し、そのあとは添字だけで考えるのがいちばん迷いません。 すると小川の中は 0 <= i < n です（Python は 0 <= i < n をそのまま書け、ほかの言語は i >= 0 && i < n）。 直さずに a[s] から始めると一つ右の石から出発し、端の検査を i < n - 1 と書くと n 番の石を小川の外とみなします。 範囲を先に聞いてから a[i] を読む必要があります。 範囲の外を読むと、Python は負の添字を後ろから数えて黙って間違え（a[-1] は最後の石）、JS・TS は undefined を返して i + undefined が NaN になります。 Java・C# は例外、Craykon は実行エラーで止まり、C・C++ の配列は何でも読んでしまう未定義動作です。 いた石の記録はカエルごとに新しく作ります。 Python [False] * n、JS new Array(n).fill(false)、Java new boolean[n]、C# new bool[n]（どちらも最初から false）、C memset(seen, 0, sizeof seen)、C++ std::vector<bool>(n, false)、Craykon 新リスト(n, 偽) です。 記録を一つだけ使い回すと、前のカエルが踏んだ石に降りただけで閉じ込められたと出ます。 外へ出る最後の一跳びを数え忘れるのもよくある間違いです。
Pythonmain.py · 14 行
n = int(input())a = list(map(int, input().split()))q = int(input())out = []for s in map(int, input().split()): seen = [False] * n # 개구리마다 새로 — 앞 개구리의 기록을 쓰면 안 된다 i = s - 1 # 돌 번호(1부터) → 목록 번호(0부터) jumps = 0 while 0 <= i < n and not seen[i]: seen[i] = True i += a[i] jumps += 1 out.append(jumps if not 0 <= i < n else -1)print("\n".join(map(str, out)))
JavaScriptmain.js · 19 行
const tokens = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);let pos = 0;const n = tokens[pos++];const a = tokens.slice(pos, pos + n);pos += n;const q = tokens[pos++];const out = [];for (let t = 0; t < q; t++) { const seen = new Array(n).fill(false); // 개구리마다 새로 let i = tokens[pos++] - 1; // 돌 번호(1부터) → 배열 번호(0부터) let jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } out.push(i >= 0 && i < n ? -1 : jumps);}console.log(out.join("\n"));
TypeScriptmain.ts · 20 行
import { readFileSync } from "node:fs";const tokens: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);let pos = 0;const n = tokens[pos++];const a: number[] = tokens.slice(pos, pos + n);pos += n;const q = tokens[pos++];const out: number[] = [];for (let t = 0; t < q; t++) { const seen: boolean[] = new Array<boolean>(n).fill(false); // 개구리마다 새로 let i = tokens[pos++] - 1; // 돌 번호(1부터) → 배열 번호(0부터) let jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } out.push(i >= 0 && i < n ? -1 : jumps);}console.log(out.join("\n"));
JavaMain.java · 28 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); int[] a = new int[n]; StringTokenizer st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(in.readLine().trim()); st = new StringTokenizer(in.readLine()); StringBuilder out = new StringBuilder(); for (int t = 0; t < q; t++) { boolean[] seen = new boolean[n]; // 개구리마다 새로(모두 false) int i = Integer.parseInt(st.nextToken()) - 1; // 돌 번호(1부터) → 배열 번호(0부터) int jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } out.append(i >= 0 && i < n ? -1 : jumps).append('\n'); } System.out.print(out); }}
C#Main.cs · 29 行
using System;using System.Linq;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); int[] a = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); Console.ReadLine(); int[] starts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); var sb = new StringBuilder(); foreach (int s in starts) { bool[] seen = new bool[n]; // 개구리마다 새로(모두 false) int i = s - 1; // 돌 번호(1부터) → 배열 번호(0부터) int jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } sb.Append(i >= 0 && i < n ? -1 : jumps).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 24 行
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); int n, q; std::cin >> n; std::vector<int> a(n); for (int& x : a) std::cin >> x; std::cin >> q; for (int t = 0; t < q; t++) { int s; std::cin >> s; std::vector<bool> seen(n, false); // 개구리마다 새로 int i = s - 1; // 돌 번호(1부터) → 배열 번호(0부터) int jumps = 0; while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps++; } std::cout << ((i >= 0 && i < n) ? -1 : jumps) << '\n'; }}
Cmain.c · 26 行
#include <stdio.h>#include <string.h>int main(void) { static int a[2000]; static char seen[2000]; int n, q; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); scanf("%d", &q); for (int t = 0; t < q; t++) { int s; scanf("%d", &s); memset(seen, 0, sizeof seen); /* 개구리마다 새로 */ int i = s - 1; /* 돌 번호(1부터) → 배열 번호(0부터) */ int jumps = 0; /* 범위를 먼저 물어야 a[i]·seen[i]가 배열 밖을 읽지 않는다 */ while (i >= 0 && i < n && !seen[i]) { seen[i] = 1; i += a[i]; jumps++; } printf("%d\n", (i >= 0 && i < n) ? -1 : jumps); } return 0;}
Craykonmain.cray · 25 行
n = コンソール.行読み().数に();a = コンソール.数読み();q = コンソール.行読み().数に();starts = コンソール.数読み();それぞれ (s の中 starts){ seen = 新リスト(n, 偽); // 개구리마다 새로 i = s - 1; // 돌 번호(1부터) → 목록 번호(0부터) jumps = 0; // 범위를 먼저 물어야 seen[i]가 목록 밖을 읽지 않는다 間 (i >= 0 && i < n && !seen[i]) { seen[i] = 真; i += a[i]; jumps += 1; } もし (i >= 0 && i < n) { コンソール.書く(-1); } でなければ { コンソール.書く(jumps); }}