codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1602B.md (3302B)


      1 Source: https://codeforces.com/problemset/problem/1602/B
      2 
      3 B. Divine Array
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Black is gifted with a Divine array $a$ consisting of $n$ ($1 \le n \le 2000$) integers. Each position in $a$ has an initial value. After shouting a curse over the array, it becomes angry and starts an unstoppable transformation.
     22 
     23 The transformation consists of infinite steps. Array $a$ changes at the $i$-th step in the following way: for every position $j$, $a_j$ becomes equal to the number of occurrences of $a_j$ in $a$ before starting this step.
     24 
     25 Here is an example to help you understand the process better:
     26 
     27 |  |  |
     28 | --- | --- |
     29 | Initial array: | $2$ $1$ $1$ $4$ $3$ $1$ $2$ |
     30 | After the $1$-st step: | $2$ $3$ $3$ $1$ $1$ $3$ $2$ |
     31 | After the $2$-nd step: | $2$ $3$ $3$ $2$ $2$ $3$ $2$ |
     32 | After the $3$-rd step: | $4$ $3$ $3$ $4$ $4$ $3$ $4$ |
     33 | ... | ... |
     34 
     35 In the initial array, we had two $2$-s, three $1$-s, only one $4$ and only one $3$, so after the first step, each element became equal to the number of its occurrences in the initial array: all twos changed to $2$, all ones changed to $3$, four changed to $1$ and three changed to $1$.
     36 
     37 The transformation steps continue forever.
     38 
     39 You have to process $q$ queries: in each query, Black is curious to know the value of $a_x$ after the $k$-th step of transformation.
     40 
     41 Input
     42 
     43 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.
     44 
     45 The first line of each test case contains an integer $n$ ($1 \le n \le 2000$) — the size of the array $a$.
     46 
     47 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the initial values of array $a$.
     48 
     49 The third line of each test case contains a single integer $q$ ($1 \le q \le 100\,000$) — the number of queries.
     50 
     51 Next $q$ lines contain the information about queries — one query per line. The $i$-th line contains two integers $x_i$ and $k_i$ ($1 \le x_i \le n$; $0 \le k_i \le 10^9$), meaning that Black is asking for the value of $a_{x_i}$ after the $k_i$-th step of transformation. $k_i = 0$ means that Black is interested in values of the initial array.
     52 
     53 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2000$ and the sum of $q$ over all test cases doesn't exceed $100\,000$.
     54 
     55 Output
     56 
     57 For each test case, print $q$ answers. The $i$-th of them should be the value of $a_{x_i}$ after the $k_i$-th step of transformation. It can be shown that the answer to each query is unique.
     58 
     59 Example
     60 
     61 Input
     62 
     63 ```
     64 2
     65 7
     66 2 1 1 4 3 1 2
     67 4
     68 3 0
     69 1 1
     70 2 2
     71 6 1
     72 2
     73 1 1
     74 2
     75 1 0
     76 2 1000000000
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 1
     83 2
     84 3
     85 3
     86 1
     87 2
     88 ```
     89 
     90 Note
     91 
     92 The first test case was described ih the statement. It can be seen that:
     93 
     94 1. $k_1 = 0$ (initial array): $a_3 = 1$;
     95 2. $k_2 = 1$ (after the $1$-st step): $a_1 = 2$;
     96 3. $k_3 = 2$ (after the $2$-nd step): $a_2 = 3$;
     97 4. $k_4 = 1$ (after the $1$-st step): $a_6 = 3$.
     98 
     99 For the second test case,
    100 
    101 |  |  |
    102 | --- | --- |
    103 | Initial array: | $1$ $1$ |
    104 | After the $1$-st step: | $2$ $2$ |
    105 | After the $2$-nd step: | $2$ $2$ |
    106 | ... | ... |
    107 
    108 It can be seen that:
    109 
    110 1. $k_1 = 0$ (initial array): $a_1 = 1$;
    111 2. $k_2 = 1000000000$: $a_2 = 2$;