codeforces-scrape

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

768B.md (2373B)


      1 Source: https://codeforces.com/problemset/problem/768/B
      2 
      3 B. Code For 1
      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 Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility.
     22 
     23 Initially Sam has a list with a single element *n*. Then he has to perform certain operations on this list. In each operation Sam must remove any element *x*, such that *x* > 1, from the list and insert at the same position ![](https://espresso.codeforces.com/19f3313a25e01487b76a1f349881f013a6d5bc47.png), ![](https://espresso.codeforces.com/9e4b81f4486fb40815e4604649896be611e6c3c0.png), ![](https://espresso.codeforces.com/19f3313a25e01487b76a1f349881f013a6d5bc47.png) sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.
     24 
     25 Now the masters want the total number of 1s in the range *l* to *r* (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?
     26 
     27 Input
     28 
     29 The first line contains three integers *n*, *l*, *r* (0 ≤ *n* < 250, 0 ≤ *r* - *l* ≤ 105, *r* ≥ 1, *l* ≥ 1) – initial element and the range *l* to *r*.
     30 
     31 It is guaranteed that *r* is not greater than the length of the final list.
     32 
     33 Output
     34 
     35 Output the total number of 1s in the range *l* to *r* in the final sequence.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 7 2 5
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 4
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 10 3 10
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 5
     61 ```
     62 
     63 Note
     64 
     65 Consider first example:
     66 
     67 ![](https://espresso.codeforces.com/288fbb682a6fa1934a47b763d6851f9d32a06150.png)
     68 
     69 Elements on positions from 2-nd to 5-th in list is [1, 1, 1, 1]. The number of ones is 4.
     70 
     71 For the second example:
     72 
     73 ![](https://espresso.codeforces.com/52e9bc51ef858cacc27fc274c7ba9419d5c1ded9.png)
     74 
     75 Elements on positions from 3-rd to 10-th in list is [1, 1, 1, 0, 1, 0, 1, 0]. The number of ones is 5.