743B.md (1672B)
1 Source: https://codeforces.com/problemset/problem/743/B 2 3 B. Chloe and the sequence 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 Chloe, the same as Vladik, is a competitive programmer. She didn't have any problems to get to the olympiad like Vladik, but she was confused by the task proposed on the olympiad. 22 23 Let's consider the following algorithm of generating a sequence of integers. Initially we have a sequence consisting of a single element equal to 1. Then we perform (*n* - 1) steps. On each step we take the sequence we've got on the previous step, append it to the end of itself and insert in the middle the minimum positive integer we haven't used before. For example, we get the sequence [1, 2, 1] after the first step, the sequence [1, 2, 1, 3, 1, 2, 1] after the second step. 24 25 The task is to find the value of the element with index *k* (the elements are numbered from 1) in the obtained sequence, i. e. after (*n* - 1) steps. 26 27 Please help Chloe to solve the problem! 28 29 Input 30 31 The only line contains two integers *n* and *k* (1 ≤ *n* ≤ 50, 1 ≤ *k* ≤ 2*n* - 1). 32 33 Output 34 35 Print single integer — the integer at the *k*-th position in the obtained sequence. 36 37 Examples 38 39 Input 40 41 ``` 42 3 2 43 ``` 44 45 Output 46 47 ``` 48 2 49 ``` 50 51 Input 52 53 ``` 54 4 8 55 ``` 56 57 Output 58 59 ``` 60 4 61 ``` 62 63 Note 64 65 In the first sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1]. The number on the second position is 2. 66 67 In the second sample the obtained sequence is [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]. The number on the eighth position is 4.