作者： chenchen

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

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

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

12569 C++17
2981 Python-3.6.9
1983 Java
1816 C++11
100 C
14 Python-2.7.17

顺便说一句，我们正在努力增加对PyPy的支持，以帮助Python选手在计算要求更高的问题上获得更高分数。

以下是白金、金、银和铜三项比赛的详细成绩。 你还可以找到每个问题的解决方案和测试数据。

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

白金组共有180名参与者，其中141名是大学预科生。与赛季首场比赛一样，白金题目极具挑战性，美国参赛者得分超过500分的美国选手不到十人。顶尖竞争者的结果将在学术诚信审核结束后公布。

1 Circle of Cows
查看问题 | 测试数据 | 解决方案
2 Cow Circle
查看问题 | 测试数据 | 解决方案
3 Dynamic Instability
查看问题 | 测试数据 | 解决方案

USACO 2026年 第二场 比赛，金奖

黄金组共有1366名参赛者，其中962名为在校生。我们的教练团队仍在进行学术诚信审核，审核结果可能影响晋级分数线——该分数线将在审核流程完成后尽快公布

1 Balancing the Barns
查看问题 | 测试数据 | 解决方案
2 Lexicographically Smallest Path
查看问题 | 测试数据 | 解决方案
3 The Chase
查看问题 | 测试数据 | 解决方案

USACO 2026年 第二场 比赛，银奖

银级共有2721名参赛者，其中1964名为预科生。本次竞赛中得分700分及以上的选手将自动晋升至金级。

1 Cow-libi 2
查看问题 | 测试数据 | 解决方案
2 Declining Invitations
查看问题 | 测试数据 | 解决方案
3 Farmer John Loves Rotations
查看问题 | 测试数据 | 解决方案

USACO 2026年 第二场 比赛，铜奖

铜牌组共有5137名参赛者，其中3876名是大学预科生。所有在本次比赛中获得700分或更高分数的参赛者将自动晋升为银牌组。

1 It's Mooin' Time IV
查看问题 | 测试数据 | 解决方案
2 Moo Hunt
查看问题 | 测试数据 | 解决方案
3 Purchasing Milk
查看问题 | 测试数据 | 解决方案

结语

2025-26赛季现在正在顺利进行，在宣布有监督的美国公开赛邀请之前，只剩下一场比赛了。总的来说，本赛季的第二场比赛非常成功，但有一个技术问题——在“认证”黄金/白金窗口结束时，负载激增，导致部分用户出现不必要的速度减慢（我们正在调查原因，并采取措施在未来缓解类似情况）。在赛季开始时，黄金组的绝大多数顶级竞争对手都开始了比赛，很高兴看到有相当多的人成功晋升回白金级别。铜组和银组也出现了大量晋升；祝贺所有在本赛季取得进步的人！

对于尚未晋升的人， 记住，练习越多，效果越好 你的算法编程技能将变得——拜托 继续努力！USACO比赛设计上甚至挑战了非常 最优秀的学生，这需要相当多的努力 要在这些领域出类拔萃。为了帮助你修复代码中的任何漏洞，你现在可以重新提交你的解决方案并获得反馈 使用“分析模式”评判服务器。

On National Milk Day, Farmer John is offering exclusive prices on buckets of milk! He has N (1≤N≤10⁵) deals numbered from 1 to N. For the i'th deal, he is offering 2i−1 buckets of milk for a_i (1≤a_i≤10⁹,a_i<a_i+1) moonies. The same deal may be taken any non-negative integer number of times.

You are thinking about Q (1≤Q≤10⁴ ) independent queries. For each query, you have an integer x (1≤x≤10⁹) in mind and wonder what is the minimum cost to purchase at least x buckets of milk.

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

The first line contains two integers N and Q.

The following line contains a₁,a₂,…,a_N.

Each of the following Q lines contains an integer x, representing a query.

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

For each query, output the minimum cost on a new line.

Note that 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:

2 4
10 15
1
2
6
7

SAMPLE OUTPUT:

10
15
45
55

In the example above, Farmer John is offering 2 deals: 1 bucket of milk for 10 moonies and 2 buckets of milk for 15 moonies.

The cheapest cost to buy 1 bucket is just the cost of the 1 bucket deal and the cheapest cost to buy 2 buckets is just the cost of the 2 bucket deal.

To get 6 buckets, the cheapest way is to purchase 3 of the 2 bucket deal for a total of 45 moonies.

To get 7 buckets, the cheapest way is to purchase 3 of the 2 bucket deal and 1 of the 1 bucket deal for a total of 55 moonies.

SAMPLE INPUT:

4 10
10 25 30 70
1
2
3
4
5
6
7
8
15
101

SAMPLE OUTPUT:

10
20
30
30
40
50
60
60
120
760

In this example, Farmer John is offering a total of 4 deals for 1, 2, 4, and 8 buckets. For each of the 10 queries, the corresponding output indicates the minimum cost to purchase at least that amount of milk. Sometimes, it is cheaper to purchase more than the specified amount.

SCORING:

Inputs 3-4: N≤2
Inputs 5-8: N≤10
Inputs 9-16: No additional constraints.

Problem credits: Chongtian Ma

Bessie is playing the popular game "Moo Hunt". In this game, there are N (3≤N≤20) cells in a line, numbered from 1 to N. All cells either have the character M or O with the i-th cell having character s_i.

Bessie plans to perform K (1≤K≤2⋅10⁵) mooves. On her i-th moove, Bessie will tap 3 different cells (x_i,y_i,z_i) (1≤x_i,y_i,z_i≤N). Bessie will earn a point if  s_xi=M
and s_yi=s_zi=O. In other words, Bessie will earn a point if she forms the string MOO by tapping cells x_i,y_i,z_i in that order.

Farmer John wants to help Bessie get a new high score. He wants you to find the maximum possible score Bessie could get across all possible boards if she performs the K mooves as well as the number of different boards that will allow Bessie to achieve this maximum possible score. Two boards are different if there exists a cell such that the corresponding characters at the cell are different.

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

The first line contains N and K, the number of cells and the number of mooves Bessie will perform.

Each of the next K lines contains x_i,y_i,z_i describing Bessie's i-th move (x_i,y_i,z_i are pairwise distinct).

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

Output the maximum possible score Bessie could achieve, followed by the count of different boards that will allow Bessie to achieve this maximum score.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4 2

The boards MOOOM and MOOMM allow Bessie to achieve a maximum score of 4. In both boards, Bessie will earn points on mooves 1,2,5,6. It can be shown that this is the maximum score Bessie can achieve, and those two boards are the only possible boards allowing Bessie to achieve a score of 4.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

6 3

The boards that allow Bessie to achieve a maximum possible score of 6 are OOMOOO, OOMMOO, and OOMOOM.

SCORING:

Inputs 3-5: N≤8,K≤10⁴

Inputs 6-12: There will be one test for each N∈{14,15,16,17,18,19,20} with no  additional constraints on K.

Problem credits: Alex Liang

Bessie has a computer with a keyboard that only has two letters, M and O.

Bessie wants to type her favorite moo S consisting of N letters, each of which is either an M or an O. However, her computer has been hit with a virus. Every time she tries to type the letter O, every letter that she has typed so far flips, either from M to O or from O to M, before the O appears.

Is it possible for Bessie to type out her favorite moo?

Additionally, Bessie is given a parameter k which is either 0 or 1.

If k=0, then Bessie only needs to determine whether it is possible to type out her favorite moo.

If k=1, then Bessie also needs to give an example of a sequence of keystrokes to type so she can type out her favorite moo.

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

The first line contains T, the number of independent test cases (1≤T≤10⁴) and k
(0≤k≤1).

The first line of each test case has N (1≤N≤2⋅10⁵).

The second line of each test case has S. It is guaranteed that no characters will  appear in S besides M and O.

The sum of N across all test cases will not exceed 4⋅10⁵.

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

For each test case, output either one or two lines using the following procedure.

If it is impossible for Bessie to type out S, print NO on a single line.

Otherwise, on the first line print YES. Furthermore, if k=1, on the second line,print a string of length N, the characters in order that Bessie needs to type in order to type out her favorite moo. If there are multiple such strings, any will be accepted.

SAMPLE INPUT:

2 0
3
MOO
5
OOMOO

SAMPLE OUTPUT:

YES
YES

SAMPLE INPUT:

2 1
3
MOO
5
OOMOO

SAMPLE OUTPUT:

YES
OMO
YES
MOOMO

As Bessie types out MOOMO, this is how the letters change:

1.Before typing the first M, Bessie has an empty string. Afterwards, she has the string M.

2.After typing the first O, the M flips to O, and then the O is appended to form OO.

3.After typing the second O, the OO flips to MM, and then the O is appended to form MMO.

4.After typing the second M, Bessie has the string MMOM.

5.After typing the last O, the string MMOM flips to OOMO, and then the O is  appended to form OOMOO, as desired.

SCORING:

Inputs 3-4: k=0.
Inputs 5-6: k=1,T≤10³,N≤10.
Inputs 7-9: k=1,T≤10,N≤1000.
Inputs 10-16: k=1.

Problem credits: Nick Wu

Farmer John has an array A containing N integers (1≤N≤5⋅10⁵,1≤A_i≤N). He picks his favorite index j and take out a sheet of paper with only  A_j written on it. He can then perform the following operation some number of times:

Cyclically shift all elements in A one spot to the left or one spot to the right. Then, write down A_j on a piece of paper.

Let S denote the set of distinct integers that occur in A. Farmer John wonders what the minimum number of operations he must perform is so that the paper contains all integers that appear in S.

Since it is unclear what FJ's favorite index is, output the answer for all possible favorite indices 1≤j≤N. Note for each index, A is reset to its original form before performing any operations.

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

The first line contains N.

The following line contains A₁,A₂,…,A_N.

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

Output N space-separated integers, where the i'th integer is the answer for his favorite index j=i.

SAMPLE INPUT:

6
1 2 3 1 3 4

SAMPLE OUTPUT:

4 3 3 4 3 3

The distinct numbers are S={1,2,3,4}. Suppose Farmer John’s favorite index is j=1. He starts off with A₁=1 written on a piece of paper. We can track the array A after each cyclic shift Farmer John makes.

Cyclic shift right: FJ writes down A₁=4.

4 1 2 3 1 3

Cyclic shift left: FJ writes down A₁=1 again.

1 2 3 1 3 4

Cyclic shift left: FJ writes down A₁=2.

2 3 1 3 4 1

Cyclic shift left: FJ writes down A₁=3.

3 1 3 4 1 2

At this point, Farmer John has written down every number in S using 4 operations.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

8 7 6 7 8 9 8 7 6 7 8 9

SCORING:

Inputs 3-5: N≤500
Inputs 6-8: N≤10⁴
Inputs 9-17: No additional constraints.

Problem credits: Chongtian Ma

N contestants participated in a contest, each placing a distinct rank from 1
to N. There are C criteria used to invite contestants to participate in the final round, and the ith-ranked contestant satisfies a specified n_i of them (1≤n_i ≤C).

The invitation process runs as follows. First, the top f₁ students who satisfy the 1
st criteria will be invited. Then, out of all students who haven't yet been invited, the top f₂ (or all remaining if there are fewer than f₂ remaining) students who satisfy the 2nd criterion will be invited. This process repeats, for each i
from 1 to C (1≤f_i≤N).

However, some contestants will decline to participate in the final round, in which case they will be ignored when determining who to invite.

You are given a permutation p₁,p₂,…,p_N of 1…N. For each i from 0 to N−1, determine the sum of the ranks of the contestants who will be invited if the participants with ranks given by the first i elements of p decline to attend.

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

The first line contains N and C (1≤N,C≤10⁵).

The next line contains f₁,f₂,…,f_C.

The next line contains p₁…,p_N.

The next N lines each contain ni (1≤n_i≤C), followed by n_i distinct integers in [1,C], representing the criteria that the i th-ranked contestant satisfies. It is guaranteed that ∑n_i≤10⁶.

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

Output N lines, the sum of ranks of invitees before each declination.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

6
6
9
6
4

There is only one criterion. The top three remaining contestants who have not declined will be invited.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

10
14
12
9
5

Initially, the ith contestant gets invited under criterion i for all 1≤i≤4.

After the first declination, the i+1th contestant gets invited under criterion i for all 1≤i≤4.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

21
20
16
10
5
3

SCORING:

Inputs 4-6: N,C≤103,∑ni≤104
Inputs 7-8: C=1
Inputs 9-10: C=2
Inputs 11-16: No additional constraints.

Problem credits: Benjamin Qi

Farmer John and Farmer Nhoj have taken their respective cows to sit around a campfire in hopes of settling their personal differences. In total, there are N
(2≤N≤10⁵) cows sitting in a circular formation. When the farmers are ready to take their cows back to their farms, they realize one crucial mistake: since all the cows look the same and are mixed up, they are unable to identify which cows belong to which farmer!

Then the N cows are organized into one straight line to be interrogated by the two farmers. Because of the confusion, the order of the cows in the line, from 1
to N, might not correspond to their circular order around the campfire.

But the cows want to play a game. Instead of answering directly which farmer they belong to, they say which farmer the cows adjacent to them in the original circle belong to. Additionally, it is known that Farmer Nhoj's cows always lie but Farmer John raised his cows well and they will always tell the truth.

Given the statements of the cows, is it possible to assign each cow to either Farmer John or Farmer Nhoj such that the statements of the cows assigned to Farmer John are all true, and the statements of the cows assigned to Farmer Nhoj are all false?

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

The first line contains T (1≤T≤1000), the number of independent test cases, and an integer C∈{0,1} (whether to output a construction or not).

The first line of each test case contains N.

The following line contains a string of length N containing characters J or N. The i'th character is J if cow i claims the cow to their left in the circle belongs to Farmer John, or Farmer Nhoj otherwise.

The following line contains a string of length N containing characters J or N. The i'th character is J if cow i claims the cow to their right in the circle belongs to Farmer John, or Farmer Nhoj otherwise.

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

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

For each test case, output YES or NO.

Additionally, if C=1 and the answer is YES, output two more lines describing your construction:

The first line should contain a permutation p₁,p₂,…,p_N of 1…N, representing the circular order of the cows around the campfire, where cow p_i is to the left of cow p_i+1 for i in 1…N−1, and cow p_N is to the left of cow p₁.

The second line should contain a string b₁b₂…b_N consisting only of Js and Ns, meaning that cow p_i belongs to Farmer John if b_i is J, or Farmer Nhoj otherwise.

Any valid construction will be accepted.

SAMPLE INPUT:

6 0
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

SAMPLE OUTPUT:

YES
NO
NO
YES
NO
YES
SAMPLE INPUT:
6 1
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

SAMPLE OUTPUT:

YES
1 2 3
JJJ
NO
NO
YES
1 2 3 4
NJNJ
NO
YES
4 5 2 1 3
JJJJN

Consider the output for the sixth test case. Cows 1, 2, 4, 5 belong to Farmer John, and Cow 3 belongs to Farmer Nhoj.

The cows will then behave as follows:

Cow 1's left and right neighbours are Cow 2 and Cow 3, respectively. Cow 1 says that Cow 2 belongs to Farmer John, and Cow 3 belongs to Farmer Nhoj.

Cow 2's left and right neighbours are Cow 5 and Cow 1, respectively. Cow 2 says that both cows belong to Farmer John.

Cow 3's left and right neighbours are Cow 1 and Cow 4, respectively. Cow 3 (dishonestly) says that both cows belong to Farmer Nhoj.

Cow 4's left and right neighbours are Cow 3 and Cow 5, respectively. Cow 4 says that Cow 3 belongs to Farmer Nhoj, and Cow 5 belongs to Farmer John.

Cow 5's left and right neighbours are Cow 4 and Cow 2, respectively. Cow 5 says that both cows belong to Farmer John.

All these claims are consistent with the input.

SCORING:

Input 3: C=0 and N≤10
Input 4: C=1 and N≤10
Inputs 5-8: C=0
Inputs 9-12: C=1

Problem credits: Chongtian Ma