分类： 赛事资讯

Farmer John has a favorite string t with M characters. He also has N strings s₁,s₂,…,s_N each with M characters (1≤N,M≤1000).

FJ can perform the following two types of operations:

FJ chooses any string sx
and two indices p
and q
. Then, he swaps the p
'th and q
'th character of sx
(1≤x≤N,1≤p,q≤M
).
FJ chooses two strings sx
and sy
and an index k
. Then, he swaps the k
'th characters of sx
and sy
(1≤x,y≤N,1≤k≤M
).
His goal is to make s1
equal to t
. Find any series of operations that fulfills his goal. Because FJ is in a hurry, he only has time to perform a total of 2M
operations. The inputs guarantee that it is possible to fulfill FJ's goal.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T
(1≤T≤10
), the number of independent tests. Each test is specified in the following format:
The first line contains N
and M
.

The second line contains t
.

Then, N
lines follow, the i
'th of which contains si
.

The inputs will guarantee that it is possible to fulfill FJ's goal. All strings contain lowercase English letters (a-z).

OUTPUT FORMAT (print output to the terminal / stdout):
The output for each test should be as follows:
On the first line, output an integer K
, the number of operations you will perform. K
must be a non-negative integer less than or equal to 2M
.

Then, output K
lines, denoting the operations you will perform in sequential order. Each line should be one of the following:

1 x p q
2 x y k
SAMPLE INPUT:
3
3 6
banana
nabana
banana
nnbaaa
5 3
abc
def
bca
ghi
jkl
mno
3 5
abcde
abcde
abcde
zzzzz
SAMPLE OUTPUT:
3
2 1 2 1
1 1 3 5
2 1 2 5
5
1 2 1 3
2 1 2 1
1 2 2 3
2 1 2 2
2 1 2 3
0
Here is how s
changes according to the first test's output (with letters swapped in uppercase):

nabana Babana baNaBa banaNa
banana -> Nanana -> nanana -> nanaBa
nnbaaa nnbaaa nnbaaa nnbaaa
After all three operations, s1=t
.

SCORING:
Inputs 2-6: N,M≤100
Inputs 7-12: No additional constraints.
Problem credits: Chongtian Ma

For all positive integers x, the function f(x) is defined as follows:

If x has any digits that aren't 0 or 1, for each digit of x, set it to 1, if it is odd or 0
otherwise, and return x.

Otherwise, return x−1.

Given a value of x (1≤x<), find how many times f needs to be applied to x until x reaches 0. As this number might be very large, output its remainder when divided by 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T (1≤T≤10⁵), the number of independent tests.

The next T lines each contain a positive integer x consisting solely of the digits 0-9, with no leading zeros.

It is guaranteed that the total number of digits in all input integers does not exceed 10⁶ .

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the remainder of the number of times when divided by 10⁹+7 on a separate line.

SAMPLE INPUT:

2
24680
210

SAMPLE OUTPUT:

1
4

First test: x becomes zero after one operation.

Second test: f(x)=10,f2(x)=9,f3(x)=1,f4(x)=0

SAMPLE INPUT:

1
1234567890123456789012345678901234567890

SAMPLE OUTPUT:

511620083

SCORING:

Inputs 3-5: T≤2000, x<10⁹
Inputs 6-7: x<10¹⁸ 
Inputs 8-9: x<10⁶⁰
Inputs 10-12: No additional constraints.

Problem credits: Aidan Bai

You have an integer array a₁…a_N with elements initially in the range [1,N](1≤N≤2⋅10⁵), as well as a nonzero integer K(−N≤K≤N,K≠0).

You may perform the following operation as many times as you'd like (possibly zero): select an index i and set a_i=a_i+K.

Find the minimum number of operations to make all array elements distinct.

INPUT FORMAT (input arrives from the terminal / stdin):

The input consists of T (1≤T≤10) independent tests. Each test is described as follows:

The first line contains N and K.

The second line contains a₁…a_N .

It is guaranteed that the sum of N over all tests does not exceed 10⁶.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test, output a single line containing the minimum number of operations.

Note: The large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

4
4 1
4 1 4 1
4 -3
4 1 4 1
4 4
4 1 4 1
3 -1
1 1 2

SAMPLE OUTPUT:

2
4
2
1

For the first test, here is a possible sequence of two operations that makes all elements distinct.

4 1 4 1
5 1 4 1 (a_1 += 1)
5 1 4 2 (a_4 += 1)

SCORING:

Inputs 2-4: N≤50
Inputs 5-7: N≤2000
Inputs 8-10: K=1
Inputs 11-13: No additional constraints.

Problem credits: Akshaj Arora, Benjamin Qi

You have N (2≤N≤10⁵,N is even) points (x_i,y_i)(1≤x_i,y_i≤10⁶) on an infinite 2D-coordinate plane.

You can perform the following two types of operations any number of times:

Choose two points that are directly adjacent to each other (manhattan distance of 1), and remove both points.

Choose any two points and swap their y-coordinates. Formally, points (a,b) and (c,d) become (a,d) and (c,b) respectively.

Determine if it is possible to eliminate all points on the board. Note that it may be the case that two points may map to the same coordinate; they should still be treated as different points. You also may not directly delete points on the same coordinate, as they are technically not directly adjacent.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T (1≤T≤5000), the number of test cases.

The first line of each test case contains an integer N.

The following N lines contain two integers x_i and y_i.

It is guaranteed that the sum of N over all test cases does not exceed 5⋅10⁵.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output "YES" or "NO" on a new line.

SAMPLE INPUT:

4
2
1 1
1 1
4
6 10
7 11
8 1
8 1
6
1 2
1 3
1 4
1 5
10 10
11 10
6
1 1
1 1
1 1
1 1
10 10
11 11

SAMPLE OUTPUT:

NO
YES
YES
NO

For the first test, the only two points are equal, so no swaps will do anything. Thus, our answer is NO.

In the second test, we can swap the y-coordinates of 6 and 7 with 8 and 8. Then, we can remove the first two points (horizontal adjacency) and the last two (vertical).

For the third test, no swaps are needed. We can remove the first pair, second, and third.

In the last test, it can be shown that no matter how we swap the y-coordinates, we will never be able to remove all the points in adjacent pairs.

SCORING:

Input 2: T≤1000, N≤6
Inputs 3-5: N≤100
Inputs 6-11: No additional constraints.

Problem credits: Alex Pylypenko, Chongtian Ma

There are N (1≤N≤2⋅10⁵) buckets in a stack where the i-th bucket from the top has capacity ai gallons (1≤a_i≤10⁹). A tap above the top bucket sends one gallon of milk per second into the first bucket per second. There is also a pool below bucket N.

When a bucket reaches its capacity after t seconds, at the start of the t+1 th second it flips to dump its contents into either the bucket below if it is not the last bucket or the pool otherwise (it reverts back to filling at the end of the t+1th second). A bucket cannot collect milk while it is flipped; any milk arriving at the bucket above during this second is lost. Additionally, any amount of milk exceeding the capacity of the bucket below is lost.

Handle Q (1≤Q≤3⋅10⁵) queries, each specified by three integers i, v, and t:

1.First, set a_i =v (1≤i≤N,1≤v≤10⁹).
2.Then answer the following question: Suppose that at time 0, all buckets as well as the pool are empty. Determine the number of gallons of milk in the pool after t seconds (1≤t≤ 10¹⁸ ).

The a_i=v updates persist through later queries.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

The second line contains a₁…a_N.

The next line contains Q.

Then the following Q lines contain three integers i, v, and t. This means that you should set a_i=v and then answer the question for t.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the answer to each question on a separate line.

SAMPLE INPUT:

3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 10

SAMPLE OUTPUT:

0
0
0
1
1
2
2
3
3
4
0
0
0
0
1
1
1
2
2
2
0
0
0
0
1
1
1
2
2
2

When a=[1,1,1],

Bucket 1 flips at times 2,4,6,…
Bucket 2 flips at times 3,5,7,…
Bucket 3 flips at times 4,6,8,…

When a=[2,1,1],

Bucket 1 flips at times 3,6,9,…
Bucket 2 flips at times 4,7,10,…
Bucket 3 flips at times 5,8,11,…

When a=[2,2,1],

Bucket 1 flips at times 3,6,9,…
Bucket 2 flips at times 4,7,10,…
Bucket 3 flips at times 5,8,11,…

SAMPLE INPUT:

2
1 2
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10

SAMPLE OUTPUT:

0
0
0
0
2
2
2
2
4
4

SAMPLE INPUT:

3
1 1 1
1
1 1 1000000000000000000

SAMPLE OUTPUT:

499999999999999999

SCORING:

Inputs 4-5: N≤10,Q≤100, and all t≤10⁴
Inputs 6-11: N≤103,Q≤10⁴
Inputs 12-23: No additional constraints.

Problem credits: Akshaj Arora

Farmer John is playing a famous and strategic card game with his dear cow Bessie. FJ has N (2≤N≤2⋅10⁵) cards, conveniently numbered from 1 to N. The i'th card costs a_i (1≤a_i ≤10⁹) moolixir if FJ wants to play it.

His hand always consists of H cards at any given time (1≤H<N). Initially, his hand consists of cards 1 through H. The remaining cards are in a draw queue. Every time FJ plays a card in his hand, he will draw its replacement from the front of the draw queue to his hand. Then, FJ will put the card he just played to the back of the draw queue. Initially, cards H+1 through N are arranged from the front to the back of the draw queue in that order.

In this game, time is measured in integer seconds. Initially, the game starts at time 0 with FJ having 0 moolixir. Immediately before each of integer times t=1,2,3,…,moolixir increases by 1. At each integer time, FJ may choose to play a card in his hand if its cost does not exceed FJ's current moolixir count, which subtracts FJ's current moolixir count by the card's cost.

FJ marks a subset of his cards s1,s2,…,sK as win-conditions (1≤k≤N, 1≤s_i≤N). If FJ has at least one win-condition in his hand, the next card he plays must be a win-condition.

He asks you Q (1≤Q≤2⋅10⁵ ) queries. Each query is of the following form: what is the maximum number of win-conditions he could have placed down within t time (1≤t≤10¹⁸)?

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and H.

The second line contains N integers a₁,a₂,…,a_N .

The third line contains an integer k, the number of win-conditions.

The fourth line contains k distinct integers s₁,s₂,…,s_K.

The fifth line contains an integer Q.

The following Q lines each contain an integer t, the time to answer for each query.

OUTPUT FORMAT (print output to the terminal / stdout):

For each query, output the maximum number of win-conditions that FJ could've put down within t time.

SAMPLE INPUT:

6 3
2 4 3 5 7 6
2
1 4
6
1
2
3
7
10
1000000000000000

SAMPLE OUTPUT:

0
1
1
2
2
142857142857143

In this case, you start with card 1, a win condition on your hand. You can play it after you accumulate 2 elixir in 2 seconds. This means that just after t=1 you can play no cards, but after t=2 you can play your first card, which must be your win condition.

After t=3, it is still most optimal to play card 1 and have 1 elixir remaining, so the answer here is still 1.

You then draw card 4, which is also a win condition. You play it immediately after t=7, so you have played 2 win conditions at this time.

You then draw card 5 and have no win conditions in your hand. After t=10, even if you play card 3 with the 3 elixir you have, your number of win conditions does not change.

SCORING:

Inputs 2-3: N,Q≤100
Inputs 4-5: H=1
Inputs 6-11: No additional constraints.

Problem credits: Chongtian Ma

Suppose the function randint(l,r) returns an integer independently and uniformly at random from the range [l,r].

Bessie generates a random labeled tree on N vertices (2≤N≤2⋅10⁵) using the following two-step process:

1.Start with vertices labeled 1 through N. For each i from 2 to N, add an edge between vertex i and randint(1,i−1).

2.Choose a permutation p₁,p₂,…,p_N of {1,2,…,N} uniformly at random. Relabel every vertex v as p_v.

Now, Farmer John is looking at the edge set of the final tree and wants to know the probability that the two-step process above produces a tree with exactly this edge set. Can you determine this probability modulo 10⁹+7?

INPUT FORMAT (input arrives from the terminal / stdin):

The input consists of T(1≤T≤10) independent inputs. Each input is specified as follows:

The first line contains N.

The next N−1 lines contain the edges of the tree specified by two space-separated integers u and v (1≤u,v≤N). It is guaranteed that these edges induce a tree.

It is guaranteed that the sum of N across all tests does not exceed 5⋅10⁵.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test, output the probability modulo 10⁹+7 on a new line (note that the output probability is a ratio of integers, so you will want to print the result of this division when working modulo 10⁹+7).

SAMPLE INPUT:

4
2
2 1
3
1 2
2 3
4
1 2
2 3
2 4
4
1 2
2 3
3 4

SAMPLE OUTPUT:

1
333333336
83333334
55555556

The probabilities are 1, 1/3, 1/12, 1/18.

First test: There is only one tree on N=2 vertices, so the probability of generating it is just 1.

Second test: there are three trees on N=3 vertices, and each of them is equally likely to have been generated by the process above. And 1/3≡333333336(mod 10⁹+7).

SCORING:

Input 2-3: N≤8
Inputs 4-9: N≤2000
Inputs 10-21: No additional constraints.

Problem credits: Benjamin Qi

**Note: The time limit for this problem is 3s, 1.5x the default.**

Farmer John's farm structure can be represented as a connected undirected graph with N vertices and M unweighted edges (2≤N≤2⋅10⁵,N−1≤M≤2⋅10⁵
). Initially, Farmer John is at his barn, represented by farm 1.

Initially, farms s₁,s₂,…,s_K contain flower fields and farms d₁,d₂,…,d_L are destination farms. FJ calls a path pretty if:

It starts at farm 1.
It ends at some destination farm x.
There is no shorter path starting at farm 1and ending at farm x.
FJ visits all flower fields along the way.

FJ can wave his magic wand and make up to one more farm contain a flower field (if it doesn't already). However, FJ isn't very decisive. For farms f numbered 2 through N, after FJ temporarily makes farm f contain a flower field, determine if there exists a pretty path.

Note that there are multiple test cases, and each case must be treated independently.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T (1≤T≤100), the number of independent test cases.

The first line of each test case contains N, M, K, and L(0≤K≤N−1,1≤L≤N−1).

The following line contains s₁,s₂,…,s_K ( 2≤ s_i ≤N, siare all distinct ).

The following line contains d₁,d₂,…,d_L (2≤d_i≤N, d_i are all distinct).

The following M lines contain u and v, denoting there is an undirected edge between farms u and v. All edges are considered to have equal length. It is guaranteed that there aren't any multi-edges or self loops.

It is guaranteed that both the sum of N and the sum of M do not exceed 10⁶ over all test cases.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output a binary string of length N−1. The i'th character in the string should be 1 if the answer holds true for the (i+1)'th farm.

SAMPLE INPUT:

1
7 7 0 1

5
1 2
2 3
3 4
4 5
5 6
6 7
3 6

SAMPLE OUTPUT:

111110

Since 5 is the only destination farm, the answer holds true if the i'th farm lies on any shortest path from 1 to 5.

There are two shortest paths from 1 to 5, which are 1→2→3→4→5 and 1→2→3→6→5.

Since there are no farms that already contain flower fields, the answer for farm i
holds true if farm i lies on at least one of the two aforementioned paths.

SAMPLE INPUT:

1
6 6 0 2

5 3
1 2
2 3
3 4
4 5
5 6
2 5

SAMPLE OUTPUT:

11010

There are two destination farms: 5 and 3. Since there are no farms that already contain flower fields, the i'th farm must lie on a shortest path to either 5 or 3. Since farm 2 lies on a shortest path to farm 5, so the answer holds for farm 2. Trivially, farm 3 lies on the shortest path to farm 3 and farm 5 lies on the shortest path to farm 5.

SAMPLE INPUT:

3
4 3 2 1
2 3
4
1 2
2 3
3 4
4 4 2 1
2 3
4
1 2
1 3
2 4
3 4
5 5 2 1
2 4
5
1 2
1 3
2 4
3 4
4 5

SAMPLE OUTPUT:

111
000
1011

For the first test case, the answer holds true for the i'th farm if FJ can pass through farm i, farm 2, and farm 3 (in no particular order) on some shortest path to farm 4. It can be shown that the answer holds true for all farms.

SCORING:

Inputs 4-6: K=0and L=1
Inputs 7-9: K=0
Inputs 10-23: No additional constraints

Problem credits: Chongtian Ma

USACO 2026赛季的第三场比赛涵盖了涵盖多种技术和难度的算法编程问题。

在为期四天的比赛期间，共有7302名不同用户登录了该活动。共有5084名参与者提交了至少一个解决方案，来自100+个不同国家。3203名参与者来自美国，中国、加拿大、韩国、马来西亚、印度和新加坡的参与度较高。

总共有14003份评分提交，按语言分类如下：

8997 C++17
2349 Python-3.6.9
1479 Java
1052 C++11
99 C
27 Python-2.7.17

以下是白金、金、银和铜三项比赛的详细成绩。 你还可以找到每个问题的解决方案和测试数据，点击任意 问题你可以练习在“分析模式”下重新提交解答。

USACO 2026年 第三场 比赛，白金奖

白金组共有300名参与者，其中243名是大学预科生。

1 All Pairs Shortest Paths
查看问题 | 测试数据 | 解决方案
2 Blast Damage
查看问题 | 测试数据 | 解决方案
3 Min Max Subarrays II
查看问题 | 测试数据 | 解决方案

USACO 2026年 第三场 比赛，金奖

金组共有1245名参与者，其中910名是大学预科生。所有在本比赛中得分达到750分或以上的选手将自动晋级白金组。

1 Good Cyclic Shifts
查看问题 | 测试数据 | 解决方案
2 Picking Flowers
查看问题 | 测试数据 | 解决方案
3 Random Tree Generation
查看问题 | 测试数据 | 解决方案

USACO 2026年 第三场 比赛，银奖

银组共有2446名参赛者，其中1916人为预科生。所有在本比赛中得分达到700分或以上的选手将自动晋级金组。

1 Clash!
查看问题 | 测试数据 | 解决方案
2 Milk Buckets
查看问题 | 测试数据 | 解决方案
3 Point Elimination
查看问题 | 测试数据 | 解决方案

USACO 2026年 第三场 比赛，铜奖

铜组共有3014名参赛者，其中2374人为大学预科生。所有在本比赛中得分达到700分或以上的选手将自动晋级银组。

1 Make All Distinct
查看问题 | 测试数据 | 解决方案
2 Strange Function
查看问题 | 测试数据 | 解决方案
3 Swap to Win
查看问题 | 测试数据 | 解决方案

结语

我对本季第三场也是最后一场“标准级”竞赛的结果感到满意。从技术层面看，一切进展非常顺利（我们在第二场竞赛中发现负载相关问题后对基础设施进行了升级，这些改进似乎取得了显著成效）。尽管本次竞赛的题目难度依然极高，但多个组别的大量选手均获得了晋级。我和USACO团队仍需投入超出理想时长的精力处理学术诚信相关事务（例如手动审核提交内容、向校方负责人提交报告等），但这些工作对于维持我们与他人所期待的竞赛高标准诚信至关重要。生成式人工智能加剧了这一挑战，但我们希望通过加强监考措施来缓解这一问题——我们期待本季最后一场邀请制监考竞赛能够顺利进行。

对于尚未晋级的选手，请记住：实践越多，你的算法编码能力就会越强——请坚持下去！USACO竞赛旨在挑战最顶尖的学生，要想脱颖而出需要付出大量努力。现在，你还可以通过"分析模式"重新提交解题方案，并从判题服务器获得反馈，以帮助修复代码中的错误。

For a permutation p₁,p₂,…,p_N of 1…N (1≤N≤2⋅10⁵), let f(p)=. A permutation is good if it can be turned into the identity permutation using at most f(p) swaps of adjacent elements.

Given a permutation, find which cyclic shifts of it are good.

INPUT FORMAT (input arrives from the terminal / stdin):

The input consists of T (1≤T≤10⁵) independent tests. Each test is specified as follows:

The first line contains N.

The second line contains p₁,p₂,…,p_N (1≤p_i≤N), which is guaranteed to be a permutation of 1…N.

It is guaranteed that the sum of N over all tests does not exceed 10⁶ .

OUTPUT FORMAT (print output to the terminal / stdout):

For each test, output two lines:

On the first line, output the number of good cyclic shifts k.

Then output a line with k space-separated integers s (0≤s<N) in increasing order, meaning that p is good when cyclically shifted to the right s times.

SAMPLE INPUT:

3
5
5 4 3 2 1
4
1 2 4 3
5
1 2 3 4 5

SAMPLE OUTPUT:

0

2
0 1
5
0 1 2 3 4

Consider the second test case, where p=[1,2,4,3].

f(p)=(|1−1|+|2−2|+|4−3|+|3−4|)/2=1. Since p can be turned into the identity permutation in one move by swapping p₃ and p₄, p is good.

Cyclically shifting p to the right 1 time, we get q=[3,1,2,4]. f(q)(|3−1|+|1−2|+|2−3|+|4−4|)/2=2. Since q can be turned into the identity permutation in two moves by swapping q₁ two steps forward, q is good.

It can be seen that the other two cyclic shifts are not good.

SCORING:

Input 2: N≤10
Inputs 3-5: T≤10,N≤2000
Inputs 6-11: No additional constraints.
Problem credits: Akshaj Arora