TheForces Round #16 (2^4-Forces)
A. Infinite Grid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There's an infinite grid graph.All cells are initially white.Your task is to dye exactly $$$n$$$ cells in red.

A blue edge is a unit edge that connects two cells with different colors.

For example,$$$n=3$$$,one of the dyeing schemes is as follows:

The number of blue edges is $$$8$$$.It can be proved that it reaches the minimum.

Find the minimum number of blue edges for given $$$n$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of a line of input.The only line of each test case contains an integer $$$n(1 \leq n \leq 10^{18})$$$.

Output

For each test case, output on a new line — the minimum number of blue edges.

Example
Input
4
3
5
8
50
Output
8
10
12
30

B. Mex Path
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a $$$2*n$$$ grid $$$a$$$. On the grid,there is a non-negative integer $$$a_{i,j}$$$ in row $$$i$$$ and line $$$j$$$.

You must walk from $$$(1,1)$$$ to $$$(2, n)$$$. Each cell can be accessed at most once.At each step, you can go up, down, or right(but not to the left or beyond the boundary).

Note the set of numbers on the grid you have walked through is $$$S$$$. Find the biggest $$$mex (S)$$$ you can get.

Remember that $$$mex(S)$$$ is the smallest non-negative integer that does not belong to $$$S$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of three line of input.

The first line contains an integer $$$n(1 \leq n \leq 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_{1,1},a_{1,2},...a_{1,n}(0 \leq a_{1,i} \leq 2n)$$$.

The third line contains $$$n$$$ integers $$$a_{2,1},a_{2,2},...a_{2,n}(0 \leq a_{2,i} \leq 2n)$$$.

The sum of $$$n$$$ over all will not exceed $$$10^5$$$.

Output

For each test case,output on a new line — the biggest $$$mex (S)$$$ you can get.

Example
Input
2
3
2 0 2
1 2 1
4
1 0 5 2
3 5 4 1
Output
3
4
Note

Test case $$$1$$$:

$$$(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3)$$$

$$$S=\{0,1,2 \},mex(S)=3$$$.It can be shown that $$$3$$$ is the maximum.

Test case $$$2$$$:

$$$(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (1,4) \rightarrow (2,4)$$$

$$$S=\{0,1,2,3,5 \},mex(S)=4$$$.It can be shown that $$$4$$$ is the maximum.

C. Get the Long Binary Number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a binary number $$$x$$$.Define $$$c0(x)$$$ as the number of $$$0$$$ in $$$x$$$,$$$c1(x)$$$ as the number of $$$1$$$ in $$$x$$$.

For example,$$$x=10100$$$,we can get $$$c0(x)=3,c1(x)=2$$$.

Now you're given a binary number $$$y$$$(without leading zero) of length $$$n$$$ and an integer $$$k$$$.Your task is find the smallest binary number $$$x$$$(without leading zero),which satisfies:

  1. $$$y \leq x$$$;
  2. $$$c0(x)-c1(x)=k$$$.
Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of two line of input.

The first line contains two integers $$$n,k(1 \leq n \leq 10^5,-10^5 \leq k \leq 10^5)$$$.

The second line contains a binary number $$$y$$$(without leading zero) of length $$$n$$$.

The sum of $$$n,|k|$$$ over all test cases will not exceed $$$4*10^5$$$.

Output

For each test case,output on a new line — the smallest binary number $$$x$$$(without leading zero),which satisfies:

  1. $$$y \leq x$$$;
  2. $$$c0(x)-c1(x)=k$$$.
Example
Input
5
1 -1
0
6 -4
110100
6 1
100000
7 1
1110000
10 -2
1011010111
Output
1
110111
1000011
1110000
1011011001

D. Increasing A and Decreasing B
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two integers $$$n$$$ and $$$x$$$.

Your task is to construct an array $$$a$$$ of size $$$n$$$ with non-negative integers,which satisfies:

  1. $$$a_1=x$$$;
  2. $$$a_i \lt 2^{30}(1 \leq i \leq n)$$$;
  3. $$$a$$$ is strictly increasing;
  4. note $$$b_i=a_i \oplus a_{i+1}(1 \leq i \leq n-1)$$$, $$$b$$$ is strictly decreasing.Here $$$\oplus$$$ means bitwise-xor.

If no solution,print $$$-1$$$ instead.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of a line of input.The only line of each test case contains two integers $$$n,x(3 \leq n \leq 10^5,0 \leq x \leq 2^{30}-1)$$$.

The sum of $$$n$$$ will not exceed $$$10^5$$$.

Output

For each test case, output on a new line:

If no solution,print $$$-1$$$;

Otherwise,print $$$n$$$ integers:$$$a_1,a_2,...,a_n$$$.

Example
Input
2
3 1
3 1073741823
Output
1 2 3
-1
Note

Test case $$$1$$$:

Obviously,$$$a$$$ is strictly increasing. And $$$b_1=a_1 \oplus a_2=1 \oplus 2=3$$$,$$$b_2=a_2 \oplus a_3=2 \oplus 3=1$$$,$$$b=[3,1]$$$ is strictly decreasing.

Test case $$$2$$$:

Since $$$a_2$$$ must be smaller than $$$2^{30}$$$ and $$$a_1$$$ is already $$$2^{30}-1$$$,no solution.

E. Grid Walking+
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an $$$n*m$$$ grid.There's an integer $$$a_{i,j}$$$ in $$$(i,j)$$$.

Here're some rules:

  1. You can start from any cell,and end at any cell;

  2. In one move,you can move left,right or down(but not move up or beyond the boundary);

  3. Each move will incur a cost of $$$c$$$;

  4. You can access the same cell multiple times.

Note $$$S$$$ as the set of cells you have accessed,and $$$k$$$ as your number of moves.Your score is defined as $$$\Sigma_{(i,j)∈S}a_{i,j}-kc$$$.

Find the maximum value of your score.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 1000)$$$, denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line contains three integers $$$n,m,c(1 \leq n,m \leq 2000,1 \leq c \leq 10^9)$$$.

The next $$$n$$$ lines describe $$$a$$$.The next $$$i$$$ line contains $$$m$$$ integers $$$a_{i,1},a_{i,2},...,a_{i,m}(-10^9 \leq a_{i,j} \leq 10^9)$$$.

The sum of $$$n,m$$$ over all test cases will not exceed $$$2000$$$.

Output

For each test case, output an integer on a new line — the maximum value of your score.

Example
Input
4
3 3 1
-2 -2 -2
-2 -1 -2
-2 -2 -2
4 5 2
-1 9 9 -1 -1
-2 0 9 -2 -1
9 -1 9 -1 -2
0 -1 -2 9 -2
6 5 3
-2 -3 3 9 6
8 7 5 -1 -1
-1 1 1 7 7
-4 -6 6 4 5
9 9 8 5 9
9 -9 6 5 7
6 6 1
8 3 -6 4 4 5
3 -9 -2 4 -1 -9
-1 -9 2 -3 -8 5
-8 -2 -6 -8 -7 -8
-5 3 -5 3 7 1
-9 5 -3 4 2 7
Output
-1
34
58
19
Note

Test case $$$1$$$:

Just start from $$$(2,2)$$$ and end at $$$(2,2)$$$.Your score is $$$a_{2,2}=-1$$$.

Test case $$$2$$$:

$$$(1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,2) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (3,4) \rightarrow (4,4)$$$

Your number of moves $$$k=9$$$.Your score is $$$a_{1,2}+a_{1,3}+a_{2,3}+a_{3,1}+a_{3,2}+a_{3,3}+a_{3,4}+a_{4,4}-kc=9+9+9+9-1+9-1+9-9*2=34$$$.