printРабочее место участника

printЗадачи

1779. Задача из старого ЕГЭ

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Строки (цепочки цифр) создаются по следующему правилу.
Первая строка состоит из одного символа – цифры 1. Каждая из последующих цепочек создается такими действиями: в очередную строку записывается сначала номер строки (без ведущих нулей), а затем два раза приписывается предыдущая строка.
Вот первые 4 строки, созданные по этому правилу:
  • 1
  • 211
  • 3211211
  • 432112113211211
А, например, 11-я строка будет начинаться так: 1110987…
По заданным `N` и `K` определите, какая цифра будет стоять в `N`-ой строке на `K`-ом месте, либо что длина строки меньше `K`.
Вводятся два натуральных числа `N` и `K` (`1\ ≤\ N\ ≤\ 100000`, `1\ ≤\ K\ ≤\ 10^15`).
Определите, какая цифра стоит в `N`-ой строке на `K`-ом месте и выведите ее. Если длина `N`-ой строки меньше `K`, выведите `-1` (минус один).

Пример ввода 1

3 2

Пример вывода 1

2

Пример ввода 2

11 4

Пример вывода 2

0

Пример ввода 3

2 25

Пример вывода 3

-1
Источник: Московская открытая олимпиада школьников по программированию, 2011/12 учебный год
loading