作者： chenchen

2022 年 12 月的比赛以算法编程问题为特色，涵盖了广泛的技术和难度级别。

在为期 4 天的比赛中，共有 14719 名不同的用户登录。共有 11798 名参与者提交了至少一个解决方案，来自 88 个不同的国家：

5378 USA 4259 CHN 444 CAN 332 KOR 142 IND 125 ROU 88 MYS 77 SGP 72 TWN 64 VNM 61 HKG 55 GEO 50 GBR 47 IRN 46 DEU 40 POL 36 ARM 28 FRA 28 EGY 25 AUS 21 AZE 18 ISR 18 BLR 17 UKR 17 KAZ 15 GRC 14 HRV 14 BGD 13 SLV 13 NZL 12 TUR 12 TUN 12 THA 12 CHE 12 BRA 10 KGZ 10 JPN 10 IDN 8 RUS 8 NLD 7 ZAF 7 SWE 7 SRB 7 MNG 7 ESP 7 BGR 6 SYR 6 PHL 5 MEX 5 LTU 5 COL 5 ARE 4 TKM 4 PER 4 NPL 4 EST 3 SVK 3 NGA 2 PRK 2 MDA 2 MAR 2 LUX 2 KHM 2 ITA 2 IRL 2 CYP 2 CUB 1 VEN 1 UZB 1 TJK 1 SHN 1 PRT 1 PAK 1 MLT 1 MAC 1 LVA 1 IRQ 1 HUN 1 GUM 1 FIN 1 DOM 1 CZE 1 CHL 1 BOL 1 BEL 1 AUT 1 ARG 1 AFG

总共有 26969 份评分提交，按语言细分如下：
12396 C++17
6423 C++11
4386 Java
3561 Python 3.6.9
178 C
25 Python 2.7.17

以下是白金、黄金、白银和铜牌比赛的详细结果。您还将找到每个问题的解决方案和测试数据，通过单击任何问题，您可以练习在“分析模式”下重新提交解决方案。 如果您已登录，您还将在下方看到您自己的具体结果以及您参加的比赛。

USACO 2022 年 12 月学术活动，白金

白金组共有412人参加，其中247人为预科生。我们在本次比赛中看到了相当多的满分，其中有4个来自美国。最佳得分手的结果在这里。祝贺所有优秀选手取得的优异成绩！

1 Breakdown
查看问题 | 测试数据 | 解决方案
2 Making Friends
查看问题 | 测试数据 | 解决方案
3 Palindromes
查看问题 | 测试数据 | 解决方案

USACO 2022 年 12 月学术活动，金牌

黄金组共有1035人参加，其中预科生721人。所有在本次比赛中获得 700 分或更高分的参赛者将自动晋升为白金组别。所有晋升者的详细结果都在这里。

1 Bribing Friends
查看问题 | 测试数据 | 解决方案
2 Mountains
查看问题 | 测试数据 | 解决方案
3 Strongest Friendship Group
查看问题 | 测试数据 | 解决方案

USACO 2022 年 12 月学术活动，银奖

银牌组共有2972人参加，其中预科生2216人。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为黄金组。

1 Barn Tree
查看问题 | 测试数据 | 解决方案
2 Circular Barn
查看问题 | 测试数据 | 解决方案
3 Range Reconstruction
查看问题 | 测试数据 | 解决方案

USACO 2022 年 12 月学术活动，铜奖

青铜组总参赛人数10226人，其中预科生8057人。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为银牌组。

1 Cow College
查看问题 | 测试数据 | 解决方案
2 Feeding the Cows
查看问题 | 测试数据 | 解决方案
3 Reverse Engineering
查看问题 | 测试数据 | 解决方案

最后的评论

对于那些尚未晋升的人，请记住，您练习得越多，您的算法编码技能就会越好——请坚持下去！USACO 比赛旨在挑战最优秀的学生，要想在比赛中脱颖而出，需要付出大量的努力。为了帮助您修复代码中的任何错误，您现在可以重新提交您的解决方案并使用“分析模式”从评审服务器获得反馈。

关于学术诚信在我们比赛中的重要性的简短说明：数百名参赛者因在本次比赛中作弊而被取消资格。作弊会被终身取消 USACO 晋级资格，教师、校长和大学招生人员通常不喜欢被告知在我们的比赛中作弊的学生（过去曾有学生因作弊而被学校开除）在 USACO 比赛中）。请尊重我们比赛的完整性。处理作弊是导致比赛结果发布时间过长的主要原因之一。

许多人为 USACO 比赛的质量和成功做出了贡献。为本次比赛提供帮助的人包括 Benjamin Qi、Freddie Tang、Mythreya Dharani、Timothy Feng、Nathan Wang、Sam Zhang、Joe Li、Larry Xing、Aryansh Shrivastava、Chongtian Ma、Jesse Choe、Yuval Vaknin、Danny Mittal、Nick Wu、Spencer Compton、Riya Arora、Jonathan Paulson、Claire Zhang、Andi Qu、Richard Qi、David Hu、Mark Chen、Daniel Zhang 和 Timothy Qian。还要感谢我们的翻译人员和克莱姆森 CCIT 为我们提供比赛基础设施。最后，我们感谢 USACO 赞助商的慷慨支持：Citadel、Ansatz、X-Camp、TwoSigma、EasyFunCoding 和 Jump Trading。

我们期待在 2023 年 1 月的比赛中再次见到大家。

编码愉快！

Elsie has a program that takes as input an array of N (1≤N≤100) variables b[0],…,b[N−1], each equal to zero or one, and returns the result of applying a sequence of if / else if / else statements on the input. Each statement examines the value of at most one input variable, and returns either zero or one. An example of such a program might be:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
For example, if the input to the program above is "10" (that is, b[0]=1 and b[1]=0), then the output should be 1.

Elsie has told Bessie the correct output for M (1≤M≤100) different inputs. Bessie is now trying to reverse engineer Elsie's program. Unfortunately, Elsie might have lied; it may be the case that no program of the form above is consistent with what Elsie said.

For each of T (1≤T≤10) test cases, determine whether Elsie must be lying or not.

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

The first line contains T, the number of test cases.
Each test case starts with two integers N and M, followed by M lines, each containing a string of N zeros and ones representing an input (that is, the values of b[0]…b[N−1]) and an additional character (zero or one) representing the output. Consecutive test cases are separated by newlines.

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

For each test case, output "OK" or "LIE" on a separate line.

SAMPLE INPUT:

4

1 3
0 0
0 0
1 1

2 4
00 0
01 1
10 1
11 1

1 2
0 1
0 0

2 4
00 0
01 1
10 1
11 0

SAMPLE OUTPUT:

OK
OK
LIE
LIE
Here's a valid program for the first test case:

if (b[0] == 0) return 0;
else return 1;
Another valid program for the first test case:

if (b[0] == 1) return 1;
else return 0;
A valid program for the second test case:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
Clearly, there is no valid program corresponding to the third test case, because Elsie's program must always produce the same output for the same input.

It may be shown that there is no valid program corresponding to the last test case.

SCORING:

Inputs 2 and 3 have N=2.
Inputs 4 and 5 have M=2.
Inputs 6 through 12 have no additional constraints.

Problem credits: Benjamin Qi

Farmer John has N (1≤N≤105) cows, the breed of each being either a Guernsey or a Holstein. They have lined up horizontally with the cows occupying positions labeled from 1…N.

Since all the cows are hungry, FJ decides to plant grassy patches on some of the positions 1…N. Guernseys and Holsteins prefer different types of grass, so if Farmer John decides to plant grass at some location, he must choose to planting either Guernsey-preferred grass or Holstein-preferred grass --- he cannot plant both at the same location. Each patch of grass planted can feed an unlimited number of cows of the appropriate breed.

Each cow is willing to move a maximum of K (0≤K≤N−1) positions to reach a patch. Find the minimum number of patches needed to feed all the cows. Also, print a configuration of patches that uses the minimum amount of patches needed to feed the cows. Any configuration that satisfies the above conditions will be considered correct.

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

Each input contains T test cases, each describing an arrangement of cows. The first line of input contains T (1≤T≤10). Each of the T test cases follow.
Each test case starts with a line containing N and K. The next line will contain a string of length N, where each character denotes the breed of the ith cow (G meaning Guernsey and H meaning Holstein).

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

For each of the T test cases, please write two lines of output. For the first line, print the minimum number of patches needed to feed the cows. For the second line, print a string of length N that describes a configuration that feeds all the cows with the minimum number of patches. The ith character, describing the ith position, should be a '.' if there is no patch, a 'G' if there is a patch that feeds Guernseys, and a 'H' if it feeds Holsteins. Any valid configuration will be accepted.

SAMPLE INPUT:

6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH

SAMPLE OUTPUT:

5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HG

Note that for some test cases, there are multiple acceptable configurations that manage to feed all cows while using the minimum number of patches. For example, in the fourth test case, another acceptable answer would be:

.GH..

This corresponds to placing a patch feeding Guernseys on the 2nd position and a patch feeding Holsteins on the third position. This uses the optimal number of patches and ensures that all cows are within 3 positions of a patch they prefer.

SCORING:

Inputs 2 through 4 have N≤10.
Inputs 5 through 8 have N≤40.
Inputs 9 through 12 have N≤105.

Problem credits: Mythreya Dharani

Farmer John is planning to open a new university for cows!

There are N (1≤N≤105) cows who could potentially attend this university. Each cow is willing to pay a maximum tuition of ci (1≤ci≤106). Farmer John can set the tuition that all cows must pay to enroll. If this tuition is greater than the maximum a cow is willing to pay, then the cow will not attend the university. Farmer John wants to make the most possible money so he can pay his instructors a fair wage. Please determine how much money he can make, and how much tuition he should charge.

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

The first line contains N. The second line contains N integers c1,c2,…,cN, where ci is the maximum tuition cow i is willing to pay.

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

Please output the maximum amount of money Farmer John can make and the optimal tuition he should charge. If there are multiple solutions, output the solution with the smallest optimal tuition.
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" in Java, a "long long" in C/C++).

SAMPLE INPUT:

4
1 6 4 6

SAMPLE OUTPUT:

12 4
If Farmer John charges 4, then 3 cows will attend, allowing him to make 3⋅4=12.

SCORING:

Test cases 2 through 4 have ci≤1,000.
Test cases 5 through 8 have N≤5,000.
Test cases 9 through 12 have no additional constraints.
Problem credits: Freddie Tang