Plus
Pin


Problem description Progress
ID 34956. Binary strings of given length
Темы: Bit operations   

Given number N print all strings of length N consisting of zeros and ones in lexicographic order.

In solving the problem, use enumeration of all subpatterns.

Input

Single number N is given. (natural, 1 ≤ N ≤ 10)

Output

It is necessary to print all strings of length N consisting of zeros and ones in lexicographic order, one per line

Input Output
2
00
01
10
11
 

ID 34957. Binary strings of given length in reverse order
Темы: Bit operations   

Given number N print all strings of length N consisting of zeros and ones in reverse lexicographical order.

In solving the problem, use enumeration of all subpatterns.

Input

Single number N specified. (1 ≤ N ≤ 10)

Output

It is necessary to output all strings of length N consisting of zeros and ones in reverse lexicographical order.

Input Output
2
eleven
10
01
00
 

ID 29641. Quiet Don №1
Темы: Bit operations   

In peacetime, the Cossacks are engaged in agriculture. Pantelei Prokofievich Melekhov grows special mathematical vegetables that grow according to very strange rules: each seed i of these vegetables has a yield value ai, and the yield of the entire garden bed is the product of the yields of all the seeds planted on it. Melekhov has N seeds. Help him choose a few of these seeds so that when planting these seeds, the yield of the garden bed is maximum.
 
Input:
The first line contains the number N (1 <= N <= 15)
Second - N numbers ai, possibly real (|ai| < 10)
 
Output:
Output the maximum yield of the bed, to at least 6 decimal places, that can be achieved with the given set of seeds. It is guaranteed that it is greater than 1.
 
Input Output
5
2.0 -1.2 4.7 -2.9 -1.1
32.712000

(с) Grigoriev E., 2018

ID 38513. Equations of Mathematical Magic
Темы: Case Study    Bit operations   

Colossal! — exclaimed the hunchback. — Programmer! We need a programmer.
Arkady and Boris Strugatsky, Monday starts on Saturday
Studying the book "Equations of Mathematical Magic" Roman Oira-Oira and Cristobal Junta discovered an interesting equation: a−(a⊕x)−x=0 for a given a, where   ⊕   stands for bitwise exclusive OR (XOR) of two numbers (this operation is denoted as ^ or xor in many modern programming languages). Since this equation was intended to be solved on the Aldan-3 machine, all calculations were performed on non-negative integers modulo 232. Oira-Oira quickly found x, which is a solution, but Cristobal Junta found Oira-Oira's result not interesting enough, so he asked a colleague how many solutions there are to this equation. Since all calculations are done modulo 232, Cristobal Junto is interested in the number of solutions x such that 0 ≤ x≤ 232. Such a task turned out to be too difficult for Oira-Oira, so he turned to you for help.

Input
The first line contains a single integer a (0 ≤ a ≤ 232−1).

Imprint
Print a single integer — the number of non-negative solutions of the equation.

Note
Let's define the bitwise OR (XOR) operation. Let two non-negative integers x and y be given, consider their binary representations (possibly with leading zeros): xk...x2x1x0 and yk...y2y1y0 . Here xi is the i-th bit of x and yi is the i-th bit of y. Let r=x⊕y — the result of an XOR operation on the numbers x and y. Then the binary representation of r is rk...r2r1r0, where:

\(r_i = \begin{cases} 1, & \quad \text{if } x_i \neq y_i \\ 0 , & \quad \text{if } x_i = y_i \end{cases} \)

In the first example, the solutions to the equation are 0 and 2147483648=231, because 0−(0⊕0)−0=0−0−0=0 and 0−(0⊕ 2147483648)− 2147483648=−4294967296=−232=0 modulo 232.

In the second example, the solutions to the equation are 0, 2, 2147483648=231 and 2147483650=231+2.

In the third example, the solutions are all x for which 0 ≤ x≤ 232.
 
Examples
# Input Output
1 0 2
2 2 4
3 4294967295 4294967296

ID 39385. XOR World
Темы: Bit operations   

Let \(F(A, B) = A \oplus (A+1) \oplus (A+2) \oplus ... \oplus B\) , where \(\oplus\)  is the exclusive OR operation (XOR).
Given the known numbers A and B calculate F(A, B).

Input
The input is a string containing 2 numbers: A and B (0 <= A, B <= 10 12).

Imprint
Output F(A, B). 
 

Examples
# Input Output
1 2 4 5
2 123 456 435
3 123456789012 123456789012 123456789012

ID 44386. And Ka
Темы: Bit operations   

Gromozeka studies bit operations. Today he will learn the bitwise AND operation (&). Now he was wondering what is the largest integer value of k that will satisfy the condition written below.
 

x & (x - 1) & (x - 2) & ... & k = 0

Input
The first line of the input contains an integer t (1 <= t <= 3*104) - the number of integers x for which you want to find the answer. Next, the program receives t lines, each of which contains one integer x (1<= x <= 10< sup>9). 

Imprint
For each x value, on a separate line print the largest integer k value that will satisfy the problem condition.
 
 
Examples
# Input Output
1 3
2
5
17
1
3
15

ID 44387. XOR hash
Темы: Bit operations   

 Gromozeka has n-1 integers written on cards and laid out in a row in random order. It computed a bitwise XOR (xor) between all the numbers written. The calculated number (X) he wrote down on a new card and added it to the end of all cards with numbers. Now he has n number cards. He shuffled all the cards and arranged them again in a row in random order. 

Gromozeka showed you all the cards and asks you to guess the number X that was written on the new card.

Input
The first line of the input contains an integer n - the number of cards with numbers (2 <= n <= 100). The second line contains n integers - the numbers written on the cards (each number belongs to the interval [0, 127]). 

Imprint
Print the answer one integer - the number X that was written on the new card.
It is guaranteed that the answer exists. If there are multiple answers, print the minimum X.
 
 

Examples
# Input Output
1 4
4 3 2 5
2

ID 44389. Wizard ORZ
Темы: Bit operations   

The ORZ Wizard loves to conjure numbers. You decided to test its strength and gave it an array a consisting of n integers, as well as an integer z. The numbering of array elements starts from 1.

The ORZ wizard performs the following operation any number (possibly zero) times:

  • It selects an integer i such that 1<= i <= n. Then he whispers a spell and after that at the same time the number  ai turns into a number equal to (a i or z), and the number z turns into a number equal to (ai and z). 


Here or and and denote the bitwise OR and bitwise AND operations, respectively.

Find the maximum possible value of the maximum element in the array a after some (possibly zero) number of transformations.


Input
The first line of the input contains two integers: n and z (1 <= n <= 2000, 0 <= z < 230). The second line of the input contains n integers: a1a2,...,an (0 <= a<230). It is guaranteed that the sum of n  values ​​over all test cases does not exceed 104.

Imprint
Print the answer to the problem.
 
 
Examples
# Input Output Note
1 2 3
3 4
7

One of the optimal sequences of actions is the following:

  • Perform operation on i = 1. Now a1 becomes (3 or 3) = 3 and z becomes (3 and 3) = 3.
  • Perform operation for i = 2. Now a2 becomes (4 or 3) = 7, and z becomes equal to (3 and 3) = 0.
  • Perform operation on i = 1. Now a1 becomes (3 or 0) = 3 and z becomes (3 and 0) = 0.

After these operations, the sequence a becomes equal to [3,7], and the maximum value in it is equal to 7. It can be proved that the maximum value in a cannot exceed 7 in any sequence of operations, so the answer is 7.

2 5 5
0 2 4 6 8
13  

ID 44507. Max XOR - 2
Темы: Bit operations   

Two numbers a and b are written in hexadecimal notation. Both entries are of length n. You can swap two adjacent digits as many times as you like in any of the numbers. What is the maximum value the result of applying the bitwise operation XOR to the numbers obtained after applying such permutations?

This operation is defined on the binary representation of numbers.

Let's define the bitwise XOR operation (XOR). Let two integer non-negative binary numbers x and y of length k (possibly with leading zeros) be given: < code>xk-1...x2x1x0  and yk-1...y2y1y0. Here xi is ith bit of x and y i is the ith bit of y. Let r = x XOR y - result of XOR operation on numbers x and y< /code>. Then the binary notation r will be rk-1...r2r1r0, where:  

\(r_i = \begin{cases} 1, ~ \text{if} ~ x_i ~ \neq ~ y_i \\ 0 , ~ \text{if} ~ x_i ~ = ~ y_i \end{cases}\)



Input

The first line contains a single integer n (1 <= <= 100000) - the length of the numbers. The second line contains the number entry a. The third line contains the number b.

The letters A, B, C, D, E, F represent the numbers 10, 11, 12,  ;13, 14, 15 in hexadecimal, respectively. Entries can contain leading zeros.


Output

In a single line, you need to print one hexadecimal number of length n, which is the answer to the question from the condition.


Note

In the first example, you can swap two adjacent digits in the first number, you get F0 XOR 0E = FE.

In the second example, any permutation of the digits does not change a  XOR  b. Please note that the length of the output number must be equal to  n, so you must print leading zeros.

In the third example, you can get 101010 from a and 010100 from b.

 
Examples
# Input Output
1
2
0F
0E
FE
2
3
000
000
000
3
6
010110
011000
111110

ID 34915. 2^n+2^m
Темы: Bit operations   

Find the sum of two different powers of 2 using only bitwise operations. In particular, you cannot use the addition operation.

Input: Two unequal numbers are given: n and m, not exceeding 31.
Output: Display the value of the sum 2n+2m.< br />
Examples
# Input Output
1 1 2 6

ID 44570. 2^k
Темы: Bit operations   

Write a program that, given a number k (0 <= k <= 31), displays the number 2k , that is, a number whose k-th bit is 1, and the rest are  zeros.

Arithmetic operations cannot be used in the program, only bit operations must be used!
 

Examples
# Input Output
1 5 32

ID 44571. Minimum OR amount
Темы: Bit operations   

Gromozeka wrote down n numbers on a piece of paper ai. It then performs the following operation on the array

  • selects two distinct integers i, j (1 <= i < j <= n) and  ;replaces ai to x and aj to y. In order not to break the array, Gromozeka should make sure ai|aj=x|y, where |< /code> denotes bitwise OR. Note that x and y are non-negative integers.

Gromoseka wants to determine the minimum sum of array elements that he can get after performing the above operation any number of times. Since Gromozeka needs to go on his next space journey as soon as possible, he asks for your help!


Input

The  first line of the  input contains an integer n (2 <= n <= 100) -  nbsp;nbsp;nbsp;nbsp; leaf. The second line of the input contains n integers a1,a2,…,an (0<=ai<= 230).


Output

Print the minimum possible sum of the array.



Examples
# Input Output
1
3
1 3 2
3
2
5
1 2 4 8 16
31
3
2
6 6
6
4
3
3 5 6
7
 

ID 44572. Set the beat
Темы: Bit operations   

Write a program that sets 1 to the kth bit of the  N. Display the resulting number.

Arithmetic operations cannot be used in the program, only bit operations must be used!
 

Input

Given an integer N and a natural number k.


Output

Display the number obtained after setting the given bit to 1.

 

Examples
# Input Output
1 5 1 7
 
 

ID 44573. Invert the bit
Темы: Bit operations   

Write a program that inverts the kth bit of a  N. Display the resulting number.

Arithmetic operations cannot be used in the program, only bit operations must be used!
 

Input

Given an integer N and a natural number k.


Output

Display the number obtained after inverting the given bit.

 

Examples
# Input Output
1 5 2 1
 

 

ID 44574. Reset the beat
Темы: Bit operations   

Write a program that resets (sets to 0) the kth bit of a  N. Display the resulting number.

Arithmetic operations cannot be used in the program, only bit operations must be used!
 

Input

Given an integer N and a natural number k.


Output

Display the number obtained after resetting the given bit.

 

Examples
# Input Output
1 5 2 1
 


 

ID 44575. Reset all beats except the last
Темы: Bit operations   

Write a program that resets (sets to 0) all bits of N except the last k bits.  Display the resulting number.

Arithmetic operations cannot be used in the program, only bit operations must be used!

Input

Given an integer N and a natural number k.


Output

Display the number obtained after the bits have been reset.

 

Examples
# Input Output
1 5 1 1
 


 

ID 44576. Determine the value of a bit
Темы: Bit operations   

Write a program that determines the k-th bit of  N

Arithmetic operations cannot be used in the program, only bit operations must be used!
 

Input

Given an integer N and a natural number k.


Output

Display the value of the given bit (0 or 1).

 

Examples
# Input Output
1 5 1 0
 


 

ID 44577. Byte bit by bit
Темы: Bit operations   

Write a program that prints out all the bits of an 8-bit number  N
 

Input

Given an integer N (0 <= N <= 255).


Output

Print a number  N in bit form: 8 bits, high bits on the left, low bits – right.

 

Examples
# Input Output
1
5
00000101
 


 

ID 44578. Fast multiplication
Темы: Bit operations   

Numbers a and b are given. Without using the operations *///% calculate them work.
 

Input

Given two numbers a and b.


Output

Print the product of numbers a and b.

 

Examples
# Input Output
1 5 2 10

ID 44579. Set low bit to zero
Темы: Bit operations   

Given a number, replace the low zero bit (first zero from the right) by one.

Branches and loops are prohibited. 
 

Input

The program receives a non-negative number a.


Output

Print the resulting number.

 

Examples
# Input Output
1 0 1
2 5 7

ID 44580. Reset low unit
Темы: Bit operations   

Given a number, reset the lower non-zero bit (i.e. replace the first one from the right to zero).

Branches and loops are prohibited. 
 

Input

A single non-negative number a.


Output

Print the resulting number.

 

Examples
# Input Output
1 1 0
2 5 4
 

ID 44583. Max XOR
Темы: Bit operations   

The two numbers a and b are written in binary. Both entries are of length 2n. Both entries are divided into  n blocks of 2 adjacent numbers. In each of the numbers, you can swap two arbitrary blocks as many times as you like. What is the maximum value the result of applying the bitwise XOR operation to the resulting numbers can have?

Let's define the bitwise XOR operation (XOR). Let two integer non-negative binary numbers x and y of length k (possibly with leading zeros) be given: < code>xk-1...x2x1x0  and yk-1...y2y1y0. Here xi is ith bit of x and y i is the ith bit of y. Let r = x XOR y - result of XOR operation on numbers x and y< /code>. Then the binary notation r will be rk-1...r2r1r0, where:  

\(r_i = \begin{cases} 1, ~ \text{if} ~ x_i ~ \neq ~ y_i \\ 0 , ~ \text{if} ~ x_i ~ = ~ y_i \end{cases}\)



Input

The first line contains a single integer n (1 <= <= 100000) - number of blocks of two digits in both numbers. The second line contains the number entry a. The third line contains the number b.

For convenience, the blocks are separated by the symbol "|".


Output

In a single line, you need to print one binary number from n blocks, which is the answer to the problem, in the same block format as the given numbers a and b.


Note

In the first example, you can swap two adjacent blocks in the first number, you get 11|00  XOR  00|10=11|10.

In the second example, any permutation of digits does not change a  XOR  b. Please note that the length of the output number must consist of n blocks, so you must print blocks of leading zeros.

In the third example, you can get 101001 from a and 010100 from b.

 

Examples
# Input Output
1
2
00|11
00|10
11|10
2
3
00|00|00
00|00|00
00|00|00
3
3
10|10|01
00|01|01
11|11|01