Array Queries (Codeforces 797E)
Tags: Others, data structures

a is an array of n positive integers, all of which are not greater than n.You have to process q queries to this array. Each query is represented by two numbers p and k. Several operations are performed in each query; each operation changes p to p + ap + k. There operations are applied until p becomes greater than n. The answer to the query is the number of performed operations.

Input: The first line contains one integer n (1 ≤ n ≤ 100000).The second line contains n integers — elements of a (1 ≤ ai ≤ n for each i from 1 to n).The third line containts one integer q (1 ≤ q ≤ 100000).Then q lines follow. Each line contains the values of p and k for corresponding query (1 ≤ p, k ≤ n).

Output: Print q integers, ith integer must be equal to the answer to ith query.

Note: Consider first example:In first query after first operation p = 3, after second operation p = 5.In next two queries p is greater than n after the first operation.

Sample Inputs:
3
1 1 1
3
1 1
2 1
3 1

Sample Outputs:
2
1
1

Solution (Python):
import sys
n = int(sys.stdin.buffer.readline().decode('utf-8'))
a = [0] + list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
q = int(sys.stdin.buffer.readline().decode('utf-8'))
dp_size = 200
dp = [[1] * (n + 1) for _ in range(dp_size + 1)]
for k in range(1, dp_size + 1):
    for i in range(n, 0, -1):
        if i + a[i] + k <= n:
            dp[k][i] = dp[k][i + a[i] + k] + 1
ans = [0] * q
for (i, (p, k)) in enumerate((map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer)):
    if k <= dp_size:
        ans[i] = dp[k][p]
    else:
        while p <= n:
            p += a[p] + k
            ans[i] += 1
sys.stdout.buffer.write('\n'.join(map(str, ans)).encode('utf-8'))

Solution (Python):
import sys
import io, os
input = sys.stdin.buffer.readline
import math
n = int(input())
A = list(map(int, input().split()))
limit = int(math.sqrt(n))
dp = [[-1] * n for i in range(limit + 1)]
for k in range(1, limit + 1):
    for i in range(n - 1, -1, -1):
        if i + A[i] + k >= n:
            dp[k][i] = 1
        else:
            dp[k][i] = dp[k][i + A[i] + k] + 1
q = int(input())
for i in range(q):
    (p, k) = map(int, input().split())
    if k >= limit:
        ans = 0
        while p <= n:
            p = p + A[p - 1] + k
            ans += 1
        print(ans)
    else:
        print(dp[k][p - 1])

Solution (Python):
import math
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
dp = []
m = int(math.sqrt(n)) + 1
for i in range(1, m):
    dp0 = [0] * (n + 1)
    for j in range(n - 1, -1, -1):
        dp0[j] = dp0[min(n, j + a[j] + i)] + 1
    dp.append(dp0)
q = int(input())
for _ in range(q):
    (p, k) = map(int, input().split())
    if k < m:
        ans = dp[k - 1][p - 1]
    else:
        ans = 0
        p -= 1
        while p < n:
            p += a[p] + k
            ans += 1
    print(ans)