Before participating in any online contest, you only keep the tab of the online contest open and close everything else.
You have n open tabs, numbered from 1 to n from left to right. Tab number k is the tab of the online contest and it is the current selected one. You have only two buttons:
- Close all tabs to the left of the selected tab.
- Close all tabs to the right of the selected tab.
What is the minimum number of clicks needed to close all tabs except tab number k?
The first line of input contains a single integer T (1 ≤ T ≤ 5050), the number of test cases.
Each test case consists of a single line that contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 100), the number of open tabs, and the tab of the online contest, respectively.
For each test case, print the minimum number of clicks needed to close all tabs except the tab of the online contest.
4
72 1
5 2
10 7
64 64
1
2
2
1
In a competitive coding contest called OverCode, matches are held between two teams. Each team must have exactly 6 coders. In order to form fair matches between coders, the absolute difference between the ratings of any two members of the same team shouldn't exceed 1000.
What is the maximum number of teams that can be formed out of n coders if you were given their ratings, such that each coder is a member of at most one team?
The first line of input contains a single integer T (1 ≤ T ≤ 512), the number of test cases.
The first line of each test case contains a single integer n (1 ≤ n ≤ 500), the number of coders participating in OverCode.
The next line contains n space-separated integers r1, r2, ..., rn (1 ≤ ri ≤ 4000), ri is the rating of the ith coder.
The total sum of n overall test cases doesn't exceed 1.5 × 105.
For each test case, print the maximum number of teams that can be formed, on a single line.
3
5
4 1 5 3 2
6
1 1001 2 4 3 5
13
7 9 7 2 1000 1001 2 3 9 4 5 2 5
0
1
2
You’re participating in the ACM JCPC for the first time. Your team solved k out of the 13 problems. Since your last successful submission, you have been trying to solve new problems with no luck.
After all the frustration from the wrong answers, you decided to quit. You raised your head looking for a volunteer, then noticed a big white screen with some red and green dashes. You put your glasses on and, it is a scoreboard! You didn't know this contest has a scoreboard! Now that you do, you noticed that some problems have been solved by many teams! You decided to focus and try to solve the problem that has been solved by the maximum number of teams.
The first line of input contains a single integer T (1 ≤ T ≤ 53235), the number of test cases.
The first line of each test case contains a single integer k (1 ≤ k < 13), the number of problems your team successfully solved.
The second line contains a string of k distinct uppercase English letters that represent the problems your team solved. The letters are given in the alphabetical order. Each problem from 1 to 13 has a corresponding letter from 'A' to 'M'.
The third line contains 13 integers t1, t2, ..., t13 (0 ≤ ti ≤ 92), ti is the number of teams that solved problem the ith problem.
It is guaranteed that the input is valid, and there's at least one problem not solved by your team and solved by other teams.
For each test case, print an uppercase letter that represents the next problem to be solved, which is the one that has been completed by the maximum number of teams.
It is guaranteed that the answer is unique.
3
2
CE
3 0 47 0 76 0 0 2 0 0 0 0 0
7
ADEFHLM
1 1 2 1 1 1 1 1 0 1 1 1 1
2
DG
35 14 40 13 11 18 1 7 41 29 8 19 43
A
C
M
You want to prepare test cases for a problem with the following description:
"Given an array of n positive integers, and a number of queries. Each query will ask about a range [l, r] (1 ≤ l ≤ r ≤ n), where each of the values between index l and index r (both inclusive) occurs an even number of times except one value. The answer to each query is the value that occurs an odd number of times in the given range."
You have generated an array of n positive integers, you need to know the number of valid queries you can ask on this array. A query is valid if it has an answer, and that answer is unique.
The first line of input contains a single integer T (1 ≤ T ≤ 64), the number of test cases.
The first line of each test case contains a single integer n (1 ≤ n ≤ 5000), the size of the array.
The next line contains n space-separated integers, a1, a2, ..., an (1 ≤ ai ≤ 106), the values of the array.
The total sum of n overall test cases doesn't exceed 72000.
For each test case, print a single line with the number of valid queries you can ask.
1
7
9 1 1 2 1 9 9
12
You built a new robot that moves over r × c grid. The rows of the grid are numbered from 1 to r from top to bottom, and the columns are numbered from 1 to c from left to right. The grid contains free and blocked cells, and the robot can only move over the free cells. All cells on the border of the grid are blocked. The robot reads the movement instructions from a file on its SD card and starts performing them.
It performs only two types of movement instructions:
- Rotate 90 degrees clockwise. The time taken in this instruction is negligible (zero time).
- Move x cells forward, where x is a positive integer. If the next cell in the current direction is blocked, the robot rotates 90 degrees clockwise and tries again. This instruction takes x seconds to be completed.
When you tried to upload the new instruction file to the SD card, you received an out-of-memory error. You want to rewrite the instructions in such a way that the robot will visit the same cells in the same order. For example, if by performing the instruction file, the robot visits {cell1, cell2, cell3, cell2, cell3} in this order, the new instructions should make the robot visit the same cells in the same order.
Given the initial position and direction, the grid, and the original instructions, what is the minimum number of instructions needed to visit the same cells in the same order? Note that you cannot change the initial position and direction.
The first line of input contains a single integer T (1 ≤ T ≤ 128), the number of test cases.
The first line of each test case contains three integer r, c, and q (3 ≤ r, c ≤ 500) (1 ≤ q ≤ 1000), the number of rows and columns of the grid, and the number of instructions in the file, respectively.
The second line of each test case contains two integers sr, sc, the row and the column of the starting cell (a free cell). Followed by a space then a single uppercase letter sdir, which is the initial direction of the robot, it can only be one of the four letters {'U', 'D', 'L', 'R'}, each letter represents one of the four directions: up, down, left, and right, respectively.
Each of the following r lines contain c characters that are either ‘.’ (a free cell), or ‘#’ (a blocked cell). It is guaranteed that each free cell has at least one adjacent free cell, and all cells on the border of the grid are blocked.
Each of the following q lines contains an instruction, each instruction will be in one of two formats:
- ‘R’ , that represents the first type of movement "Rotate".
- ‘F’ x, that represents the second type of movement "Move x" (1 ≤ x ≤ 1000).
Note that the robot performs the given instructions in the given order.
For each test case, print the minimum number of instructions needed to visit the same cells in the same order.
3
6 10 12
2 9 U
##########
#........#
#.#.....##
#........#
#...#....#
##########
R
R
R
F 3
F 4
R
R
R
F 2
R
R
F 2
4 4 2
2 2 R
####
#..#
#..#
####
R
R
4 4 3
3 2 R
####
#.##
#.##
####
F 1000
R
F 1000
7
0
1
In the first test case, the following 7 instructions will visit the same cells as the given instructions and in the same order: F 7, R, R, R, F 2, R, F 2.
In the second test case, there's no need for any instruction, as the robot didn't visit any cell.
Note that the description of the grid, and the movement instructions are the same as in problem Robot I - Instruction Reduction.
Instead of rewriting the instructions to fit on the SD card, you decided to buy a new one with larger capacity. Now, you are facing a new problem. Each free cell can be lit by one of k different colors. Initially, all the free cells are lit with the first color (white). Each time the robot visits a cell, it changes its color to a new color that wasn’t used in that cell before. If all color were used, the robot explodes.
Given the initial position and direction of the robot, the grid, and the movement instructions, determine the position of the cell that the robot will explode at and the total amount of time the robot took from the start until it exploded. Note that rotation takes no time.
The first line of input contains a single integer T (1 ≤ T ≤ 64), the number of test cases.
The first line of each test case contains four integers r, c, q, and k (3 ≤ r, c ≤ 500) (1 ≤ q ≤ 2 × 105) (2 ≤ k ≤ 109), the number of rows and columns of the grid, the number of instructions in the file, and the number of different colors for each cell, respectively.
The second line of each test case contains two integers sr, sc, the row and the column of the starting cell (a free cell). Followed by a single uppercase letter sdir, which is the initial direction of the robot, it can be only one of the four letters {'U', 'D', 'L', 'R'}, each letter represents one of the four directions: up, down, left, and right, respectively.
Each of the following r lines contains c characters that are either ‘.’ (a free cell), or ‘#’ (a blocked cell). It is guaranteed that each free cell has at least one adjacent free cell, and all cells on the border of the grid are blocked.
Each of the following q lines contains an instruction, each instruction will be in one of two formats:
- ‘R’ , that represents the first type of movement “Rotate”.
- ‘F’ x, that represents the second type of movement “Move x” (1 ≤ x ≤ 107).
Note that the robot performs the given instructions in the given order.
The total number of cells in all test cases doesn't exceed 106.
The total number of instructions in all test cases doesn't exceed 2 × 106.
For each test case, print three integers, the row and column of the cell that the robot will explode at, and elapsed time until then. If it will not explode print only - 1.
2
5 7 3 2
3 3 R
#######
#.....#
#...#.#
#.....#
#######
F 5
R
F 3
3 6 1 2
2 2 U
######
#....#
######
F 3
3 4 7
-1
Just days before the JCPC, your internet service went down. You decided to continue your training at the ACM club at your university. Sadly, you discovered that they have changed the WiFi password. On the router, the following question was mentioned, the answer is the WiFi password padded with zeros as needed.
A subarray [l, r] of an array A is defined as a sequence of consecutive elements Al, Al + 1, ..., Ar, the length of such subarray is r - l + 1. The bitwise OR of the subarray is defined as: Al OR Al + 1 OR ... OR Ar, where OR is the bitwise OR operation (check the notes for details).
Given an array A of n positive integers and an integer v, find the maximum length of a subarray such that the bitwise OR of its elements is less than or equal to v.
The first line contains an integer T (1 ≤ T ≤ 128), where T is the number of test cases.
The first line of each test case contains two space-separated integers n and v (1 ≤ n ≤ 105) (1 ≤ v ≤ 3 × 105).
The second line contains n space-separated integers A1, A2, ..., An (1 ≤ Ai ≤ 2 × 105), the elements of the array.
The sum of n overall test cases does not exceed 106.
For each test case, if no subarray meets the requirement, print 0. Otherwise, print the maximum length of a subarray that meets the requirement.
3
5 8
1 4 5 3 1
5 10
8 2 6 1 10
4 2
9 4 5 8
5
3
0
To get the value of x OR y, consider both numbers in binary (padded with zeros to make their lengths equal), apply the OR operation on the corresponding bits, and return the result into decimal form. For example, the result of 10 OR 17 = 01010 OR 10001 = 11011 = 27.
The city of single direction consists of n blocks in a row, numbered from 1 to n from left to right. All of them are populated by citizens, and some of them has gas stations. People in each block will go to the nearest block that has a gas station. The distance between two blocks i and j is |i - j|, where |x| is the absolute value of x.
The government wants to move at most one station from its original block to another block. What is the maximum distance that a citizen has to cross to get to his/her nearest station, if the government operated in a way that minimizes this distance?
The first line of input contains a single integer T (1 ≤ T ≤ 1200), the number of test cases.
The first line of each test case contains a single integer n (1 ≤ n ≤ 105), the number of blocks in the city.
The second line contains a string s of n characters, each character is either ‘+’, which represents a block with one gas station, or ‘.’ which represents a normal block.
It is guaranteed that there’s at least one block that has a gas station.
The total sum of n overall test cases doesn't exceed 5 × 106.
For each test case, print the answer on a single line.
5
1
+
3
+..
4
+.+.
5
.+...
10
..+.....++
0
1
1
2
2
The organizers of the ACM Movie Night event decided to hold a voting to let members choose one of the available three movies. Each member can pick an ink-stamp of the first letter of the movie he/she wants to vote for {‘H’, ‘M’, or ‘Y’}, and use it on a big whiteboard rotated in any angle they want, but without overlapping/touching previous votes or touching the borders of the whiteboard.
Stamps for each movie are available in different sizes but they are all made of the same font, and all of them will leave a black mark on the whiteboard. The picture shows the used font and how the whiteboard may look at the end of the voting process (it represents an actual test case but scaled down).
The first line of input contains a single integer T (1 ≤ T ≤ 32), the number of test cases.
The first line of each test case contains two space-separated integers r and c (r, c ≤ 1000), the number of rows and columns of the image, respectively.
Each of the following r lines contains c characters that are either ‘.’ (a white pixel), or ‘#’ (a black pixel).
It is guaranteed that the input is valid and matches the following constraints:
- All cells on the border are white.
- The image contains at least one letter.
- The width of any used letter before rotating it is at least 20 pixels.
- Each maximal connected component of black pixels represents one of the three letters.
The total number of pixels in all test cases doesn't exceed 5 × 106.
For each test case, print a single line with three space-separated integers, the number of times each of ‘H’, ‘M’, and ‘Y’ appears on the whiteboard, respectively.
A connected component is a set of black pixels such that it is possible to start at any pixel from the set and reach all other pixels by moving only to adjacent pixels. Two pixels are adjacent if they share a corner or an edge. A connected component is maximal if adding a new black pixel to the component will make it disconnected.
You built a robot that only jumps. To test its efficiency you have created a circular path that contains empty cells and walls. Your robot may stand only on empty cells and allowed to jump above at most one wall at a time.
Initially the length of the jump is k. Each time the robot fails to jump because it will not land on an empty cell, or this jump will be above more than one wall, the robot decreases the current length of the jump by one and tries again. The robot is only allowed to decrease the current length when it fails to jump, and it is not allowed to increase it again. If the length of jump reaches zero, the robot stops.
To complete the test, you will place the robot at every position on the circular path, and record the number of jumps it needs to complete a path. A path is completed if the robot jumped over each wall at least once.
You will place the robot facing to the right and it will jump in clockwise direction without changing its direction.
The first line of input contains a single integer T (1 ≤ T ≤ 128), the number of test cases.
The first line of each test case contains two space-separated integers n and k (3 ≤ n ≤ 105) (2 ≤ k ≤ min{n - 1, 50}), the length of the path, and the initial length of the jump.
The second line contains a string of n characters. Each character is either '.' (an empty cell) or '#' (a wall). The given path contains at least one wall.
Cells are numbered from 1 to n in the given order. Cell number 1 is to the right of cell number n.
The sum of n overall test cases doesn't exceed 2 × 106.
For each test case, print n numbers on a single line, a1, a2, ..., an, where ai is one of the following:
- 0, if cell i is a wall.
- - 1, if it is impossible to complete a path starting from cell i.
- Otherwise, it is equal to the minimum number of jumps needed to complete a path if the robot started from cell number i.
4
3 2
###
4 2
.#..
6 5
.#...#
10 3
.#..#...#.
0 0 0
1 0 2 -1
2 0 2 2 2 0
3 0 -1 3 0 -1 3 3 0 4
You're participating in a contest for finding the 1031415926th prime number. You've developed a relatively fast algorithm, that has been working for a month, to find that number. To maximize the utilization of the resources you have, you distributed the work of the algorithm over k threads, where each thread was assigned a specific amount of work.
Two days left until the contest deadline, and the only thing you know about the progress of your algorithm is shown on the console window:
The first line shows the amount of work assigned to each of the k threads, these amounts were assigned randomly (clever!). Each of the following lines has a single integer that represents the current progress of one of the threads. You don't know for which thread each line belongs, but you do know that the progress value of each thread never decreases and doesn't exceed the amount of work assigned to the thread. Each thread takes a non-zero amount of the remaining work assigned to it, finishes it and then reports its new progress, for that no thread will print the same progress value twice, and all the finished work of the threads is reported.
To have an idea about the actual progress of your algorithm, you want to know the minimum and the maximum possible overall amount of remaining work.
The first line of input contains a single integer T, the number of test cases.
The first line of each test case contains two space-separated integers n and k (1 ≤ n ≤ 100) (2 ≤ k ≤ 16), the number of lines that shows progress values on your screen, and the number of threads.
The second line contains k space-separated integers w1, w2, ..., wk (1 ≤ wi ≤ 109), the ith integer represents the amount of work assigned to the ith thread.
Each of the following n lines contains a single integer that represents a progress value printed by one of the threads. The lines are given in the order they were printed in.
It is guaranteed that the input is valid and matches the problem statement.
The sum of n overall test cases doesn't exceed 1500.
For each test case, print a single line with two integers, the minimum and the maximum possible overall amount of remaining work, respectively.
3
6 3
8 12 7
5
3
7
3
4
9
3 3
1000000000 999999999 999999998
1
10
1000
5 3
9 5 8
9
3
6
5
8
6 11
2999998986 2999998997
0 0
In a custom chess game, you are given an army of r knights placed on a grid. The grid contains r × c cells that are either empty, occupied by a knight, or by an obstacle. Initially, each row has exactly one knight. The knight moves two cells horizontally then one cell vertically, or one cell horizontally then two cells vertically (L-shape moves).
The positions of your knights were leaked, and all of them now have to move to stay safe. Each knight should make exactly one knight-move and jump to an empty cell. Each empty cell can be occupied by at most one knight. Your knights can share the same row after they move. Keep in mind, since all of the old positions of your knights were leaked, it is not safe to use any of these cells again.
Find the number of ways to move all the knights. Two ways are different if the new position of at least one of the knights is different. As the result can be very large, print it modulo 1000000007 (109 + 7).
The first line of input contains a single integer T (1 ≤ T ≤ 256), the number of test cases.
The first line of each test case contains two space-separated integer r and c (3 ≤ r, c ≤ 500), the number of rows and columns, respectively.
Each of the following r lines contains c characters. Each character is one of the following:
- ‘.’: an empty cell.
- '#': a cell that is occupied by an obstacle.
- '*': a cell that is occupied by a knight.
It is guaranteed that each row has exactly one knight.
The total number of knights in all test cases doesn't exceed 105.
For each test case, print the number of ways to move all the knights modulo 109 + 7, on a single line.
3
3 3
*..
..*
..*
3 5
*....
....*
*....
5 5
*..#.
...*.
..#.*
..#.*
*....
2
6
1
You and your friend decided to play a new game using a squared chessboard of size n × n and one rook. Rows are numbered from 1 to n from top to bottom, and columns are numbered from 1 to n from left to right. Each cell is identified by a pair (r, c) which means that the cell is located at row r and column c.
The rules are simple, you and your friend will take turns, and you will start first. In each turn a player can move the rook at least 1 cell, and at most k cells in only one direction, either up or left, without going outside the chessboard. The player who moves the rook to the top-left cell (1, 1) wins.
You will choose the starting position for the rook. You are not allowed to choose the top-left cell. If you both will play optimally, how many cells can you choose as a starting position to win the game.
The first line of input contains an single integer T (1 ≤ T ≤ 2 × 104), the number of test cases.
Each test case consists of a single line that contains two space-separated integers n and k (1 ≤ k < n ≤ 109), where n is the size of the chessboard, and k is the maximum allowed move.
For each test case, print a single line that contains the number cells you can choose as a starting position to win the game.
3
2 1
3 1
9 4
2
4
64