<PREV Problem:
NEXT>
Solved by 64 users: ...
UserDateAttemptTimeCMSC
WsemirZ21 mar 2009Kylix1200.0182 
WsemirZ21 mar 2009Kylix900.0188 
JohnJones_00101 may 2006Python100.06112 
Huang_SR04 jul 2006Python100.06118 
stevengao16 nov 2006FPC100.01131 
seshaoqi25 jan 2004FPC1?.??131 
beiyz20 feb 2004FPC3?.??141 
bloodmage17 apr 2006Python100.07160 
armageddon198830 jul 2008C++600.01177 
armageddon198830 jul 2008C++500.01178 
avg7914 jan 2017C++300.01183 
gaoyihan29 nov 2007C++100.02184 
Languages
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

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


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

SW soft NIX
ID = 35.168.111.191