codeforces-scrape

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

1999E.md (1345B)


      1 Source: https://codeforces.com/problemset/problem/1999/E
      2 
      3 E. Triple Operations
      4 
      5 time limit per test
      6 
      7 1 second
      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 On the board Ivy wrote down all integers from $l$ to $r$, inclusive.
     22 
     23 In an operation, she does the following:
     24 
     25 * pick two numbers $x$ and $y$ on the board, erase them, and in their place write the numbers $3x$ and $\lfloor \frac{y}{3} \rfloor$. (Here $\lfloor \bullet \rfloor$ denotes rounding down to the nearest integer).
     26 
     27 What is the minimum number of operations Ivy needs to make all numbers on the board equal $0$? We have a proof that this is always possible.
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     32 
     33 The only line of each test case contains two integers $l$ and $r$ ($1 \leq l \lt r \leq 2 \cdot 10^5$).
     34 
     35 Output
     36 
     37 For each test case, output a single integer — the minimum number of operations needed to make all numbers on the board equal $0$.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 
     46 1 3
     47 
     48 2 4
     49 
     50 199999 200000
     51 
     52 19 84
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 5
     59 6
     60 36
     61 263
     62 ```
     63 
     64 Note
     65 
     66 In the first test case, we can perform $5$ operations as follows: $$ 1,2,3 \xrightarrow[x=1,\,y=2]{} 3,0,3 \xrightarrow[x=0,\,y=3]{} 1,0,3 \xrightarrow[x=0,\,y=3]{} 1,0,1 \xrightarrow[x=0,\,y=1]{} 0,0,1 \xrightarrow[x=0,\,y=1]{} 0,0,0 .$$