Задача. Гірлянда

Задача. Гірлянда

Новорічну ялинку прикрашено гірляндою нескінченної довжини, що складається з послідовно з'єднаних лампочок. Коли гірлянду вмикають, загоряється лише перша лампочка, рахуючи від вимикача, яка горить одну секунду. Далі гірлянда починає мигати за таким правилом. Щосекунди для кожної лампочки перевіряється умова: якщо рівно одна із її сусідніх лампочок горить, то ця лампочка буде горіти на наступній секунді; інакше – не буде горіти. Перша лампочка має лише одну сусідню.

Завдання

Напишіть програму GARLAND, яка за номером секунди знаходить кількість лампочок гірлянди, що будуть горіти протягом цієї секунди.

Вхідні дані

Єдиний рядок вхідного файлу GARLAND.DAT містить одне ціле число N (1≤N≤10⁹) – номер секунди.

Вихідні дані

Єдиний рядок вихідного файлу GARLAND.SOL має містити ціле число – кількість лампочок, що будуть горіти на секунді N.

Приклад вхідних та вихідних даних

GARLAND.DAT	GARLAND.SOL
5	2

Опис тестів до задачі garland
№	N	бітів у N	1-бітів у N	Відповідь	Розв'язок за O(logN)	Розв'язок за O(N^2)
1	1	1	1	1	+	+
2	7	3	3	4	+	+
3	20	5	2	2	+	+
4	105	7	4	8	+	+
5	1023	10	10	512	+	+
6	25860	15	5	16	+	−
7	520511	19	14	8192	+	−
8	16621499	24	19	262144	+	−
9	67149824	27	3	4	+	−
10	536600575	29	27	67108864	+	−

Розв′язання. Мовою Паскаль.

Var fi,fo:text;

    i,j,k,l,m,n:longint;

    a:array[1..4] of longint;

Begin

 readln(n);

 a[1]:=1;

 a[2]:=2;

 a[3]:=2;

 a[4]:=4;

 i:=1;

 l:=0;

 while i<n do begin

  i:=i*2+1;

  inc(l);

 end;

 if n<>1 then begin

  i:=(i-1)div 2;

  m:=n-i;

  k:=1;

  for i:=1 to l do k:=k*2;

  while k>4 do begin

   l:=(k div 4);

   j:=1;

   if m>l then inc(j);

   if m>(2*l) then inc(j);

   if m>(3*l) then inc(j);

   i:=a[j];

   a[1]:=i;

   a[2]:=2*i;

   a[3]:=2*i;

   a[4]:=2*2*i;

   k:=k div 4;

   dec(j);

   m:=m-(l*j);

  end;

  m:=a[m];

  writeln(m);

  end else writeln('1');

 End.