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