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 .$$