codeforces-scrape

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

2162D.md (4426B)


      1 Source: https://codeforces.com/problemset/problem/2162/D
      2 
      3 D. Beautiful Permutation
      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 This is an interactive problem.
     22 
     23 There is a permutation$^{\text{∗}}$ $p$ of length $n$.
     24 
     25 Someone secretly chose two integers $l, r$ ($1 \le l \le r \le n$) and modified the permutation in the following way:
     26 
     27 * For every index $i$ such that $l \le i \le r$, set $p_i := p_i + 1$.
     28 
     29 Let $a$ denote the resulting array obtained by modifying the permutation.
     30 
     31 You are given an integer $n$ denoting the length of the permutation $p$.
     32 
     33 In one query, you are allowed to choose two integers $l, r$ ($1 \le l \le r \le n$) and ask for the sum of the subarray either of the original permutation $p[l \dots r]$ or of the modified array $a[l \dots r]$. The answer to such a query will be the corresponding integer sum.
     34 
     35 Your task is to find the pair $(l, r)$ that was chosen to obtain $a$ in no more than $\bf{40}$ queries.
     36 
     37 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (the number $2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$, but the array contains $4$).
     38 
     39 Input
     40 
     41 The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     42 
     43 Each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^4$) — the length of the permutation.
     44 
     45 It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^4$.
     46 
     47 Interaction
     48 
     49 The interaction for each test case begins by reading the integer $n$.
     50 
     51 You can ask two types of queries.
     52 
     53 * Print "$ \texttt{1 l r} $" ($1 \le l \le r \le n$).
     54 
     55   In response, you should read a line containing a single integer $x$ — the sum of the subarray of the original permutation. (Formally, $x = p_l + p_{l + 1} + \dots + p_r$).
     56 * Print "$ \texttt{2 l r} $" ($1 \le l \le r \le n$).
     57 
     58   In response, you should read a line containing a single integer $y$ — the sum of the subarray of the modified array. (Formally, $y = a_l + a_{l + 1} + \dots + a_r$).
     59 
     60 The permutation $p$ and the chosen integers $l$, $r$ are fixed beforehand and can't be changed during the time of interaction.
     61 
     62 You can output the final answer by printing "$ \texttt{! l r} $", where $l$, $r$ denote the integers that were chosen to obtain $a$. After printing the answer, your program should proceed to the next test case or terminate if there are no more.
     63 
     64 You can ask no more than $40$ queries per testcase. Printing the answer doesn't count as a query. If your program performs more than $40$ queries for one test case or makes an invalid query, you may receive a Wrong Answer verdict.
     65 
     66 After printing a query, do not forget to output the end of line and flush$^{\text{∗}}$ the output. Otherwise, you will get Idleness limit exceeded.
     67 
     68 Hacks
     69 
     70 To make a hack, use the following test format.
     71 
     72 The first line should contain a single integer $t$ $(1 \le t \le 10^4)$ — the number of testcases.
     73 
     74 The first line of each test case should contain a single integer $n$ ($1 \le n \le 2\cdot10^4$) — the length of the permutation $p$.
     75 
     76 The second line of each test case should contain $n$ integers $p_i$ ($1 \le p_i \le n$) — denoting the permutation $p$.
     77 
     78 The third line of each test case should contain two space-separated integers $l$, $r$ ($1 \le l \le r \le n$) — the chosen integers.
     79 
     80 For example, the following is the hack format of the example test:
     81 
     82 ```
     83 2  
     84 3  
     85 3 1 2  
     86 2 2  
     87 4  
     88 2 1 3 4  
     89 2 4
     90 ```
     91 
     92 $^{\text{∗}}$To flush, use:
     93 
     94 * fflush(stdout) or cout.flush() in C++;
     95 * System.out.flush() in Java;
     96 * flush(output) in Pascal;
     97 * stdout.flush() in Python;
     98 * see documentation for other languages
     99 
    100 Example
    101 
    102 Input
    103 
    104 ```
    105 2
    106 
    107 3
    108 
    109 4
    110 
    111 5
    112 
    113 4
    114 
    115 8
    116 
    117 8
    118 
    119 9
    120 ```
    121 
    122 Output
    123 
    124 ```
    125 1 1 2
    126 
    127 2 1 2
    128 
    129 ! 2 2
    130 
    131 1 2 4
    132 
    133 2 1 3
    134 
    135 2 3 4
    136 
    137 ! 2 4
    138 ```
    139 
    140 Note
    141 
    142 For the first testcase, $p = [3, 1, 2]$ and $l = 2$, $r = 2$. Hence, the modified array $a$ will be equal to $[3, 2, 2]$.
    143 
    144 So, querying "$\texttt{1 1 2}$" gives $p_1 + p_2 = 3 + 1 = 4$. And querying "$\texttt{2 1 2}$" gives $a_1 + a_2 = 3 + 2 = 5$.
    145 
    146 For the second testcase, $p = [2, 1, 3, 4]$ and $l = 2$, $r = 4$.
    147 
    148 Note that the queries shown in the sample test are only for demonstration purposes, and they may not correspond to any optimal solution.