codeforces-scrape

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

1227D1.md (3454B)


      1 Source: https://codeforces.com/problemset/problem/1227/D1
      2 
      3 D1. Optimal Subsequences (Easy Version)
      4 
      5 time limit per test
      6 
      7 3 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 This is the easier version of the problem. In this version $1 \le n, m \le 100$. You can hack this problem only if you solve and lock both problems.
     22 
     23 You are given a sequence of integers $a=[a_1,a_2,\dots,a_n]$ of length $n$. Its subsequence is obtained by removing zero or more elements from the sequence $a$ (they do not necessarily go consecutively). For example, for the sequence $a=[11,20,11,33,11,20,11]$:
     24 
     25 * $[11,20,11,33,11,20,11]$, $[11,20,11,33,11,20]$, $[11,11,11,11]$, $[20]$, $[33,20]$ are subsequences (these are just some of the long list);
     26 * $[40]$, $[33,33]$, $[33,20,20]$, $[20,20,11,11]$ are not subsequences.
     27 
     28 Suppose that an additional non-negative integer $k$ ($1 \le k \le n$) is given, then the subsequence is called optimal if:
     29 
     30 * it has a length of $k$ and the sum of its elements is the maximum possible among all subsequences of length $k$;
     31 * and among all subsequences of length $k$ that satisfy the previous item, it is lexicographically minimal.
     32 
     33 Recall that the sequence $b=[b_1, b_2, \dots, b_k]$ is lexicographically smaller than the sequence $c=[c_1, c_2, \dots, c_k]$ if the first element (from the left) in which they differ less in the sequence $b$ than in $c$. Formally: there exists $t$ ($1 \le t \le k$) such that $b_1=c_1$, $b_2=c_2$, ..., $b_{t-1}=c_{t-1}$ and at the same time $b_t \lt c_t$. For example:
     34 
     35 * $[10, 20, 20]$ lexicographically less than $[10, 21, 1]$,
     36 * $[7, 99, 99]$ is lexicographically less than $[10, 21, 1]$,
     37 * $[10, 21, 0]$ is lexicographically less than $[10, 21, 1]$.
     38 
     39 You are given a sequence of $a=[a_1,a_2,\dots,a_n]$ and $m$ requests, each consisting of two numbers $k_j$ and $pos_j$ ($1 \le k \le n$, $1 \le pos_j \le k_j$). For each query, print the value that is in the index $pos_j$ of the optimal subsequence of the given sequence $a$ for $k=k_j$.
     40 
     41 For example, if $n=4$, $a=[10,20,30,20]$, $k_j=2$, then the optimal subsequence is $[20,30]$ — it is the minimum lexicographically among all subsequences of length $2$ with the maximum total sum of items. Thus, the answer to the request $k_j=2$, $pos_j=1$ is the number $20$, and the answer to the request $k_j=2$, $pos_j=2$ is the number $30$.
     42 
     43 Input
     44 
     45 The first line contains an integer $n$ ($1 \le n \le 100$) — the length of the sequence $a$.
     46 
     47 The second line contains elements of the sequence $a$: integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).
     48 
     49 The third line contains an integer $m$ ($1 \le m \le 100$) — the number of requests.
     50 
     51 The following $m$ lines contain pairs of integers $k_j$ and $pos_j$ ($1 \le k \le n$, $1 \le pos_j \le k_j$) — the requests.
     52 
     53 Output
     54 
     55 Print $m$ integers $r_1, r_2, \dots, r_m$ ($1 \le r_j \le 10^9$) one per line: answers to the requests in the order they appear in the input. The value of $r_j$ should be equal to the value contained in the position $pos_j$ of the optimal subsequence for $k=k_j$.
     56 
     57 Examples
     58 
     59 Input
     60 
     61 ```
     62 3
     63 10 20 10
     64 6
     65 1 1
     66 2 1
     67 2 2
     68 3 1
     69 3 2
     70 3 3
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 20
     77 10
     78 20
     79 10
     80 20
     81 10
     82 ```
     83 
     84 Input
     85 
     86 ```
     87 7
     88 1 2 1 3 1 2 1
     89 9
     90 2 1
     91 2 2
     92 3 1
     93 3 2
     94 3 3
     95 1 1
     96 7 1
     97 7 7
     98 7 4
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 2
    105 3
    106 2
    107 3
    108 2
    109 3
    110 1
    111 1
    112 3
    113 ```
    114 
    115 Note
    116 
    117 In the first example, for $a=[10,20,10]$ the optimal subsequences are:
    118 
    119 * for $k=1$: $[20]$,
    120 * for $k=2$: $[10,20]$,
    121 * for $k=3$: $[10,20,10]$.