In a stream, n stones lie in a row, numbered 1, 2, …, n from the left.
Stone i has an integer a_i written on it.
A frog sitting on stone i always jumps to stone i + a_i. If a_i is negative it jumps left, and if it is 0 it jumps in place.
If the frog lands below 1 or above n, it leaves the stream.
If the frog lands on a stone it has already sat on, it repeats the same path forever and never leaves the stream. The starting stone counts as a stone it has sat on.
q frogs start one after another, each on its own. One frog's path has nothing to do with the next frog.
The first line gives n, the second line a_1 to a_n, the third line q, and the fourth line the starting stone of each frog, separated by spaces.
For each frog print one line: if it leaves the stream, the number of jumps until it leaves, counting the last jump that takes it out.
If it never leaves, print -1.
Input
1 ≤ n ≤ 2,000, -n ≤ a_i ≤ n, 1 ≤ q ≤ 200, 1 ≤ starting stone ≤ n
Output
q lines, each the number of jumps or -1
Example 1 · stdin
6
2 4 -2 -4 -3 1
5
1 2 4 5 6
stdout
-1
2
1
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
Stones are numbered from 1, while list indexes in all eight languages start at 0, so it is least confusing to convert once at the start with i = s - 1 and think only in list indexes after that. Then "in the stream" is 0 <= i < n (Python writes 0 <= i < n as is; the others write i >= 0 && i < n). Starting at a[s] without converting starts one stone to the right, and writing the end check as i < n - 1 treats stone n as outside the stream. Check the range first, then read a[i]. Reading out of range, Python counts a negative index from the back and is silently wrong (a[-1] is the last stone), and JS/TS give undefined, so i + undefined becomes NaN. Java and C# throw, Craykon stops with a runtime error, and C/C++ arrays read whatever is there, which is undefined behavior. The record of visited stones must be made fresh for each frog: Python [False] * n, JS new Array(n).fill(false), Java new boolean[n], C# new bool[n] (both start all false), C memset(seen, 0, sizeof seen), C++ std::vector<bool>(n, false), Craykon NewList(n, false). Keeping one record for all frogs reports a frog as trapped just because it landed where an earlier frog had been. Leaving out the last jump, the one that takes the frog out, is another common mistake.
Pythonmain.py · 14 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
n = Console.ReadLine().ToNumber();a = Console.ReadNumbers();q = Console.ReadLine().ToNumber();starts = Console.ReadNumbers();foreach (s in starts){ seen = NewList(n, false); // 개구리마다 새로 i = s - 1; // 돌 번호(1부터) → 목록 번호(0부터) jumps = 0; // 범위를 먼저 물어야 seen[i]가 목록 밖을 읽지 않는다 while (i >= 0 && i < n && !seen[i]) { seen[i] = true; i += a[i]; jumps += 1; } if (i >= 0 && i < n) { Console.WriteLine(-1); } else { Console.WriteLine(jumps); }}