<PREV Problem:
NEXT>
Solved by 64 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Calculating XOR via AND

Time limit = 5 second(s)

Your program should be capable of calulating function f(n), for n=1,2, ..., 500.

f(n) is integer number less than n. It shows how many XOR's can be calculated via ANDn.

It is defined in the following way. AND and XOR are wellknown boolean operations with two bits:

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

The function AND maps the set {00, 01, 10, 11} to the set {0,1}. Functions AND2 is AND function of two bit pares.

It maps the set {{00,00}, {00, 01}, {00, 10}, {00,11}, {01,00}, {01, 01}, {01, 10}, {00,11}, ...} of size 16 to the set {00,01,10,11} of size 4.

Bitwise AND of two bytes is AND8. So ANDn denotes direct product of n functions AND (bitwise AND of two n-bit words). XORn denotes direct product of n functions XOR.

Definition 1.

Lets g1:A1B1 and g2:A2B2 be two maps, where A1, A2, B1, B2 are finite sets.

Function g2 can be calculated via g1 iff there are two functions hin: A2A1 and hout: B'1B2 :

g2 = hout · g1 · hin

in another notation:

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

Here hin and hout are injection functions. The domain B'_1 of the function hout is the image of A2 for the map g1 · hin:

B'1 = g1 ( hin(A2) )
Injection function returns different results for different arguments.

Definition 2.
f(n) is the maximum value of m :

XORm can be calculated via ANDn

Input One line with positive integer number less than 501.

Output One line with integer number f(n).

Input#1
1
Output#1
0

Input#2
2
Output#2
1

Input#3
10
Output#3
8

Author:
Voroztsov Artem
18 May 2003

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 54.198.246.116