作者： chenchen

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

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

5794 USA 5763 CHN 483 CAN 377 KOR 151 ROU 139 IND 127 ISR
124 MYS 120 SGP 103 TWN 72 HKG 68 POL 63 DEU 58 VNM
53 IRN 46 AUS 44 GBR 40 EGY 37 JPN 33 BLR 31 FRA
29 ABW 28 GEO 23 UZB 21 ARM 20 SLV 18 ZAF 18 NZL
18 BRA 17 HRV 16 NLD 16 CUB 13 IDN 13 CHE 12 TUR
12 TKM 11 SRB 11 PAK 11 ESP 11 BDI 10 THA 10 SYR
10 KGZ 10 ASM 9 BGD 9 AUT 9 ARE 8 UKR 8 PHL
8 COL 8 CHL 8 AZE 7 AIA 6 TUN 6 SWE 6 RUS
6 MEX 6 KAZ 6 AGO 5 ITA 5 IRL 5 GRC 5 FIN
5 EST 5 ANT 5 ALA 4 PRK 4 MNG 4 MLT 4 LTU
4 HUN 4 CYP 4 ATG 4 ARG 4 AND 4 ALB 4 AFG
3 MKD 3 MAC 3 KEN 3 HTI 3 CCK 3 BGR 2 YEM
2 VGB 2 QAT 2 PRT 2 NOR 2 MCO 2 GHA 2 BWA
2 BLM 2 BEL 1 ZWE 1 VUT 1 VEN 1 URY 1 UGA
1 TTO 1 TJK 1 SWZ 1 SMR 1 SAU 1 PSE 1 NPL
1 NGA 1 NER 1 NAM 1 MNE 1 MAR 1 LUX 1 LSO
1 LAO 1 KHM 1 ISL 1 IOT 1 HMD 1 GUY 1 GUM
1 GMB 1 GAB 1 FSM 1 FJI 1 DNK 1 DJI 1 CZE
1 CRI 1 CMR 1 CIV 1 BLZ 1 BHS 1 BHR

共有 67 名白金美国大学预科参与者参加了“认证”比赛 比赛窗口。在整个比赛中，共有 38095 份分级作品，按语言细分如下：

20207 C++17
7673 C++11
5342 Python 3.6.9
4633 Java
195 C
45 Python 2.7.17

以下是每场白金、黄金、白银和铜牌比赛的详细结果。 您还可以找到每个问题的解决方案和测试数据。

USACO 2023 年 12 月学术活动，白金奖

白金部门共有 673 名参与者，其中 455 名是大学预科生。最佳得分手的成绩在这里。恭喜所有顶尖选手取得优异成绩！

1 Cowntact Tracing
查看问题 | 测试数据 | 解决方案
2 A Graph Problem
查看问题 | 测试数据 | 解决方案
3 Train Scheduling
查看问题 | 测试数据 | 解决方案

USACO 2023 年 12 月比赛，金奖

黄金组共有 1375 名参与者，其中 980 名是大学预科生。所有在本次比赛中得分达到或超过800分的选手将自动晋升为白金组。所有晋升者的详细结果都在这里。

1 Flight Routes
查看问题 | 测试数据 | 解决方案
2 Minimum Longest Trip
查看问题 | 测试数据 | 解决方案
3 Haybale Distribution
查看问题 | 测试数据 | 解决方案

USACO 2023 年 12 月比赛，银奖

白银组共有3841名参与者，其中2967名是大学预科生。所有在本次比赛中得分达到或超过750分的参赛者将自动晋升为黄金组。

1 Bovine Acrobatics
查看问题 | 测试数据 | 解决方案
2 Cycle Correspondence
查看问题 | 测试数据 | 解决方案
3 Target Practice
查看问题 | 测试数据 | 解决方案

USACO 2023 年 12 月比赛，铜奖

青铜组共有12591名参赛者，其中9707名是大学预科生。所有在本次比赛中得分达到或超过700分的选手将自动晋升为银牌组。

1 Candy Cane Feast
查看问题 | 测试数据 | 解决方案
2 Cowntact Tracing 2
查看问题 | 测试数据 | 解决方案
3 Farmer John Actually Farms
查看问题 | 测试数据 | 解决方案

结语

欢迎来到 2023-2024 USACO 赛季！我很高兴看到我们的 第一届比赛进行得很顺利，涉及的用户数量创下了历史新高。相当多的参与者得分很高并得到了晋升，尽管这是一场具有挑战性的问题阵容。看到如此强劲的表现令人鼓舞，特别是考虑到人工智能等领域的最新创新和势头可能在上升，因而对具有卓越计算机天赋的学生的要求越来越高。

对于那些尚未晋升的人， 请记住，练习越多越好 你的算法编码技能将成为 -- 拜托坚持下去！USACO竞赛旨在挑战甚至最好的学生，这可能需要大量的努力在他们身上出类拔萃。为了帮助您修复代码中的任何错误，您需要 现在可以重新提交您的解决方案并从 使用“分析模式”判断服务器。

很多人为质量做出了贡献以及USACO竞赛的成功。那些帮助过这件事的人 参赛作品包括Mihir Singhal、Agastya Goel、Chongtian 马、Suhas Nagar、Eric Hsu、Benjamin Qi、Claire Zhang、Spencer Compton、Brandon Wang、Nick Wu、Jichao Qian、Nathan Wang、Danny Mittal、Andi Quad、Ho Tin Fan、Benjamin Chen、David 胡、Richard Qi、Andrew Gu和Anand John。 谢谢 也感谢我们的翻译人员和克莱姆森CCIT提供的 我们的比赛基础设施。最后，我们心存感激 感谢USACO赞助商的慷慨支持： Citadel、Ansatz、X-Camp、TwoSigma、VPlanet 编码、EasyFunCoding、 Orijtech 和 Jump Trading。

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

祝您编码愉快！

Farmer John is growing N (1≤N≤2⋅10⁵) plants of asparagus on his farm! However some of his plants have genetic differences, so some plants will grow faster than others. The initial height of the ith plant is h_i inches, and after each day, the ith plant grows by a_i inches.

FJ likes some of his plants more than others, and he wants some specific plants to be taller than others. He gives you an array of distinct values t₁,…,t_N containing all integers from 0 to N−1 and he wants the ith plant to have exactly t_i other plants that are taller than it. Find the minimum number of days so that FJ's request is satisfied, or determine that it is impossible.

INPUT FORMAT (pipe stdin):

The first will consist of an integer T, denoting the number of independent test cases (1≤T≤10).

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

The second line consists of N integers hi (1≤h_i ≤109) denoting the initial height of the ith plant in inches.

The third line consists of N integers a_i (1≤a_i≤109) denoting the number of inches the ith plant grows each day.

The fourth line consists of N distinct integers t_i denoting the array that FJ gives you.

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

OUTPUT FORMAT (pipe stdout):

Output T lines, the answer to each test case on a different line. If it is not possible, output −1.

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:

6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0

SAMPLE OUTPUT:

0
3
2
5
-1
-1

In the first sample input, there are 6 test cases.

In the first test case, there is only one plant, so the condition is satisfied on day 0.

In the second test case, we need the first plant to be shorter than the second plant. After day 1, the heights are 15 and 13. After day 2, the heights are both 23. After day 3, the heights are 31 and 33, and that's the first day in which the condition is satisfied.

The third and fourth test cases are similar to the second.

In the fifth test case, both plants start with an initial height of 7 and a growth rate of 8. So they will always have identical heights, and therefore the condition is never satisfied.

In the sixth test case, the condition is not satisfied initially and the growth rates are the same. So the condition can never be satisfied.

SAMPLE INPUT:

2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0

SAMPLE OUTPUT:

4
7
In the second sample input, there are 2 test cases.

In the first test case, the final heights after day 4 are 19, 20, 21, 18, 16.

In the second test case, the final heights after day 7 are 25, 17, 19, 35, 36.

SCORING:

Input 3: N≤2
Inputs 4-5: N≤50 and ai,hi≤103
Inputs 6-8: N≤103
Inputs 9-13: No additional constraints.
Problem credits: Chongtian Ma

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John has N cows in a line (1≤N≤3⋅10⁵). Unfortunately, there is a sickness spreading throughout.

Initially, some cows start off infected. Every night, an infected cow spreads the sickness to the cows on their left and right (if they exist). Once a cow is infected, she stays infected.

After some amount of nights, Farmer John realizes that the issue has gotten out of control, so he tests his cows to determine who has the sickness. Find the minimum number of cows that could have started with the sickness.

INPUT FORMAT (pipe stdin):

The first line contains N, the number of cows that Farmer John has.
The next line contains an N character bitstring of only 1s and 0s where a 1 represents an infected cow and a 0 represents an uninfected cow after some number of nights.

OUTPUT FORMAT (pipe stdout):

Output a single integer: the minimum number of cows that could have started with the sickness.

SAMPLE INPUT:

5
11111

SAMPLE OUTPUT:

1
Suppose the middle cow was the only cow to start off infected. Then the cows would be infected in the following order:

After two or more nights, the final state of the cows would look like the input. There are many other initial states and number of nights that could have produced the input state, such as:

All of these initial states contain at least one infected cow.

SAMPLE INPUT:

6
011101

SAMPLE OUTPUT:

4
The only initial state and number of nights that could have led to this final state is if no nights have passed and each of the four infected cows in the input started off with the sickness.

SCORING:

Inputs 3-7: N≤1000
Inputs 8-12: No additional constraints.
Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John's cows have quite the sweet tooth, and they especially enjoy eating candy canes! FJ has N total cows, each with a certain initial height and he wants to feed them M candy canes, each also of varying height (1≤N,M≤2⋅10⁵).

FJ plans to feed the candy canes one by one to the cows, in the order they are given in the input. To feed a candy cane to his cows, he will hang the candy cane so that initially the candy cane is just touching the ground. The cows will then line up one by one, in the order given by the input, and go up to the candy cane, each eating up to their height (since they cannot reach any higher). The candy cane stays suspended in place where it is initially set up and is not lowered to the ground, even after cows eat the bottom of the candy cane. It is possible a cow may eat nothing during her turn, if the base of the candy cane is already above that cow's height. After every cow has had their turn, the cows grow in height by how many units of candy cane they ate, and Farmer John hangs the next candy cane and the cows repeat the process again (with cow 1 again being the first to start eating the next candy cane).

INPUT FORMAT (pipe stdin):

The first line contains N and M.

The next line contains the initial heights of the N cows, each in the range [1,109].

The next line contains the heights of the M candy canes, each in the range [1,109].

OUTPUT FORMAT (pipe stdout):

The final heights of each of the N cows on separate lines.

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:

3 2
3 2 5
6 1

SAMPLE OUTPUT:
7
2
7

The first candy cane is 6 units tall.

The first cow eats the portion of the first candy cane up to height 3, after which the remaining portion of the first candy cane occupies heights [3,6].
The second cow is not tall enough to eat any of the remaining portion of the first candy cane.
The third cow eats two additional units of the first candy cane. The remaining portion of the first candy cane, occupying heights [5,6], is not eaten.
Next, each cow grows by the amount she ate, so the heights of the cows become [3+3,2+0,5+2]=[6,2,7].

The second candy cane is 1 unit tall, and the first cow eats all of it.

SCORING:

Inputs 2-10: N,M≤10³
Inputs 11-14: No additional constraints.
Problem credits: Agastya Goel

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of T (1≤T≤10⁵) targets located at distinct positions. Bessie starts at position 0 and follows a string of C (1≤C≤10⁵) commands, each one of L, F, or R:

L: Bessie moves one unit to the left.
R: Bessie moves one unit to the right.
F: Bessie fires. If there is a target at Bessie's current position, it is hit and destroyed, and cannot be hit again.

If you are allowed to change up to one command in the string to a different command before Bessie starts following it, what is the maximum number of targets that Bessie can hit?

INPUT FORMAT (pipe stdin):

The first line contains T and C.

The next line contains the locations of the T targets, distinct integers in the range [−C,C].

The next line contains the command string of length C, containing only the characters F, L, and R.

OUTPUT FORMAT (pipe stdout):

Print the maximum number of targets that Bessie can hit after changing up to one command in the string.

SAMPLE INPUT:

3 7
0 -1 1
LFFRFRR

SAMPLE OUTPUT:

3

If you make no changes to the string, Bessie will hit two targets:

If you change the last command from R to F, Bessie will hit all three targets:

SAMPLE INPUT:

1 5
0
FFFFF

SAMPLE OUTPUT:

1

If the commands are left unchanged, the only target at 0 will be destroyed. Since a target cannot be destroyed multiple times, the answer is 1.

SAMPLE INPUT:

5 6
1 2 3 4 5
FFRFRF

SAMPLE OUTPUT:
3

SCORING:

Inputs 4-6: T,C≤1000
Inputs 7-15: No additional constraints.
Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划