Задача из старого ЕГЭ
Medium
Execution time limit is 1 second
Runtime memory usage limit is 64 megabytes
Строки (цепочки цифр) строятся по следующему правилу.
Первая строка состоит из одного символа - цифры "1". Каждая из последующих цепочек создаётся такими действиями: в очередную строку записывается сначала номер строки (без ведущих нулей), а затем два раза приписывается предыдущая строка.
Вот первые 4 строки, созданные по этому правилу:
1
211
3211211
432112113211211
А, например, 11-я строка будет начинаться так:
11. 1110987...
По заданным N и K определите, какая цифра будет стоять в N-ой строке на K-ом месте, либо что длина строки меньше K.
Input
Вводятся два натуральных числа N и K (1 ≤ N ≤ 100000, 1 ≤ K ≤ 10^15).
Output
Определите, какая цифра будет стоять в N-ой строке на K-ом месте и выведите её. Если длина N-ой строки меньше K, выведите -1 (минус один).
Examples
Input #1
Answer #1
Submissions 228
Acceptance rate 9%