<ПРЕД Задача:
СЛЕД>
Задачу решили 64 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Вычисление XOR через AND.

Time limit = 5 секунд(ы)

Вам нужно написать программу, которая умеет вычислять целочисленную функцию f(n) натурального аргумента для n = 1, 2, ..., 500.

f(n) < n. Она определяется следующим образом.

Функции AND и XOR — это известные элементарные булевы функции, которые два бита отображают в один:

x1  x2   AND(x1,x2)
0   0    0
0   1    0
1   0    0
1   1    1

x1  x2   XOR(x1,x2)
0   0    0
0   1    1
1   0    1
1   1    0

Функция AND2 --- это операция AND для двух пар бит. Повитовый AND двух байт, это операция, которая два байта отображает в один и обозначается как AND8. Вообще ANDn --- это побитовый AND двух бинарных слов длины n. Соответственно XORn — это побитовый XOR двух бинарных слов длины n.

Пусть g1:A1B1 и g2:A2B2 --- две конечные функции (то есть g1 — это функция, аргумент которой есть элемент множества A1, а значение функции принадлежит конечному множеству B1).

Определение 1.
Будем говорить, что одна функция g2 вычислется через другую функцию g1, если есть две функции hin:A2A1 и hout:B'1B2:

g2 = hout · g1 · hin

или, в других обозначениях:

g2(x) = hout( g1 (hin( x ) ) ) )

Причем, каждая из функций hout и hin для разных значений аргумента возвращает разные значения. При этом hout определена только на тех значениях аргумента, которые могут к ней прийти как результат выполнения функции g1(hin(x)) с x из множества A2, то есть

B'1 = g1(hin(A2)).

Определение 2.
Функция f(n) это такое максимальное число m, что

XORm может быть вычислена через ANDn

Вход Одна строчка с натуральным числом n < 501.

Выход Одна строчка с числом f(n).

Вход#1
1
Выход#1
0

Вход#2
2
Выход#2
1

Вход#3
10
Выход#3
8

Автор:
Ворожцов Артем
18 мая 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 3.228.220.31