Условие: Последовательность 1001011001101001... строится так: сначала пишется 1, затем повторяется такое действие: уже написанную часть приписывают справа с заменой элемента 0 на 1 и наоборот, т.е. 1->10->1001->10010110->... Требуется написать программу, вычисляющую n-ый член этой последовательности по заданному n<=2147483647.
Технические условия: Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных: Входной файл INPUT.TXT содержит n.
Формат выходных данных: В выходной файл OUTPUT.TXT вывести найденную цифру.
Примеры входных и выходных файлов: Input.txt 6
Output.txt 1
Решение: ---------- cut ---------- Эта задача предлагалась на олимпиадах школьников различных регионов России еще в конце 80 годов уже прошлого века. Ее решение осуществляется методом возврата. Пусть на искомом месте стоит 0. Определим, откуда и из чего получилось это значение при указанных в условии задачи построениях. Это продолжаем до тех пор, пока не возвратимся к началу построения (вначале пишется 1). Если найденное нами значение совпадает с 1, значит на искомом месте действительно стоит 0, а иначе там 1. ---------- cut ----------
var n, p : longint; t : byte; f, g : text; begin assign(f,'input.txt'); reset(f); read(f,n); if n>1073741824 then p:=1073741824 else if n>536870912 then p:= 536870912 else begin p:=1; while p<n do p:=p*2; p:=p div 2 end; t:=0; while n>1 do begin t:=1-t; n:=n-p; while p>=n do p:=p div 2 end; assign(g,'output.txt'); rewrite(g); write(g,1-t); close(g) end.
