E. Array Queries

Codeforces

IDCF797E

Time2000ms

Memory256MB

Difficulty—

brute forcedata structuresdp

English · Original

Chinese · Translation

Formal · Original

_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_ + _a__p_ + _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 ≤ _a__i_ ≤ _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, _i_th integer must be equal to the answer to _i_th query. [samples] ## 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.

#cf_span[a] 是一个包含 #cf_span[n] 个正整数的数组，所有元素均不超过 #cf_span[n]。你需要对这个数组处理 #cf_span[q] 个查询。每个查询由两个数 #cf_span[p] 和 #cf_span[k] 表示。每个查询中会执行若干次操作；每次操作将 #cf_span[p] 更新为 #cf_span[p + ap + k]。这些操作会持续进行，直到 #cf_span[p] 大于 #cf_span[n]。该查询的答案是执行的操作次数。第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 100000)]。第二行包含 #cf_span[n] 个整数 —— 数组 #cf_span[a] 的元素（对于每个 #cf_span[i] 从 #cf_span[1] 到 #cf_span[n]，满足 #cf_span[1 ≤ ai ≤ n]）。第三行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 100000)]。接下来 #cf_span[q] 行，每行包含对应查询的 #cf_span[p] 和 #cf_span[k] 的值 #cf_span[(1 ≤ p, k ≤ n)]。请输出 #cf_span[q] 个整数，第 #cf_span[i] 个整数必须等于第 #cf_span[i] 个查询的答案。考虑第一个例子：在第一个查询中，第一次操作后 #cf_span[p = 3]，第二次操作后 #cf_span[p = 5]。在接下来的两个查询中，第一次操作后 #cf_span[p] 就已大于 #cf_span[n]。 ## Input 第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 100000)]。第二行包含 #cf_span[n] 个整数 —— 数组 #cf_span[a] 的元素（对于每个 #cf_span[i] 从 #cf_span[1] 到 #cf_span[n]，满足 #cf_span[1 ≤ ai ≤ n]）。第三行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 100000)]。接下来 #cf_span[q] 行，每行包含对应查询的 #cf_span[p] 和 #cf_span[k] 的值 #cf_span[(1 ≤ p, k ≤ n)]。 ## Output 请输出 #cf_span[q] 个整数，第 #cf_span[i] 个整数必须等于第 #cf_span[i] 个查询的答案。 [samples] ## Note 考虑第一个例子：在第一个查询中，第一次操作后 #cf_span[p = 3]，第二次操作后 #cf_span[p = 5]。在接下来的两个查询中，第一次操作后 #cf_span[p] 就已大于 #cf_span[n]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of array $ a = (a_1, a_2, \dots, a_n) $, where $ 1 \leq a_i \leq n $ for all $ i \in \{1, \dots, n\} $. Let $ q \in \mathbb{Z}^+ $ be the number of queries. Each query is a pair $ (p, k) \in \{1, \dots, n\}^2 $. **Constraints** 1. $ 1 \leq n \leq 100000 $ 2. $ 1 \leq q \leq 100000 $ 3. $ 1 \leq a_i \leq n $ for all $ i \in \{1, \dots, n\} $ 4. $ 1 \leq p, k \leq n $ for each query **Objective** For each query $ (p, k) $, define the sequence $ p_0 = p $, and for $ t \geq 0 $: $$ p_{t+1} = p_t + a_{p_t} + k $$ Let $ T $ be the smallest non-negative integer such that $ p_T > n $. Output $ T $.

Samples

Input #1

Output #1

2
1
1

API Response (JSON)

{
  "problem": {
    "name": "E. Array Queries",
    "description": {
      "content": "_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 operation",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF797E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_a_ is an array of _n_ positive integers, all of which are not greater than _n_.\n\nYou have to process _q_ queries to this array. Each query is represented by two numbers _p_ and _k_. Several operation...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "#cf_span[a] 是一个包含 #cf_span[n] 个正整数的数组，所有元素均不超过 #cf_span[n]。\n\n你需要对这个数组处理 #cf_span[q] 个查询。每个查询由两个数 #cf_span[p] 和 #cf_span[k] 表示。每个查询中会执行若干次操作；每次操作将 #cf_span[p] 更新为 #cf_span[p + ap + k]。这些操作会持续进行，直到 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of array $ a = (a_1, a_2, \\dots, a_n) $, where $ 1 \\leq a_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments