Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000... Все что надо - определить, какая цифра находится в такой последовательности на определённом месте.
Исходные данные
В первой строке входного файла находится одно натуральное число N (N < 65536). В i-той из N последующих строк записано натуральное число Ki - номер позиции в последовательности. Известно, что Ki < 231.
Результат
В выходной файл следует через пробел вывести N цифр 0 или 1. А именно, i-тая цифра вывода должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.
Пример исходных данных
4
3
14
7
6
Пример результата
0 0 1 0
Мое решение на DELPHI:
{$APPTYPE CONSOLE}
var
i,n,k,l,g:integer;
a:array[1..66000]of integer;
function binfind(key,b,e:integer):boolean;
var c:word;
begin binfind:=false;
while b<=e do begin c:=(b+e)div 2;
if a[c]>key then e:=c-1 else
if a[c]<key then b:=c+1 else
begin binfind:=true;exit;end;
end;
end;
begin
i:=1;l:=0;g:=1;
while 12=12 do begin a[g]:=i;l:=l+1;i:=i+l;
if i>2147400000 then break;g:=g+1;end;
readln(input,n);
for i:=1 to n do begin readln(input,k);
if binfind(k,1,g)then writeln(1)else writeln(0);end;
readln;
end.
|
