codeforces-scrape

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

2053C.md (2842B)


      1 Source: https://codeforces.com/problemset/problem/2053/C
      2 
      3 C. Bewitching Stargazer
      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 I'm praying for owning a transparent heart; as well as eyes with tears more than enough...
     22 
     23 — Escape Plan, [Brightest Star in the Dark](https://www.youtube.com/watch?v=GPnymcrXgX0)
     24 
     25 Iris looked at the stars and a beautiful problem emerged in her mind. She is inviting you to solve it so that a meteor shower is believed to form.
     26 
     27 There are $n$ stars in the sky, arranged in a row. Iris has a telescope, which she uses to look at the stars.
     28 
     29 Initially, Iris observes stars in the segment $[1, n]$, and she has a lucky value of $0$. Iris wants to look for the star in the middle position for each segment $[l, r]$ that she observes. So the following recursive procedure is used:
     30 
     31 * First, she will calculate $m = \left\lfloor \frac{l+r}{2} \right\rfloor$.
     32 * If the length of the segment (i.e. $r - l + 1$) is even, Iris will divide it into two equally long segments $[l, m]$ and $[m+1, r]$ for further observation.
     33 * Otherwise, Iris will aim the telescope at star $m$, and her lucky value will increase by $m$; subsequently, if $l \neq r$, Iris will continue to observe two segments $[l, m-1]$ and $[m+1, r]$.
     34 
     35 Iris is a bit lazy. She defines her laziness by an integer $k$: as the observation progresses, she will not continue to observe any segment $[l, r]$ with a length strictly less than $k$. In this case, please predict her final lucky value.
     36 
     37 Input
     38 
     39 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows.
     40 
     41 The only line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 2\cdot 10^9$).
     42 
     43 Output
     44 
     45 For each test case, output a single integer — the final lucky value.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 6
     53 
     54 7 2
     55 
     56 11 3
     57 
     58 55 13
     59 
     60 5801 6
     61 
     62 8919 64
     63 
     64 8765432 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 12
     71 18
     72 196
     73 1975581
     74 958900
     75 38416403456028
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, at the beginning, Iris observes $[1, 7]$. Since $[1, 7]$ has an odd length, she aims at star $4$ and therefore increases her lucky value by $4$. Then it is split into $2$ new segments: $[1, 3]$ and $[5, 7]$. The segment $[1, 3]$ again has an odd length, so Iris aims at star $2$ and increases her lucky value by $2$. Then it is split into $2$ new segments: $[1, 1]$ and $[3, 3]$, both having a length less than $2$, so no further observation is conducted. For range $[5, 7]$, the progress is similar and the lucky value eventually increases by $6$. Therefore, the final lucky value is $4 + 2 + 6 = 12$.
     81 
     82 In the last test case, Iris finally observes all the stars and the final lucky value is $1 + 2 + \cdots + 8\,765\,432 = 38\,416\,403\,456\,028$.