分类： 赛事资讯

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

共有 7890 名参与者提交了至少一个解决方案，来自 100+ 个不同的国家。其中，3693 人来自 美国，中国、加拿大、韩国、罗马尼亚、马来西亚、印度和新加坡也有很高的代表。

总共有 19289 份分级提交，按语言细分如下：

10346 C++17
3183 C++11
2949 Python-3.6.9
2687 Java
92 C
32 Python-2.7.17

以下是白金、黄金、白银和铜牌比赛的详细结果。 您还可以找到每个问题的解决方案和测试数据，然后单击任何问题您可以在“分析模式”中练习重新提交解决方案。

USACO 2024 年 2 月比赛，白金奖

白金组共有520名参与者，其中385名是大学预科生。得分最高的球员的结果在这里。恭喜所有顶尖参赛者取得优异成绩！

1 Lazy Cow
查看问题 | 测试数据 | 解决方案
2 Minimum Sum of Maximums
查看问题 | 测试数据 | 解决方案
3 Infinite Adventure
查看问题 | 测试数据 | 解决方案

USACO 2024 年 2 月比赛，金奖

金牌组共有934名参与者，其中682名是大学预科生。所有在本次比赛中获得 800 分或更高分的参赛者将自动晋升为白金组。所有晋升者的详细结果都在这里。

1 Bessla Motors
查看问题 | 测试数据 | 解决方案
2 Milk Exchange
查看问题 | 测试数据 | 解决方案
3 Quantum Moochanics
查看问题 | 测试数据 | 解决方案

USACO 2024 年 2 月比赛，银奖

白银组共有4139名参与者，其中3207名是大学预科生。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为黄金组。

1 Target Practice II
查看问题 | 测试数据 | 解决方案
2 Test Tubes
查看问题 | 测试数据 | 解决方案
3 Moorbles
查看问题 | 测试数据 | 解决方案

USACO 2024 年 2 月比赛，铜牌

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

1 Palindrome Game
查看问题 | 测试数据 | 解决方案
2 Milk Exchange
查看问题 | 测试数据 | 解决方案
3 Maximizing Productivity
查看问题 | 测试数据 | 解决方案

结语

在经历了一月份比赛中的挑战之后，从运营的角度来看，很高兴看到比赛进行得更顺利 观点，部分原因是我们的比赛基础设施最近和正在进行的改进。随着 2023-2024 赛季接近尾声， 我们继续看到所有赛区的强劲表现和大量晋升。

对于那些尚未晋升的人，请记住，你练习得越多，你的算法编码技能就会变得越好——请坚持下去！USACO比赛旨在挑战甚至最好的学生，要想取得优异成绩，可能需要付出很多努力才能超越他们（从结果来看，白金级问题阵容在这个比赛看起来特别具有挑战性！）。为帮助您修复任何代码中的错误，您现在可以重新提交解决方案，并使用“分析模式”从判断服务器获得反馈。

许多人为USACO比赛的质量和成功做出了贡献。为本次比赛提供帮助的人包括 Brandon Wang, Claire Zhang, Benjamin Qi, Alexander Wei, Chongtian Ma, Alex Liang, Patrick Deng, Aryansh Shrivastava, Suhas Nagar, Nick Wu, Alex Fan, Anand John, Andi Qu, Richard Qi, Danny Mittal, Benjamin Chen, Jichao Qian和 Nathan Wang。也感谢我们的翻译人员和克莱姆森CCIT提供我们的比赛基础设施。最后，我们心存感激 感谢USACO赞助商的慷慨支持： Citadel、Ansatz、X-Camp、TwoSigma、VPlanet Coding、EasyFunCoding、 Orijtech 和 Jump Trading。

我们期待在 2024 年美国公开赛上再次见到大家 比赛，我们本赛季的最后一场比赛。

祝您编码愉快！

Farmer John has N (1≤N≤2⋅10⁵ ) farms, numbered from 1 to N. It is known that FJ closes farm i at time c_i. Bessie wakes up at time S, and wants to maximize the productivity of her day by visiting as many farms as possible before they close. She plans to visit farm i on time t_i+S. Bessie must arrive at a farm strictly before Farmer John closes it to actually visit it.

Bessie has Q (1≤Q≤2⋅10⁵) queries. For each query, she gives you two integers S
and V. For each query, output whether Bessie can visit at least V farms if she wakes up at time S.

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

The first line consists of N and Q.

The second line consists of c₁,c₂,c₃…c_N(1≤c_i≤10⁶).

The third line consists of t₁,t₂,t₃…t_N (1≤t_i≤10⁶).

The next Q lines each consist of two integers V (1≤V≤N) and S (1≤S≤10⁶).

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

For each of the Q queries, output YES or NO on a new line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

YES
NO
YES
YES
NO

For the first query, Bessie will visit the farms at time t=[9,7,8,8,13], so she will only get to visit farm 4 on time before FJ closes the farm.

For the second query, Bessie will not be able to visit any of the farms on time.

For the third query, Bessie will visit farms 3,4,5 on time.

For the fourth and fifth queries, Bessie will be able to visit all but the first farm on time.

SCORING:

Inputs 2-4: N,Q≤10³
Inputs 5-9: c_i,t_i≤20
Inputs 10-17: No additional constraints.

Problem credits: Chongtian Ma

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

咨询一对一备赛规划

Farmer John's N (1≤N≤2⋅10⁵) cows are lined up in a circle such that for each i
in 1,2,…,N−1, the cow to the right of cow i is cow i+1, and the cow to the right of cow N is cow 1. The ith cow has a bucket with integer capacity a_i (1≤a_i ≤10⁹)
liters. All buckets are initially full.

Every minute, the cows exchange milk according to a string s₁s₂…s_N consisting solely of the characters ‘L’ and ‘R’. if the ith cow has at least 1 liter of milk, she will pass 1 liter of milk to the cow to her left if si=‘L’, or to the right if si=‘R’. All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away a liter of milk but also receives a liter, her milk is preserved). If a cow's total milk ever ends up exceeding a_i , then the excess milk will be lost.

FJ wants to know: after M minutes (1≤M≤10⁹), what is the total amount of milk left among all cows?

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

The first line contains N and M.

The second line contains a string s₁s₂…s_N consisting solely of the characters ‘L’
or ‘R’, denoting the direction each cow will pass their milk in.

The third line contains integers a₁,a₂,…,a_N, the capacities of each bucket.

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

Output an integer, the sum of milk among all cows after M minutes.

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 1
RRL
1 1 1

SAMPLE OUTPUT:

2

Cows 2 and 3 pass each other one liter of milk, so their milk is preserved. When cow 1 passes their milk to cow 2, cow 2's bucket overflows, and one liter of milk is lost after one minute.

SAMPLE INPUT:

5 20
LLLLL
3 3 2 3 3

SAMPLE OUTPUT:

14

Each cow is passing a liter of milk to the cow on the left and gaining a liter of milk from the cow on the right, so all of the milk is preserved regardless of how much time passes.

SAMPLE INPUT:

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

SAMPLE OUTPUT:

38

Initially, there are a total of 51 liters of milk. After 5 minutes, cows 3, 6, and 7
will lose 5, 3, and 5 liters of milk respectively. Therefore, a total of 38 liters of milk remain.

SCORING:

Inputs 4-8: N,M≤1000
Inputs 9-16: No additional constraints.

Problem credits: Chongtian Ma, Alex Liang

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

咨询一对一备赛规划

Bessie and Elsie are playing a game with a pile of stones that initially contains S
stones The two cows alternate turns, with Bessie going first. When it is a cow's turn, she must remove x stones from the pile, where x is any positive integer palindrome of the cow's choosing. If the pile is empty when a cow's turn starts, that cow loses.

Definition: A positive integer is a palindrome if it reads the same forward and backward; examples of palindromes include 1, 121, and 9009. Leading zeros are not allowed; e.g., 990 is *not* a palindrome.

There are T (1≤T≤10) independent test cases. For each test case, print who wins the game if both cows play optimally.

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

The first line contains T, the number of test cases. The next T lines describe the test cases, one line per test case.

Each test case is specified by a single integer S.

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

For each test case, output B if Bessie wins the game under optimal play starting with a pile of stones of size S, or E otherwise, on a new line.

SAMPLE INPUT:

3
8
10
12

SAMPLE OUTPUT:

B
E
B

For the first test case, Bessie can remove all the stones on her first move, since 8
is a palindrome, guaranteeing her win.

For the second test case, 10 is not a palindrome, so Bessie cannot remove all the stones on her first move. Regardless of how many stones Bessie removes on her first move, Elsie can always remove all remaining stones on her second move, guaranteeing her win.

For the third test case, it can be proven that Bessie wins under optimal play.

SCORING:

Inputs 2-4: S<100
Inputs 5-7: S<10⁶
Inputs 8-10: S< 10⁹
Inputs 11-13: No additional constraints.

Problem credits: Nick Wu

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

咨询一对一备赛规划

Bessie and Elsie are playing a game of Moorbles. The game works as follows: Bessie and Elsie each start out with some amount of marbles. Bessie holds out A of her marbles in her hoof and Elsie guesses if A is Even or Odd. If Elsie is correct, she wins the A marbles from Bessie and if she guesses incorrectly, she loses A
of her marbles to Bessie (if Elsie has less than A marbles, she loses all her marbles). A player loses when they lose all of their marbles.

After some amount of turns in the game, Elsie has N (1≤N≤10⁹) marbles. She thinks it is hard to win, but she is playing to not lose. After being around Bessie enough, Elsie has a good read on Bessie's habits and recognizes that on turn i, there are only K (1≤K≤4) different amounts of marbles that Bessie may put out. There are only M (1≤M≤3⋅10⁵) turns before Bessie gets bored and stops playing. Can you identify a lexicographically minimum turn sequence such that Elsie will not lose, regardless of how Bessie plays?

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

The first line contains a single integer T(1≤T≤10) representing the number of test cases. Each test case is described as follows:

First, one line containing three integers N, M, and K, representing the number of marbles Elsie has, the number of turns, and the number of potential moves Bessie can make respectively.

Then, M lines where line i contains K distinct space separated integers a_i,1a_i,2…a_i,K
(1≤a_i,j≤10³) representing the possible amounts of marbles that Bessie might play on turn i.

It is guaranteed that the sum of M over all test cases is at most 3⋅10⁵.

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

For each test case, output the lexicographically minimum move sequence for Elsie to guarantee not losing, or −1 if she will lose. The move sequence should be on a single line and consist of M space-separated tokens each equal to either "Even" or "Odd".

Note: "Even" is lexicographically smaller than "Odd".

SAMPLE INPUT:

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

SAMPLE OUTPUT:

Even Even Odd
-1

In the first case, the only lexicographically smaller sequence of moves is "Even Even Even", but Bessie can make Elsie lose in that case by first playing 5, which reduces Elsie's number of marbles from 10 to 5, then playing 3, which reduces Elsie's number of marbles from 5 to 2, then playing 3, which wipes out all of her marbles.

If Elsie instead plays the correct move sequence "Even Even Odd", then if Bessie plays the same way, at the end when she plays 3, Elsie will gain those 3 marbles, increasing her number of marbles to 5. It can further be shown that Bessie cannot play in a different way to take all of Elsie's marbles given that Elsie plays "Even Even Odd".

In the second case, it can be shown that for any move sequence that Elsie could choose, Bessie can play in a way to take all of Elsie's marbles.

SAMPLE INPUT:

1
20 8 2
3 5
3 5
3 5
3 5
3 5
3 5
3 5
3 5

SAMPLE OUTPUT:

Even Even Even Odd Even Odd Even Odd

SCORING:

Input 3: M≤16.
Inputs 4-6: M≤1000.
Inputs 7-12: No further constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Bessie has recently gotten into chemistry. At the moment, she has two different colors 1 and 2 of various liquids that don't mix well with one another. She has two test tubes of infinite capacity filled with N (1≤N≤10⁵ ) units each of some mixture of liquids of these two colors. Because the liquids don’t mix, once they settled, they divided into layers of separate colors. Because of this, the two tubes can be viewed as strings f₁f₂…f_N and s₁s₂…s_N where f_i represents the color of the liquid that is i units from the bottom of the first tube, and s_i represents the color of the liquid that is i units from the bottom of the second tube. It is guaranteed that there is at least one unit of each color of liquid.

Bessie wants to separate these liquids so that each test tube contains all units of one color of liquid. She has a third empty beaker of infinite capacity to help her in this task. When Bessie makes a "pour", she moves all liquid of color i
at the top of one test tube or beaker into another.

Determine the minimum number of pours to separate all the liquid into the two test tubes, and the series of moves needed to do so. It does not matter which test tube ends up with which color, but the beaker must be empty..

There will be T (1≤T≤10) test cases, with a parameter P for each test case.

Suppose the minimum number of pours to separate the liquids into the original tubes is M.

If P=1, you will receive credit if you print only M.
If P=2, you will receive credit if you print an integer A such that M≤A≤M+5, followed by A lines that construct a solution with that number of moves. Each line should contain the source and the destination tube (1, 2, or 3for the beaker). The source tube must be nonempty before the move and a tube may not be poured into itself.
If P=3, you will receive credit if you print M, followed by a valid construction using that number of moves.

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

The first line contains T, the. number of test cases. For each test case, the next line contains N and P representing the amount each test tube is initially filled to, and the query type. The following line contains f₁f₂f₃…f_N representing the first test tube. f_i∈{1,2} and f₁ represents the bottom of the test tube. The subsequent line contains s₁,s₂,…,s_N representing the second test tube.s_i∈{1,2} and s₁ represents the bottom of the test tube.

It is guaranteed that there will be at least one 1 and one 2 across both input strings.

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

For each test case, you will print a single number representing the minimum pours to separate the liquid in the test tubes. Depending on the query type, you may also need to provide a valid construction.

SAMPLE INPUT:

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

SAMPLE OUTPUT:

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

In the first three test cases, the minimum number of pours to separate the tubes is 4. We can see how the following moves separate the test tubes:

Initial state:

1: 1221
2: 2211
3:

After the move "1 2":

1: 122
2: 22111
3:

After the move "1 3":

1: 1
2: 22111
3: 22
After the move "2 1":
1: 1111
2: 22
3: 22

After the move "3 2":

1: 1111
2: 2222
3:

In the last test case, the minimum amount of pours is 5. However, since P=2, the given construction with 6 moves is valid since it is within 5 pours from the optimal answer.

SCORING:

Inputs 2-6: P=1
Inputs 7-11: P=2
Inputs 12-21: No additional constraints.

Additionally, it is guaranteed that T=10 for all inputs besides the sample.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Note: The time limit for this problem is 2.5s, 1.25 times the default.

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++).

The Paris Moolympics are coming up and Farmer John is training his team of cows in archery! He has set up the following exercise on the 2D coordinate plane.

There are N(1≤N≤4⋅10⁴) axis-aligned rectangular targets and 4N cows. Every cow must be assigned to a different target vertex. At moment i, for 1≤i≤N:

1.Target i appears.
2.The 4 cows assigned to its vertices shoot at them.
3.If a cow's shot passes through the interior of the target before it hits the assigned vertex or misses, the cows fail the exercise.
4.The target disappears to make space for the next one.

Each cow is located on the y-axis (x=0), and each target is a rectangle where target i has its lower left coordinate at and its upper right coordinate at The coordinates also satisfy (Note: X₁ is the same for every target).

In addition, each cow has a "focus" angle they are working on. Therefore, they will turn at a specific angle when shooting. Given that their shot travels in a straight line from their position towards their assigned vertex, the trajectory of cow i's arrow can be described by s_i (0<|s_i |<10⁹), the slope of the trajectory.

So that he can carefully examine the cows' technique, Farmer John wants to minimize the distance between the furthest cows. If Farmer John were to optimally assign each cow to a target vertex and place them on the y-axis, can you help him determine what the minimum distance between the furthest cows would be or if the cows will always fail the exercise?

Each input contains T (1≤T≤10) independent test cases. The sum of N across all test cases is guaranteed to not exceed 4⋅10⁴.

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

The first line contains T(1≤T≤10), the number of independent test cases. Each test case is described as follows:The first line of each test case contains two integers, N and X₁, the number of targets and the left-most x-coordinate of the targets respectively.

This is followed by N lines with the i-th line consisting of three integers,and , the lower y-coordinate, the upper y-coordinate, and the right x-coordinate of the i-th target respectively.

The last line consists of 4N integers,s₁,s₂,…,s_4N where s_i denotes the slope of cow i's shot trajectory.

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

The minimum possible distance between the furthest cows or −1 if the cows will always fail the exercise.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

17
-1
11

One optimal assignment for test case 1 is the following target vertices for cows 1-8 respectively:
(6,1),(6,3),(3,4),(3,6),(1,4),(1,3),(1,6),(1,1)

This gives the following y locations for cows 1-8 respectively:
−5,9,−2,12,1,6,2,5

This gives a minimum distance of 12−(−5)=17.

One reason the second test case is impossible is because it is impossible to shoot the vertex at (6,3)(the top right vertex of target 1) without the shot passing through the interior of target 1.

SCORING:

Input 2: |s_i|is the same for all 1≤i≤4N.
Input 3-9: The sum of N across all testcases is at most 1000.
Inputs 10-15: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

In her free time, Bessie likes to dabble in experimental physics. She has recently discovered a pair of new subatomic particles, named mootrinos and antimootrinos. Like standard matter-antimatter pairs, mootrinos and antimootrinos annihilate each other and disappear when they meet. But what makes these particles unique is that they switch their direction of motion (while maintaining the same speed) whenever Bessie looks at them.

For her latest experiment, Bessie has placed an even number N (2≤N≤2⋅10⁵) of these particles in a line. The line starts with a mootrino on the left and then alternates between the two types of particles, with the i-th particle located at position p_i (0≤p₁<⋯<p_N≤10¹⁸). Mootrinos initially move right while antimootrinos initially move left, and the i-th particle moves with a constant speed of s_i units per second (1≤s_i≤10⁹).

Bessie makes observations at the following times:

First, 1 second after the start of the experiment.
Then 2 seconds after the first observation.
Then 3 seconds after the second observation.
...
Then n+1 seconds after the n-th observation.

During each observation, Bessie notes down which particles have disappeared.

This experiment may take an extremely long time to complete, so Bessie would like to first simulate its results. Given the experiment setup, help Bessie determine when (i.e., the observation number) she will observe each particle disappear! It may be shown that all particles will eventually disappear.

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

Each input contains T(1≤T≤10) independent test cases.Each test case consists of three lines. The first line contains N, the second line contains p_1,…, p_N, and the third line contains s₁…,s_N.

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

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

For each test case, output the observation number for each particle's disappearance, separated by spaces.

SAMPLE INPUT:

4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5

SAMPLE OUTPUT:

9 9
11 11
1 1
3 3

For the first test, Bessie observes the following during the first 8
observations:

The mootrino (initially moving right) appears at positions 2→0→3→−1→4→−2→5→−3.
The antimootrino (initially moving left) appears at positions 10→12→9→13→8→14→7→15.

Then right at observation 9, the two particles meet at position 6 and annihilate each other.

For the second test, the antimootrino starts 1 additional unit to the right, so the two particles meet at position 6.5 half a second before observation 11.

Note that we only care about observation numbers, not times or positions.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1 1 3 3
7 2 2 7

For the first test:

The two leftmost particles meet at position 2 right at observation 1.
The two rightmost particles meet at position 6.5 half a second before observation 3.

SCORING:

Input 3 satisfies N=2.
Input 4 satisfies N≤2000 and p_i≤10⁴ for all cows.
Inputs 5-7 satisfy N≤2000.
Inputs 8-12 satisfy no additional constraints.

Problem credits: Aryansh Shrivastava, Benjamin Qi

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

咨询一对一备赛规划

Farmer John's N(1≤N≤5⋅10⁵)cows are lined up in a circle. The ith cow has a bucket with integer capacity a_i (1≤a_i≤10⁹) liters. All buckets are initially full.

Every minute, cow i will pass all the milk in their bucket to cow i+1 for 1≤i<N, with cow N passing its milk to cow 1. All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away x liters of milk and also receives x
liters, her milk is preserved). If a cow's total milk ever ends up exceeding ai, then the excess milk will be lost.

After each of 1,2,…,N minutes, how much total milk is left among all cows?

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

The first line contains N.

The next line contains integers a₁,a₂,…,a_N

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

Output N lines, where the i-th line is the total milk left among all cows after i
minutes.

SAMPLE INPUT:

6
2 2 2 1 2 1

SAMPLE OUTPUT:

8
7
6
6
6
6

Initially, the amount of milk in each bucket is [2,2,2,1,2,1].

After 1 minute, the amount of milk in each bucket is [1,2,2,1,1,1] so the total amount of milk is 8.

After 2 minutes, the amount of milk in each bucket is [1,1,2,1,1,1] so the total amount of milk is 7.

After 3 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.

After 4 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.

After 5 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.

After 6 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.

SAMPLE INPUT:

8
3 8 6 4 8 3 8 1

SAMPLE OUTPUT:

25
20
17
14
12
10
8
8

After 1 minute, the amount of milk in each bucket is [1,3,6,4,4,3,3,1] so the total amount of milk is 25.

SAMPLE INPUT:

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

SAMPLE OUTPUT:

2000000053
1000000054
56
49
42
35
28
24
20
20

SCORING:

Inputs 4-5: N≤2000
Inputs 6-8: a_i ≤2
Inputs 9-13: All a_i are generated uniformly at random in the range [1,109].
Inputs 14-23: No additional constraints.

Problem credits: Chongtian Ma, Alex Liang, Patrick Deng

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

咨询一对一备赛规划

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

Farmer John would like to promote his line of Bessla electric tractors by showcasing Bessla's network of charging stations. He has identified N
(2≤N≤5⋅10⁴) points of interest labeled 1…N, of which the first C
(1≤C<N) are charging stations and the remainder are travel destinations. These points of interest are interconnected by M (1≤M≤10⁵) bidirectional roads, the i-th of which connects distinct points u_i and v_i (1≤u_i,v_i≤N) and has length ℓ_i miles (1≤ℓ_i ≤10⁹).

A Bessla can travel up to 2R miles (1≤R≤10⁹) on a single charge, allowing it to reach any destination within R miles of a charging station. A destination is deemed well-connected if it is reachable from at least K(1≤K≤10) distinct charging stations. Your task is to assist Farmer John in identifying the set of well-connected travel destinations.

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

The first line contains five space-separated integers N, M, C, R, and K. Each of the following M lines contains three space-separated integers u_i, v_i, and ℓ_i such that u_i≠v_i.

The charging stations are labeled 1,2,…,C. The remaining points of interest are all travel destinations.

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

First, output the number of well-connected travel destinations on a single line. Then, list all well-connected travel destinations in ascending order, each on a separate line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1
2

We have one charging station at 1. From this charging station, we can reach point 2(since it is distance 3 away from 1), but not point 3 (since it is distance 5 away from 1). Thus, only point 2 is well-connected.

SAMPLE INPUT:

4 3 2 101 2
1 2 1
2 3 100
1 4 10

SAMPLE OUTPUT:

2
3
4

We have charging stations at 1 and 2, and both points 3 and 4 are within distance 101 of both 1 and 2. Thus, both points 3 and 4 are well-connected.

SAMPLE INPUT:

4 3 2 100 2
1 2 1
2 3 100
1 4 10

SAMPLE OUTPUT:

1
4

SCORING:

Inputs 4 and 5: K=2 and N≤500 and M≤1000.
Inputs 6 and 7: K=2.
Inputs 8-15: No additional constraints.

Problem credits: Alexander Wei

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

咨询一对一备赛规划