codeforces-scrape

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

2093D.md (2525B)


      1 Source: https://codeforces.com/problemset/problem/2093/D
      2 
      3 D. Skibidi Table
      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 Vadim loves filling square tables with integers. But today he came up with a way to do it for fun! Let's take, for example, a table of size $2 \times 2$, with rows numbered from top to bottom and columns numbered from left to right. We place $1$ in the top left cell, $2$ in the bottom right, $3$ in the bottom left, and $4$ in the top right. That's all he needs for fun!
     22 
     23 Fortunately for Vadim, he has a table of size $2^n \times 2^n$. He plans to fill it with integers from $1$ to $2^{2n}$ in ascending order. To fill such a large table, Vadim will divide it into $4$ equal square tables, filling the top left one first, then the bottom right one, followed by the bottom left one, and finally the top right one. Each smaller table will be divided into even smaller ones as he fills them until he reaches tables of size $2 \times 2$, which he will fill in the order described above.
     24 
     25 Now Vadim is eager to start filling the table, but he has $q$ questions of two types:
     26 
     27 * what number will be in the cell at the $x$-th row and $y$-th column;
     28 * in which cell coordinates will the number $d$ be located.
     29 
     30 Help answer Vadim's questions.
     31 
     32 Input
     33 
     34 Each test consists of several sets of input data. The first line contains a single integer $t$ $(1 \leq t \leq 10)$  — the number of sets of input data. The following lines describe the input data sets.
     35 
     36 In the first line of each data set, there is an integer $n$, describing the size of the table $(1 \le n \le 30)$.
     37 
     38 In the second line of each data set, there is an integer $q$  — the number of questions $(1 \le q \le 20\,000)$.
     39 
     40 In the following $q$ lines of each data set, the questions are described in the following formats:
     41 
     42 * -> x y  — What number will be in the cell $(1 \le x, y \le 2^n)$;
     43 * <- d  — In which cell coordinates will the number $(1 \le d \le 2^{2n})$ be located.
     44 
     45 It is guaranteed that the sum of $q$ over all test cases does not exceed $20\,000$.
     46 
     47 Output
     48 
     49 Output the answers to each question on a separate line.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 2
     57 
     58 2
     59 
     60 5
     61 
     62 -> 4 3
     63 
     64 <- 15
     65 
     66 <- 4
     67 
     68 -> 3 1
     69 
     70 -> 1 3
     71 
     72 1
     73 
     74 8
     75 
     76 -> 1 1
     77 
     78 -> 1 2
     79 
     80 -> 2 1
     81 
     82 -> 2 2
     83 
     84 <- 1
     85 
     86 <- 2
     87 
     88 <- 3
     89 
     90 <- 4
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 7
     97 2 3
     98 1 2
     99 9
    100 13
    101 1
    102 4
    103 3
    104 2
    105 1 1
    106 2 2
    107 2 1
    108 1 2
    109 ```
    110 
    111 Note
    112 
    113 This is how the filled table from the first example looks:
    114 
    115  ![](https://espresso.codeforces.com/da748157aec3b2f6a243518e84d255f6a0b8b6c6.png)