meet in the middle

Plus

Problem description Progress

ID 28324. Palindromic Paths

Темы: Bust meet in the middle

John's farm is represented by a grid of N×N fields (2≤N≤18), each labeled with a letter of the alphabet. For example,

ABCD

BXZX

CDXB

WCBA

Every day Besi the cow goes from the upper left corner to the lower right, moving either one cell to the right or one cell down. Besi writes down the string that results from her route, built from the letters she walked. She will be very upset if the resulting string turns out to be a palindrome (it reads the same from beginning to end and from end to beginning), because she will get confused in which direction she went.

Please help Besie figure out how many different palindromes she can form during her journey. Different ways to form the same palindrome should only be counted once. For example, in the example above, there are several ways to form the palindrome ABXZXBA, but there are only 4 different palindromes that Besi can form ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

INPUT FORMAT :

The first line of input contains N and subsequent N lines contain N< /strong> field description. Each line contains N characters in the range A..Z.

OUTPUT FORMAT :

Print the number of distinct palindromes Besi can form.

Input Output

4

ABCD

BXZX

CDXB

WCBA
4

ID 39835. Modulo maximum subsequence

Темы: meet in the middle

Given an array A consisting of n positive integers and a number m. Select the sequence of positions B ₁, B₂, ..., B_k (1 <= B₁ < B₂ < ... < B_k <= n) such that ; \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) was the maximum (that is, so that the remainder of dividing the sum of the elements of the subsequence by the number m is the maximum possible). The selected sequence can be empty.
Calculate the maximum possible value of \((\sum_{i=1}^{k} A_{B_i}) mod \; m\).

Input
The first line contains two integers n and m (1 <= n <= 35, 1 <= m <= 10^{9). The second line contains n integers A₁, A₂< /code>, ..., A_n (1 <= A_i <= 10⁹ )

Imprint

Output one number - the maximum value \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)}

`Examples`






#
Input
Output




1
4 4

5 2 4 1
3


2
3 20

199 41 299
19



 

Explanations
In the first example, you can choose B = {1, 2}. (A₁ + A₂) mod m = (5 + 2) % 4 = 3.

In the second example, you can select B = {3}.

ID 39836. Xor paths in a matrix

Темы: meet in the middle Bust

A rectangular field of size n*m is specified. Each cell contains a non-negative integer. You need to count the number of paths from cell (1,1) to cell (n,m) that satisfy the following conditions.
1) From each cell, you can only move down or right without leaving the field.
2) The bitwise exclusive OR of all numbers on the path must be equal to k.
Find the number of matching paths for the given field.

Input
The first line contains three integers n, m and k (1 <= n, m <= 20, 0 <= k <= 10¹⁸) - the height and width of the field, and the number k.
The following n lines each contain m integers a_i,j, where j -th element of i-th row is equal to a_i,j (0 <= a_i,j < ;= 10¹⁸).

Imprint
Print one integer - the number of paths that satisfy all conditions.

Examples

#	Input	Output
1	3 3 11 2 1 5 7 10 0 12 6 4	3
2	3 4 2 1 3 3 3 0 3 3 2 3 0 1 1	5

ID 39838. Kazuma and his companions

Темы: meet in the middle

Kazuma travels with three companions: Aqua, Megumin, and Darkness. But travel is not paid, so our squad must complete the tasks assigned by the Adventurer's Guild.

Kazuma has already chosen n tasks to complete. However, whenever a squad in full force takes on something, unforeseen and absurd things happen. That is why Kazuma decided that for each of the tasks he would take exactly two companions.

The ratio of each of the companions to Kazuma is characterized by an integer. Initially, the attitude of each of them is neutral and equal to 0. In the process of completing the task, the attitude of the girls he took on the task towards him changes in a positive or negative direction (or may not change at all).

For each of the tasks, Kazuma knows how each girl's attitude towards him will change after completing the task. He wants to take companions on assignments so that after completing all of them, the attitudes of all the girls towards him are equal. If this can be achieved in different ways, then, of course, it is necessary that the relationship be as good as possible.

Help Kazuma figure out what the most equal treatment he can get for all the girls.

Input:
The first line contains a positive integer n (1 ≤ n ≤ 25) — the number of tasks to complete.
The next n lines contain descriptions of — i-th line contains three numbers a_i, m_i, d_i — the amount by which Aqua, Megumin or Darkness's attitudes towards Kazuma will change, respectively, if the hero takes them with him to complete the i-th task.
All numbers in the input are integers and do not exceed 10⁷ in absolute value.

Output:
If there is no solution, print "Impossible" in the first line.
Otherwise, print the relationship that all girls will have towards Kazuma, and at the same time, print the maximum possible.

Examples:

Input	Output
3 1 0 0 0 1 0 0 0 1	1
7 0 8 9 5 9 -2 6-8-7 9 4 5 -4 -9 9 -4 5 2 -6 8 -7	5
2 1 0 0 1 1 0	Impossible

ID 39839. hidden treasures

Темы: meet in the middle Segment tree, RSQ, RMQ

The daughter of the King of Flatland is about to marry Prince Charming.
The prince wants to give the princess treasures, but he is not sure which diamonds to choose from his collection.

There are n diamonds in the prince's collection, each characterized by weight w_i and value v_i.
The prince wants to give the most expensive diamonds, but the king is smart and will not accept diamonds with a total weight of more than R. On the other hand, the prince will consider himself greedy for the rest of his life if he gives diamonds with a total weight of less than L.

Help the prince choose a set of diamonds with the highest total value so that the total weight is in the segment [L, R].

Input:
The first line contains the number n (1 <= n <= 32), L and R (0 <= L <= R <= 10¹⁸).
The next n lines describe the diamonds and contain two numbers each - the weight and value of the corresponding diamond (1 <= wi, vi <= 10¹⁵).

Output:
The first line of the output should contain k - the number of diamonds to give to the princess.
The second line should contain the numbers of the diamonds to be given.
Diamonds are numbered from 1 to n in the order they appear in the input.

If it is impossible to compose a present for the princess, then print 0 in the first line of the output.

Examples:

Input	Output
3 6 8 3 10 7 3 8 2	1 2