Разбор задачи B6 (демо ЕГЭ 2005)
В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдушая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i).
Для удобства в скобках пишется номер строки (начиная с 0).
Ниже показаны первые строки, сформированные по описанному правилу:
(0) 0
(1) 001
(2) 0010012
(3) 001001200100123
Какая цифра стоит в последней строке на 123-м месте (считая слева направо)?
Введем обозначение: "001001200100123"-().
Распишем, какие будут созданы строки с № от 4-х до 6-и.
(4) ()() 4
(5) ()()4 ()()4 5
(6) ()()4 ()()4 5 ()()4 ()()4 5 6
Чтобы определить позицию цифры, нужно определить сколько цифр образуется в каждой строке. Количество цифр определяется по формуле:
Ni=2i+1−1,
где i-№ строки.
В 6-й строке образуется N6=26+1−1=27−1=127 символов:
(6) ()()4 ()()4 5 ()()4 ()()4 5 6127
Нам нужно найти место 123. Расставим позиции:
(6) ()()4 ()()4 5 ()()4 ()()1244125 5126 6127
Видно, что элемент в позиции 123 нужно смотреть в ():
001001200100121233124
Получили 2.