Solved by 64 users: ...
UserDateAttemptTimeCMSC
WsemirZ`21 mar 2009`Kylix1200.0182
WsemirZ`21 mar 2009`Kylix900.0188
JohnJones_001`01 may 2006`Python100.06112
Huang_SR`04 jul 2006`Python100.06118
stevengao`16 nov 2006`FPC100.01131
seshaoqi`25 jan 2004`FPC1?.??131
beiyz`20 feb 2004`FPC3?.??141
bloodmage`17 apr 2006`Python100.07160
armageddon1988`30 jul 2008`C++600.01177
armageddon1988`30 jul 2008`C++500.01178
avg79`14 jan 2017`C++300.01183
gaoyihan`29 nov 2007`C++100.02184
 C++ 26 FPC 17 Java 6 Kylix 6 C 5 Python 4
` >  >  >  >  >  >  >  >  >  > `

## 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

 © acm.mipt DevGroupThe page was generated in 190ms