分类： 赛事资讯

The cows are taking a multiple choice test. But instead of a standard test where your selected choices are scored for each question individually and then summed, in this test your selected choices are summed before being scored.
Specifically, you are given N (2≤N≤10*5) groups of integer vectors on the 2D plane, where each vector is denoted by an ordered pair (x,y). Choose one vector from each group such that the sum of the vectors is as far away from the origin as possible.
It is guaranteed that the total number of vectors is at most 2?105. Each group has size at least 2, and within a group, all vectors are distinct. It is also guaranteed that every x and y coordinate has absolute value at most 109N.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N, the number of groups.
Each group starts with G, the number of vectors in the group, followed by G lines containing the vectors in that group. Consecutive groups are separated by newlines.
OUTPUT FORMAT (print output to the terminal / stdout):
The maximum possible squared Euclidean distance.
SAMPLE INPUT:
3
2
-2 0
1 0
2
0 -2
0 1
3
-5 -5
5 1
10 10
SAMPLE OUTPUT:
242
It is optimal to select (1,0) from the first group, (0,1) from the second group, and (10,10) from the third group. The sum of these vectors is (11,11), which is squared distance 112+112=242 from the origin.
SCORING:
In test cases 1-5, the total number of vectors is at most 103.
In test cases 6-9, every group has size exactly two.
Test cases 10-17 satisfy no additional constraints.

As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has N (1≤N≤5000) stacks of haybales. For each i∈[1,N], the ith stack has hi (1≤hi≤10^9) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:
If two adjacent stacks' heights differ by exactly one, she can move the top haybale of the taller stack to the shorter stack.
How many configurations are obtainable after performing the above operation finitely many times, modulo 109+7? Two configurations are considered the same if, for all i, the ith stack has the same number of haybales in both.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent test cases, all of which must be solved to solve one input correctly.
Each test case consists of N, and then a sequence of N heights. It is guaranteed that the sum of N over all test cases does not exceed 5000.

OUTPUT FORMAT (print output to the terminal / stdout):
Please output T lines, one for each test case.
SAMPLE INPUT:
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 5
SAMPLE OUTPUT:
4
4
5
15
9
8
19
For the first test case, the four possible configurations are:

(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2).
For the second test case, the four possible configurations are:

(2,3,3,1),(3,2,3,1),(3,3,2,1),(3,3,1,2).
SCORING:
Inputs 1-3 satisfy N≤10.
Input 4 satisfies 1≤hi≤3 for all i.
Inputs 5-7 satisfy |hi−i|≤1 for all i.
Inputs 8-10 satisfy 1≤hi≤4 for all i and N≤10^0.
Inputs 11-13 satisfy N≤100.
Inputs 14-17 satisfy N≤1000.
Inputs 18-21 satisfy no additional constraints.

As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has N (1≤N≤5000) stacks of haybales. For each i∈[1,N], the ith stack has hi (1≤hi≤109) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:
If two adjacent stacks' heights differ by exactly one, she can move the top haybale of the taller stack to the shorter stack.
How many configurations are obtainable after performing the above operation finitely many times, modulo 10^9+7? Two configurations are considered the same if, for all i, the ith stack has the same number of haybales in both.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent test cases, all of which must be solved to solve one input correctly.
Each test case consists of N, and then a sequence of N heights. It is guaranteed that the sum of N over all test cases does not exceed 5000.

OUTPUT FORMAT (print output to the terminal / stdout):
Please output T lines, one for each test case.
SAMPLE INPUT:
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 5
SAMPLE OUTPUT:
4
4
5
15
9
8
19
For the first test case, the four possible configurations are:

(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2).
For the second test case, the four possible configurations are:

(2,3,3,1),(3,2,3,1),(3,3,2,1),(3,3,1,2).
SCORING:
Inputs 1-3 satisfy N≤10.
Input 4 satisfies 1≤hi≤3 for all i.
Inputs 5-7 satisfy |hi−i|≤1 for all i.
Inputs 8-10 satisfy 1≤hi≤4 for all i and N≤100.
Inputs 11-13 satisfy N≤100.
Inputs 14-17 satisfy N≤1000.
Inputs 18-21 satisfy no additional constraints.
Problem credits: Daniel Zhang

Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has N (1≤N≤10^5) stacks of haybales. For each i∈[1,N], the ith stack has hi (1≤hi≤10^9) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows:
If two adjacent stacks' heights differ by at most K (1≤K≤10^9), she can swap the two stacks.
What is the lexicographically minimum sequence of heights that Bessie can obtain after some sequence of these operations?

**Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N and K. The i+1-st line contains the height of the i-th haybale.
OUTPUT FORMAT (print output to the terminal / stdout):
Please print out N lines, the i-th containing the height of the i-th haybale in the solution.
SAMPLE INPUT:
5 3
7
7
3
6
2
SAMPLE OUTPUT:
6
7
7
2
3
One way that Bessie can swap the stacks is as follows:

7 7 3 6 2
-> 7 7 6 3 2
-> 7 7 6 2 3
-> 7 6 7 2 3
-> 6 7 7 2 3
SCORING:
In 10% of all input cases, N≤10^0
In another 20% of all input cases, N≤5000
In the remaining 70% of input cases, there are no additional constraints
Problem credits: Daniel Zhang and Benjamin Qi

In an effort to improve her vocabulary, Bessie the cow has obtained a set of four wooden blocks, each one a cube with a letter of the alphabet written on each of its six sides. She is learning how to spell by arranging the blocks in a row so the letters on top of the blocks spell words.
Given the letters on each of Bessie's four blocks, and a list of words she would like to spell, please determine which of words on her list she will be able to spell successfully using the blocks.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N (1≤N≤10), the number of words that Bessie would like to spell. The next four lines each contain a string with six uppercase letters, representing the letters on the six sides of one of Bessie's blocks. The next N lines contain the N words Bessie would like to spell. Each of these is between 1 and 4 uppercase letters long.
OUTPUT FORMAT (print output to the terminal / stdout):
For each word on Bessie's list, output YES if she is able to spell it using the blocks and NO otherwise.
SAMPLE INPUT:
6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
MOO
ZOO
MOVE
CODE
FARM
SAMPLE OUTPUT:
YES
NO
YES
YES
NO
NO
In this example, Bessie can spell COW, ZOO, and MOVE. Sadly, she cannot spell MOO, since the only block with an M cannot also be used for an O. She cannot spell FARM since there is no block with a letter R. She cannot spell CODE since the C, D, and E all belong to the same block.

Problem credits: Brian Dean

In what seems to be a familiar occurrence, Farmer John is lining up his N cows (1≤N≤10^5), conveniently numbered 1…N, for a photograph.
Initially, the cows are lined up in the order a1,a2,…,aN from left to right. Farmer John's goal is to line up the cows in the order b1,…,bN from left to right. To accomplish this, he may perform a series of modifications to the ordering. Each modification consists of choosing a single cow and moving it some number of positions to the left.

Please count the minimum number of modifications required in order for Farmer John to line up his cows in the desired order.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains N. The second line contains a1,a2,…,aN. The third line contains b1,b2,…,bN.
OUTPUT FORMAT (print output to the terminal / stdout):
Print the minimum number of modifications required to produce Farmer John's desired ordering.
SAMPLE INPUT:
5
1 2 3 4 5
1 2 3 4 5
SAMPLE OUTPUT:
0
In this example, the cows are already in the desired order, so no modifications are required.

SAMPLE INPUT:
5
5 1 3 2 4
4 5 2 1 3
SAMPLE OUTPUT:
2
In this example, two modifications suffice. Here is one way Farmer John can rearrange his cows:

Choose cow 4 and move it four positions to the left.
Choose cow 2 and move it two positions to the left.
5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3
SCORING:
Test cases 3-6 satisfy N≤100.
Test cases 7-10 satisfy N≤5000.
Test cases 11-14 satisfy no additional constraints.
Problem credits: Benjamin Qi

Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often.
Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are N class periods (1≤N≤10^5), and Elsie logs that Bessie fell asleep ai times (0≤ai≤10^6) in the i-th class period. The total number of times Bessie fell asleep across all class periods is at most 106.

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures. The only way Elsie may modify the log is by combining two adjacent class periods. For example, if a=[1,2,3,4,5], then if Elsie combines the second and third class periods the log will become [1,5,4,5].

Help Elsie compute the minimum number of modifications to the log that she needs to make so that she can make all the numbers in the log equal.

INPUT FORMAT (input arrives from the terminal / stdin):
Each input will contain T (1≤T≤10) test cases that should be solved independently.
The first line contains T, the number of test cases to be solved. The T test cases follow, each described by a pair of lines. The first line of each pair contains N, and the second contains a1,a2,…,aN.

It is guaranteed that within each test case, the sum of all values in a is at most 106. It is also guaranteed that the sum of N over all test cases is at most 105.

OUTPUT FORMAT (print output to the terminal / stdout):
Please write T lines of output, giving the minimum number of modifications Elsie could perform to make all the log entries equal for each case.

SAMPLE INPUT:
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
SAMPLE OUTPUT:
3
2
0
For the first test case in this example, Elsie can change her log to consist solely of 3s with 3 modifications.

1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3
For the second test case, Elsie can change her log to 7 with 2 modifications.

2 2 3
-> 2 5
-> 7
For the last test case, Elsie doesn’t need to perform any operations; the log already consists of equal entries.

Problem credits: Jesse Choe

Farmer John has fallen behind on organizing his inbox. The way his screen is organized, there is a vertical list of folders on the left side of the screen and a vertical list of emails on the right side of the screen. There are M total folders, numbered 1…M (1≤M≤104). His inbox currently contains N emails numbered 1…N (1≤N≤105); the ith email needs to be filed into folder fi (1≤fi≤M).
FJ's screen is rather small, so he can only view K (1≤K≤min(N,M)) folders and K emails at once. Initially, his screen starts out displaying folders 1…K on the left and emails 1…K on the right. To access other folders and emails, he needs to scroll through these respective lists. For example, if he scrolls down one position in the list of folders, his screen will display folders 2…K+1, and then scrolling down one position further it will display folders 3…K+2. When FJ drags an email into a folder, the email disappears from the email list, and the emails after the one that disappeared shift up by one position. For example, if emails 1,2,3,4,5 are currently displayed and FJ drags email 3 into its appropriate folder, the email list will now show emails 1,2,4,5,6. FJ can only drag an email into the folder to which it needs to be filed.

Unfortunately, the scroll wheel on FJ's mouse is broken, and he can only scroll downwards, not upwards. The only way he can achieve some semblance of upward scrolling is if he is viewing the last set of K emails in his email list, and he files one of these. In this case, the email list will again show the last K emails that haven't yet been filed, effectively scrolling the top email up by one. If there are fewer than K emails remaining, then all of them will be displayed.

Please help FJ determine if it is possible to file all of his emails.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains T (1≤T≤10), the number of subcases in this input, all of which must be solved correctly to solve the input case. The T subcases then follow. For each subcase, the first line of input contains M, N, and K. The next line contains f1…fN.
It is guaranteed that the sum of M over all subcases does not exceed 104, and that the sum of N over all subcases does not exceed 10^5.

OUTPUT FORMAT (print output to the terminal / stdout):
Output T lines, each one either containing either YES or NO, specifying whether FJ can successfully file all his emails in each of the T subcases.
SAMPLE INPUT:
6
5 5 1
1 2 3 4 5
5 5 1
1 2 3 5 4
5 5 1
1 2 4 5 3
5 5 2
1 2 4 5 3
3 10 2
1 3 2 1 3 2 1 3 2 1
3 10 1
1 3 2 1 3 2 1 3 2 1
SAMPLE OUTPUT:
YES
YES
NO
YES
YES
NO
SCORING:
In inputs 2-10, the sum of M over all subcases does not exceed 10^3.
In inputs 11-12, no additional constraints.
Problem credits: Brian Dean

Bessie is learning how to control a robot she has recently received as a gift.
The robot begins at point (0,0) on the coordinate plane and Bessie wants the robot to end at point (xg,yg). Bessie initially has a list of N (1≤N≤40) instructions to give to the robot, the i-th of which will move the robot xi units right and yi units up (or left or down when xi and yi are negative, respectively).

For each K from 1 to N, help Bessie count the number of ways she can select K instructions from the original N such that after the K instructions are executed, the robot will end at point (xg,yg).

**Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N. The next line contains xg and yg, each in the range −10^9…10^9. The final N lines describe the instructions. Each line has two integers xi and yi, also in the range −10^9…10^9.
It is guaranteed that (xg,yg)≠(0,0) and (xi,yi)≠(0,0) for all i.

OUTPUT FORMAT (print output to the terminal / stdout):
Print N lines, the number of ways Bessie can select K instructions from the original N for each K from 1 to N.
SAMPLE INPUT:
7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10
SAMPLE OUTPUT:
0
2
0
3
0
1
0
In this example, there are six ways Bessie can select the instructions:

(-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (1 2 3 5 6 7)
(-2,0) (3,0) (4,0) (0,10) (1 2 3 5)
(-2,0) (3,0) (4,0) (0,10) (1 2 3 7)
(5,0) (0,10) (0,-10) (0,10) (4 5 6 7)
(5,0) (0,10) (4 5)
(5,0) (0,10) (4 7)
For the first way, the robot's path looks as follows:

(0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10)
SCORING:
Test cases 2-4 satisfy N≤20.
Test cases 5-16 satisfy no additional constraints.
Problem credits: Alex Liang

Farmer John has N gifts labeled 1…N for his N cows, also labeled 1…N (1≤N≤500). Each cow has a wishlist, which is a permutation of all N gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.
FJ was lazy and just assigned gift i to cow i for all i. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.

For each i from 1 to N, compute the most preferred gift cow i could hope to receive after reassignment.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N. The next N lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of 1…N.
OUTPUT FORMAT (print output to the terminal / stdout):
Please output N lines, the i-th of which contains the most preferred gift cow i could hope to receive after reassignment.
SAMPLE INPUT:
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
SAMPLE OUTPUT:
1
3
2
4
In this example, there are two possible reassignments:

The original assignment: cow 1 receives gift 1, cow 2 receives gift 2, cow 3 receives gift 3, and cow 4 receives gift 4.
Cow 1 receives gift 1, cow 2 receives gift 3, cow 3 receives gift 2, and cow 4 receives gift 4.
Observe that both cows 1 and 4 cannot hope to receive better gifts than they were originally assigned. However, both cows 2 and 3 can.

SCORING:
Test cases 2-3 satisfy N≤8.
Test cases 4-11 satisfy no additional constraints.