trang chủ / bài tập / arrquery

Truy vấn trên mảng

Cho một mảng $a$ gồm $n$ số nguyên dương, mỗi phần tử không vượt quá $n$ .

Bạn cần xử lý $q$ truy vấn trên mảng này. Mỗi truy vấn gồm hai số $p$ và $k$ . Trong mỗi truy vấn, ta thực hiện lặp lại thao tác sau: thay $p$ bằng $p + a_{p} + k$ . Thao tác được lặp cho đến khi $p$ trở nên lớn hơn $n$ . Đáp án của truy vấn là số thao tác đã thực hiện.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên — các phần tử của mảng $a$ .
Dòng thứ ba chứa số nguyên $q$ .
$q$ dòng tiếp theo, mỗi dòng chứa hai số $p$ và $k$ tương ứng với một truy vấn.

Dữ liệu ra

In ra $q$ số nguyên, mỗi số trên một dòng: số thứ $i$ là đáp án của truy vấn thứ $i$ .

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq a_{i} \leq n$ với mọi $i$ từ $1$ đến $n$
$1 \leq q \leq 10^{5}$
$1 \leq p, k \leq n$

Ví dụ

Input	Output	Giải thích
3 1 1 1 3 1 1 2 1 3 1	2 1 1	Truy vấn 1 ( $p = 1, k = 1$ ): sau thao tác thứ nhất $p = 1 + a_{1} + 1 = 3$ , sau thao tác thứ hai $p = 3 + a_{3} + 1 = 5 > 3$ . Vậy có $2$ thao tác. Truy vấn 2 ( $p = 2, k = 1$ ): $p = 2 + a_{2} + 1 = 4 > 3$ ngay sau thao tác đầu, đáp án $1$ . Truy vấn 3 ( $p = 3, k = 1$ ): $p = 3 + a_{3} + 1 = 5 > 3$ , đáp án $1$ .
10 3 5 4 3 7 10 6 7 2 3 10 4 5 2 10 4 6 9 9 9 2 5 1 6 4 1 1 5 6 6 4	1 1 1 1 1 1 1 2 1 1	Với truy vấn 8 ( $p = 1, k = 1$ ): $p = 1 + a_{1} + 1 = 5$ , rồi $p = 5 + a_{5} + 1 = 13 > 10$ . Vậy $2$ thao tác. Các truy vấn còn lại đều vượt $n$ chỉ sau một thao tác.

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 7,00một phần

Giới hạn thời gian 2.0s

Python 35.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig