FreeOberon/Programs/FunGame.Mod

MODULE FunGame;
IMPORT Texts, Out;

PROCEDURE LastBit(x: INTEGER): INTEGER;
VAR k: INTEGER;
BEGIN k := 1;
  WHILE k <= x DO k := k * 2 END
RETURN k DIV 2 END LastBit;

PROCEDURE Rotate(x, k: INTEGER): INTEGER;
RETURN x DIV 2 + ORD(ODD(x)) * k END Rotate;

PROCEDURE Parse(x: INTEGER): INTEGER;
VAR x0, k, max: INTEGER;
BEGIN
  x0 := x; max := x;
  k := LastBit(x); (* k - максимальная степень двойки такая, что k <= x *)
  REPEAT
    x := Rotate(x, k);
    Out.Int(x, 10); Out.Ln;
    IF x > max THEN max := x END
  UNTIL x = x0
RETURN max END Parse;

PROCEDURE Do;
VAR T: Texts.Text;
  S: Texts.Scanner;
  W: Texts.Writer;
  n: INTEGER;
BEGIN
  NEW(T); Texts.Open(T, 'fungame.in'); Texts.OpenScanner(S, T, 0);
  Texts.Scan(S); n := S.i;
  n := Parse(n);
  Texts.Open(T, ''); Texts.OpenWriter(W);
  Texts.WriteInt(W, n, 0); Texts.WriteLn(W);
  Texts.Append(T, W.buf); Texts.Close(T, 'fungame.out')
END Do;

BEGIN
  Do
END FunGame.


                  Забавная игра
                  ~~~~~~~~~~~~~

Задача D заочного тура Московской олимпиады по программированию, 2003.

Время на тест - 1 секунда.

Легендарный учитель математики Юрий Петрович придумал забавную игру с
числами. А именно, взяв произвольное целое число, он переводит его в двоичную
систему счисления, получая некоторую последовательность из нулей и единиц,
начинающуюся с единицы (Например, десятичное число 19 в двоичной системе
запишется как 10011). Затем учитель начинает сдвигать цифры полученного
двоичного числа по циклу (так, что последняя цифра становится первой, а все
остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом
последовательности из нулей и единиц в столбик - он подметил, что независимо
от выбора исходного числа получающиеся последовательности начинают с
некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает
максимальное из выписанных чисел и переводит его обратно в десятичную систему
счисления, считая это число результатом проделанных манипуляций. Так, для
числа 19 список последовательностей будет таким:

     10011
     11001
     11100
     01110
     00111
     10011

и результатом игры, следовательно, окажется число 28 (11100[2]). Поскольку
придуманная игра с числами все больше занимает воображение учителя, отвлекая
тем самым его от работы с ну очень одаренными школьниками, вас просят
написать программу, которая бы помогла Юрию Петровичу получать результат игры
без утомительных ручных вычислений.

Входные данные:
  Программа получает на вход единственное натуральное число,
  не превосходящее 10^9.

Выходные данные:
  Программа должна вывести единственное натуральное число - результат игры.