005. Следующее число

(Время - 1 сек., память - 16 Мб)

Задано натуральное число N.

Требуется написать программу, которая найдет следующее за ним число, в двоичном разложении которого столько же единиц, сколько в двоичном разложении числа N.

Входные данные

В единственной строке входного файла input.txt записано одно натуральное число N (1  N  230).

Выходные данные

В единственную строку выходного файла output.txt нужно вывести одно число – следующее за заданным, в двоичном разложении которого столько же единиц.

Примеры

input.txt

output.txt

1

1

2

2

2

4

3

3

5

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2007-2008 уч. год, 2-й тур

Тематика

Целочисленная арифметика

Примерная сложность

36%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=318

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  А.В. Алексеев, 26.04.2012

 

Разбор

Найдем двоичное разложение заданного числа. Просматривая его слева направо, пропускаем нули, первую единицу заменяем нулем, также далее следующую группу единиц заменяем нулями, подсчитывая количество таких замен, первый встретившийся ноль заменяем на единицу, справа дописываем подсчитанное количество единиц.

Программа на Паскале

{Автор программы - А.В.Алексеев,  дата написания - 23.04.2012}

var

  n : longint;

  i, k, j : integer;

  a : array [1..32] of integer;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(n); k:=0;

  while n>0 do

  begin k:=k+1; a[k]:=n mod 2; n:=n div 2 end;

  i:=1; while a[i]=0 do i:=i+1;

  a[i]:=0; i:=i+1; j:=0;

  while a[i]=1 do begin a[i]:=0; i:=i+1; j:=j+1 end;

  a[i]:=1; if i>k then k:=i;

  for i:=1 to j do a[i]:=1;

  if k=32 then write('2147483648') else

  begin

    for i:=k downto 1 do n:=n*2+a[i];

    write(n)

  end

end.

Программа на С