作者： chenchen

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

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

4725 USA 3375 CHN 354 CAN 261 KOR 131 ROU 108 IND 78 MYS
77 SGP 64 HKG 57 TWN 46 DEU 44 GBR 44 AUS 40 SYR
34 TUR 33 POL 32 ISR 30 AZE 26 GEO 26 EGY 26 BLR
23 VNM 21 JPN 20 BRA 17 KAZ 17 ABW 16 IRN 15 SLV
15 FRA 15 COL 15 ARM 14 BOL 13 IDN 12 SAU 12 CUB
11 UZB 10 THA 10 NZL 10 MEX 10 ESP 10 BGD 9 PAK
8 ZAF 8 RUS 8 ARG 7 SWE 7 NLD 5 UKR 5 EST
5 CHL 5 AUT 5 ATG 5 AFG 4 SRB 4 MKD 4 KGZ
4 GRC 4 BEL 4 ARE 4 AND 3 ZWE 3 UMI 3 TUN
3 PHL 3 ANT 3 ALB 3 ALA 3 AGO 2 VIR 2 TKM
2 PRK 2 NPL 2 NER 2 MNG 2 MLT 2 MAC 2 LTU
2 ITA 2 IRL 2 HRV 2 GHA 2 FIN 2 CMR 2 CHE
2 BWA 2 ASM 1 YEM 1 VGB 1 VAT 1 TZA 1 TKL
1 TJK 1 SEN 1 QAT 1 PSE 1 PER 1 NOR 1 MMR
1 MDA 1 MCO 1 MAR 1 LAO 1 KHM 1 KEN 1 JEY
1 IMN 1 HUN 1 HTI 1 GIB 1 FSM 1 DNK 1 CZE
1 CYP 1 CXR 1 CRI 1 CCK 1 CAF 1 BTN 1 BRN
1 BLZ 1 BIH 1 BHR 1 BGR 1 BDI 1 ATF

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

13779 C++17
4504 C++11
4018 Python-3.6.9
3975 Java
117 C
21 Python-2.7.17

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

USACO 2024 年 1 月比赛，白金奖

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

1 Island Vacation
查看问题 | 测试数据 | 解决方案
2 Merging Cells
查看问题 | 测试数据 | 解决方案
3 Mooball Teams III
查看问题 | 测试数据 | 解决方案

USACO 2024 年 1 月比赛，金牌

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

1 Walking in Manhattan
查看问题 | 测试数据 | 解决方案
2 Cowmpetency
查看问题 | 测试数据 | 解决方案
3 Nap Sort
查看问题 | 测试数据 | 解决方案

USACO 2024 年 1 月比赛，银奖

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

1 Cowmpetency
查看问题 | 测试数据 | 解决方案
2 Potion Farming
查看问题 | 测试数据 | 解决方案
3 Cowlendar
查看问题 | 测试数据 | 解决方案

USACO 2024 年 1 月比赛，铜牌

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

1 Majority Opinion
查看问题 | 测试数据 | 解决方案
2 Cannonball
查看问题 | 测试数据 | 解决方案
3 Balancing Bacteria
查看问题 | 测试数据 | 解决方案

结语

从科学的角度来看，2024 年 1 月的比赛进行得很顺利， 所有级别都有强大的问题阵容，并且有相当数量的学生得到提升。不幸的是，我们在比赛期间经历了两次大规模的拒绝服务攻击，这干扰了大量参赛者的比赛运作。因此，我们正在努力迁移到更强大的新托管平台，该平台具有更强大的对策来应对这种情况。对于那些受到这些中断影响的人，我们理解并分享你们的沮丧。 不幸的是，对于超出我们控制范围的中断，我们的一般政策不允许我们为受影响的人提供额外的时间，这是出于维护我们比赛的完整性的需要，这确实是美国IOI和EGOI团队的选拔机制。对于美国大学预科白金选手:由于认证白金窗口不受影响，本次比赛的分数将被计算在内，在决赛选择期间，我们的教练将确保不会对本次比赛中可能受到中断影响的非认证白金分数进行处罚。例如，在本次比赛中，3个认证分数加上一个可能受到损害的非认证分数将得到充分考虑。

对于那些尚未晋升的人，请记住，你得到的练习越多，你的算法编码技能就会越好——请坚持下去!USACO的竞赛旨在挑战最优秀的学生，要想在竞赛中脱颖而出，可能需要付出大量的努力。

许多人为USACO比赛的质量和成功做出了贡献。参与本次比赛的有Benjamin Qi、Dhruv Rohatgi、Nick Wu、Suhas Nagar、Rohin Garg、Brandon Wang、Rain Jiang、Danny Mittal、Timothy Qian Anand John、Ben Chen、Andi Qu、Bing-Dong Liu、Richard Qi、Andrew Gu、Claire Zhang、Nathan Wang和Spencer Compton。也感谢我们的翻译和克莱姆森CCIT提供我们的比赛基础设施。最后，我们感谢USACO赞助商的慷慨支持:Citadel、Ansatz、X-Camp、TwoSigma、VPlanet Coding、EasyFunCoding、Orijtech和Jump Trading。

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

祝您编码愉快！

Farmer John has N (1≤N≤2⋅10⁵) patches of grass in a line, where patch i
has a level of bacteria that differs by ai from that of healthy grass (−10¹⁵≤a_i≤10¹⁵). For example, if a_i=−3, then patch i has a level of bacteria 3 lower than normal, and would need exactly 3 additional units of bacteria added to raise it to the point where it is considered healthy.

Farmer John wants to ensure every patch of grass is corrected to have a healthy level of bacteria. Conveniently, he owns two brands of pesticide that he can spray on his field, one that adds bacteria and one that removes bacteria. When Farmer John sprays either type of pesticide, he stands in patch N (the rightmost patch) and selects a power level L for his sprayer (1≤L≤N).

The sprayer has the most impact on patches near Farmer John, with diminishing effect farther away. If Farmer John chooses the pesticide that adds bacteria, then L units of bacteria will be added to patch N, L−1 units to patch N−1, L−2 units to patch N−2, and so on. Patches 1…N−L will receive no bacteria, since the sprayer isn't set to a level powerful enough to reach them. Similarly, if Farmer John chooses the pesticide that removes bacteria, then L units of bacteria will be removed from patch N, L−1 units will be removed from patch N−1, and so on. Again, patches 1…N−L will be unaffected.

Find the minimum number of times Farmer John has to apply his sprayer such that every patch of grass has the recommended value of bacteria for healthy grass. It is guaranteed that the answer is at most 10⁹.

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

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

The first line contains N .

The second line contains N integers a₁,a₂,…,a_N , the initial bacteria levels of each patch of grass.

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

The minimum number of applications necessary to make every patch of grass have the recommended value of bacteria for healthy grass.

SAMPLE INPUT:
2
-1 3

SAMPLE OUTPUT:

6

Use the type of pesticide that removes bacteria, at a power level of 1, five times. Then use the type of pesticide that adds bacteria, with a power level of 2, one time.

SAMPLE INPUT:

5
1 3 -2 -7 5

SAMPLE OUTPUT:

26

SCORING:

Inputs 3-5: N≤10³, the answer is at most 10³
Inputs 6-10: N≤10³
Inputs 11-15: No additional constraints.

Problem credits: Rohin Garg

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

咨询一对一备赛规划

Bessie has mastered the art of turning into a cannonball and bouncing along a number line of length N (1≤N≤10⁵) with locations numbered 1,2,…,N
from left to right. She starts at some integer location S (1≤S≤N) bouncing to the right with a starting power of 1. If Bessie has power k, her next bounce will be at a distance k forward from her current location.

Every integer location from 1 to N is either a target or a jump pad. Each target and jump pad has an integer value in the range 0 to N inclusive. A jump pad with a value of v increases Bessie's power by v and reverses her direction. A target with a value of v will be broken if landed on with a power of at least v. Landing on a target does not change Bessie's power or direction. A target that is broken will remain broken and Bessie can still bounce on it, also without changing power or direction.

If Bessie bounces for an infinite amount of time or until she leaves the number line, how many targets will she break?

If Bessie starts on a target that she can break, she will immediately do so. Similarly, if Bessie starts on a jump pad, the pad's effects will be applied before her first jump.

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

The first line of the input contains N and S, where N is the length of the number line and S is Bessie's starting location.

The next N lines describe each of the locations. The ith of these lines contains integers q_i and v_i , where q_i =0 if location i is a jump pad and q_i=1 if location i is a target, and where viis the value of location i .

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

Output one number representing the number of targets that will be broken.

SAMPLE INPUT:

5 2
0 1
1 1
1 2
0 1
1 1

SAMPLE OUTPUT:

1

Bessie starts at coordinate 2, which is a target of value 1, so she immediately breaks it. She then bounces to coordinate 3, which is a target of value 2, so she can't break it. She continues to coordinate 4, which switches her direction and increases her power by 1 to 2. She bounces back to coordinate 2, which is an already broken target, so she continues. At this point, she bounces to coordinate 0, so she stops. She breaks exactly one target at located at 2.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

3

The path Bessie takes is 4→5→3→1→6, where the next bounce would take her out of the number line (11). She breaks targets 4,3,6in that order.

SCORING:

Inputs 3-5: N≤100
Inputs 6-10: N≤1000
Inputs 11-20: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Farmer John has an important task - figuring out what type of hay to buy for his cows.

Farmer John's N cows (2≤N≤10⁵) are numbered 1 through N and each cow likes exactly one type of hay  h_i (1≤h_i≤N). He wants all his cows to like the same type of hay.

To make this happen, Farmer John can host focus groups. A focus group consists of getting all cows in a contiguous range numbered i to j, inclusive, together for a meeting. If there is a type of hay that more than half the cows in the group like, then after the focus group finishes meeting, all cows end up liking that type of hay. If no such type of hay exists, then no cows change the type of hay they like. For example, in focus group consisting of a range of 16 cows, 9 or more of them would need to have the same hay preference to cause the remaining cows to switch their preference to match.

Farmer John wants to know which types of hay can become liked by all cows simultaneously. He can only host one focus group at a time, but he can run as many focus groups as necessary to get all cows to like the same type of hay.

INPUT FORMAT (input arrives from the terminal / 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 N.

The second line consists of N integers, the favorite types of hay h_i  for the cows in order.

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

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

Output T lines, one line per test case.

If it possible to make all cows like the same type of hay simultaneously, output all possible such types of hay in increasing order. Otherwise, output −1. When printing a list of numbers on the same line, separate adjacent numbers with a space, and be sure the line does not end with any extraneous spaces.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

2
-1
1 2
3
-1

In the sample input, there are 5 test cases.

In the first test case, it is only possible to make all cows like type 2. FJ can do this by running a single focus group with all cows.

In the second test case, we can show that no cows will change which type of hay they like.

In the third test case, it is possible to make all cows like type 1 by running three focus groups - first by having cows 1 through 4 in a focus group, then by having cows 1 through 5 in a focus group, then by having cows 1 through 6 in a focus group. By similar logic, using cows 3 through 6, cows 2 through 6, then cows 1 through 6, we can make all cows like type 2.

In the fourth test case, it is possible to make all cows like type 3 by running a single focus group with all cows.

In the fifth test case, we can show that no cows will change which type of hay they like.

SCORING:

Input 2: N=2.
Inputs 3-4: N≤50.
Inputs 5-6: h_i≤h_i+1 for all 1≤i≤N−1.
Inputs 7-15: No additional constraints.

Problem credits: Nick Wu

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

咨询一对一备赛规划

Bessie has woken up on a strange planet. In this planet, there are N
(1≤N≤10⁴) months, with a₁,…,a_N days, respectively (1≤a_i≤4⋅10⁹, all a_i
are integers). In addition, on the planet, there are also weeks, where each week is L days, with L being a positive integer. Interestingly, Bessie knows the following:

For the correct L, each month is at least 4 weeks long.
For the correct L, there are at most 3 distinct values of a_i mod L.
Unfortunately, Bessie has forgotten what L is! Help her by printing the sum of all possible values of L.

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

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

The first line contains a single integer N. The second line contains N
space-separated integers, a₁,…,a_N.

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

A single integer, the sum of all possible values of L.

SAMPLE INPUT:

12
31 28 31 30 31 30 31 31 30 31 30 31

SAMPLE OUTPUT:

28

The possible values of L are 1, 2, 3, 4, 5, 6, and 7. For example, L=7 is valid because each month is at least length 4⋅7=28 days long, and each month is either 0, 2, or 3 mod 7.

SAMPLE INPUT:

4
31 35 28 29

SAMPLE OUTPUT:

23
The possible values of L are 1, 2, 3, 4, 6, and 7. For example, L=6 is valid because each month is at least length 4⋅6=24 days long, and each month is either 1, 4, or 5 mod 6.

SCORING:

Inputs 3-4: 1≤a_i≤10⁶
Inputs 5-14: No additional constraints

Problem credits: Brandon Wang

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

咨询一对一备赛规划

You are playing your favorite mobile game and you are trying to farm potions so that you may have a chance at defeating the legendary cow boss. The game map is a series of N (2≤N≤10⁵) rooms labeled 1…N connected by N−1 edges that form a tree.

You can explore the map by making a series of "traversals". A traversal is a simple path from room 1 to any other room in the tree. Once you finish one traversal, you can start another traversal from room 1. The map is complete once every one of its rooms is visited by at least one traversal. Your main goal is to complete the map in the minimum number of traversals.

Your secondary goal is to farm as many potions as possible. Before a traversal begins, a potion will spawn at some room in the map. You can pick up the potion by visiting the room that the potion spawned at in the current traversal. If you do not pick up the potion, then it will disappear once the current traversal ends, so you cannot pick it up in future traversals.

As you are a smart programmer, after looking at the game files, you were able to figure out where the potions will appear before your next N traversals. If you complete the map in the minimum number of traversals, what is the maximum amount of potions that you can farm from the map?

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

The first line of the input contains an integer N, denoting the number of rooms in the map.

Then follow N space-separated integers p₁p₂…p_N where 1≤p_i≤N, where p_i
is the room that a potion will appear at before the ith traversal.

Finally, N−1 lines follow with two space-separated integers ab (1≤a,b≤N) representing an edge between rooms a and b. It is guaranteed that these edges form a tree.

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

Output one line containing a single integer, the maximum amount of potions that you can farm from the map in the minimum number of traversals.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

2

In this case, the minimum number of traversals required to complete the map is 3.

One optimal plan that picks up two potions in three traversals is as follows:

Traversal 1: 1→3→5 (Pick up potion at 5)
Traversal 2: 1→3→4 (Pick up potion at 4)
Traversal 3: 1→2 (Forced to complete the map and ignore potion at 3)

Alternatively, we could have also planned our traversals as follows:

Traversal 1: 1→2 (no potions)
Traversal 2: 1→3→4 (Pick up potion at 4)
Traversal 3: 1→3→5 (Pick up potion at 3)

SCORING:

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

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

咨询一对一备赛规划

Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed N(2≤N≤10⁵) cows for the position. After interviewing the i
th candidate, he assigned the candidate an integer "cowmpetency" score c_i
ranging from 1 to C inclusive (1≤C≤10⁹) that is correlated with their leadership abilities.

Because he has interviewed so many cows, Farmer John does not remember all of their cowmpetency scores. However, he does remembers Q (1≤Q<N) pairs of numbers (a_j,h_j) where cow h_j was the first cow with a strictly greater cowmpetency score than cows 1 through a_j (so 1≤a_j<h_j≤N).

Farmer John now tells you the sequence c₁,…,c_N (where c_i=0 means that he has forgotten cow i's cowmpetency score) and the Q pairs of (a_j,h_j). Help him determine the lexicographically smallest sequence of cowmpetency scores consistent with this information, or that no such sequence exists! A sequence of scores is lexicographically smaller than another sequence of scores if it assigns a smaller score to the first cow at which the two sequences differ.

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

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

The first line contains T, the number of independent test cases. Each test case is described as follows:

First, a line containing N, Q, and C.
Next, a line containing the sequence c₁,…,c_N (0≤c_i≤C).
Finally, Q lines each containing a pair (a_j,h_j). It is guaranteed that all a_j within a test case are distinct.

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

For each test case, output a single line containing the lexicographically smallest sequence of cowmpetency scores consistent with what Farmer John remembers, or −1 if such a sequence does not exist.

SAMPLE INPUT:

1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5

SAMPLE OUTPUT:

1 2 2 3 4 4 1

We can see that the given output satisfies all of Farmer John's remembered pairs.
max(c1)=1, c2=2 and 1<2 so the first pair is satisfied
max(c1,c2,c3)=2, c4=3 and 2<3 so the second pair is satisfied
max(c1,c2,c3,c4)=3, c5=4 and 3<4so the third pair is satisfied

There are several other sequences consistent with Farmer John's memory, such as
1 2 2 3 5 4 1
1 2 2 3 4 4 5

However, none of these are lexicographically smaller than the given output.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

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

In test case 3, since C=1, the only potential sequence is

1 1

However, in this case, cow 2 does not have a greater score than cow 1, so we cannot satisfy the condition.

In test case 5,a₁and h₁ tell us that cow 6 is the first cow to have a strictly greater score than cows 1 through 4. Therefore, the largest score for cows 1 through 6 is that of cow 6: 5. Since cow 7 has a score of 7, cow 7 is the first cow to have a greater score than cows 1 through 6. So, the second statement that cow 9 is the first cow to have a greater score than cows 1 through 6 cannot be true.

SCORING:

Input 3 satisfies N≤10 and Q,C≤4.
Inputs 4-8 satisfy N≤1000.
Inputs 9-12 satisfy no additional constraints.
Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Bessie is trying to sort an array of integers using her own sorting algorithm. She has a pile of N (1≤N≤2⋅10⁵) integers a₁,a₂,…,a_N (1≤a_i≤10¹¹) that she will put in a separate array in sorted order. She repeatedly finds the minimum integer in her pile, removes it, and adds it to the end of the array. It takes Bessie p seconds to find the minimum integer in a pile of p integers.

Farmer John instructed some of the other cows in the farm to help Bessie with her task, but they are quite lazy, so Bessie uses that to her advantage. She divides the integers into two piles: Bessie pile and Helper pile. For every integer in Bessie's pile, she performs her algorithm as normal. For every integer in the helper pile, she assigns it to a different helper cow. Farmer John has a large farm, so Bessie can get as many helper cows as she wants. If a helper receives the integer a_i, Bessie instructs that cow to nap for a_i seconds, and add their integer to the end of the array immediately when they wake up. If Bessie and a helper add an integer to the array at the same time, Bessie's integer will get added first since she is the leader. If more than one helper gets assigned the same integer, they will add copies of that integer to the array at the same time.

Help Bessie divide her integers so that the final array is sorted and the time it takes to sort the array is minimized.

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

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

Each test case is formatted as follows:

The first line of each test case contains the number of integers N in Bessie's array.

The next line of each test case contains a₁,a₂,…,a_N, the integers that Bessie is sorting. The same integer may appear multiple times.

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

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

For each test case, output the minimum time to sort the array on a new line, if Bessie divides her integers optimally.

SAMPLE INPUT:

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

SAMPLE OUTPUT:

6
15
5
6

In the first example, Bessie can assign 1,2 to helpers and leave 4,5,10¹¹ for herself.

In the second example, the best Bessie can do is sort everything by herself. One division that does *not* work is for Bessie to assign 4 to a helper and the rest to herself because Bessie will end up adding 17 to the array before the helper adds 4
to the array.

In the third example, Bessie can assign all the integers to helpers.

In the fourth example, Bessie can assign 1,4,5 to helpers and leave 2,5,100
to herself.

SCORING:

Input 2: N≤16
Inputs 3-5: N≤150
Inputs 6-8: ∑N≤5000
Inputs 9-11: No additional constraints.

Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed N (2≤N≤10⁹) cows for the position. After each interview, he assigned an integer "cowmpetency" score to the candidate ranging from 1
to C(1≤C≤10⁴) that is correlated with their leadership abilities.

Because he has interviewed so many cows, Farmer John has forgotten all of their cowmpetency scores. However, he does remembers Q(1≤Q≤min(N−1,100)) pairs of numbers (a_i,h_i) where cow h_i was the first cow with a strictly greater cowmpetency score than cows 1 through a_i (so 1≤a_i<h_i≤N).

Farmer John now tells you the Q pairs of (a_i,h_i). Help him count how many sequences of cowmpetency scores are consistent with this information! It is guaranteed that there is at least one such sequence. Because this number may be very large, output its value modulo 10⁹+7.

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

The first line contains N, Q, and C.
The next Q lines each contain a pair (a_i,h_i). It is guaranteed that all a_j are distinct.

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

The number of sequences of cowmpetency scores consistent with what Farmer John remembers, modulo 10⁹+7.

SAMPLE INPUT:

6 2 3
2 3
4 5

SAMPLE OUTPUT:

6

The following six sequences are the only ones consistent with what Farmer John remembers:

1 1 2 1 3 1
1 1 2 1 3 2
1 1 2 1 3 3
1 1 2 2 3 1
1 1 2 2 3 2
1 1 2 2 3 3

SAMPLE INPUT:

10 1 20
1 3

SAMPLE OUTPUT:

399988086
Make sure to output the answer modulo 10⁹+7.

SCORING:

Inputs 3-4 satisfy N≤10 and Q,C≤4.
Inputs 5-7 satisfy N,C≤100.
Inputs 8-10 satisfy N≤2000 and C≤200.
Inputs 11-15 satisfy N,C≤2000.
Inputs 16-20 satisfy no additional constraints.
Problem credits: Suhas Nagar

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

咨询一对一备赛规划

Farmer John and his Q(1≤Q≤2⋅10⁵) cows are in Manhattan on vacation, but the cows have escaped and are now walking around freely in the city! Manhattan is huge – so huge that its N (1≤N≤2⋅10⁵) roads stretch infinitely in the x-y plane, but conveniently, those roads all run perfectly horizontally or vertically. Each horizontal and vertical road can be modeled by an equation of the form y= c_i or x=c_i , where c_i  is an integer in the range 0 to 10⁹ inclusive.

Farmer John knows exactly where each cow started walking and how long ago they escaped. Cows are very predictable, so each of them walks according to the following pattern:

They only walk north (+y) or east (+x) at one unit per second.
If they are currently on a single road, they continue walking along the road's direction.
If they are at the intersection of two roads, they walk north if they have been walking for an even number of seconds and east otherwise.

Given the layout of Manhattan and the information for each cow, help Farmer John determine where his cows are now!

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

The first line contains N and Q.

The next N lines describe the roads. Each road is described by a direction (H or V) and a coordinate c_i. It is guaranteed that the roads are unique.

The next Q lines describe the cows. Each cow is described by three integers (x_i,y_i,d_i), meaning that they started walking from (x_i,y_i) exactly d_i seconds ago. It is guaranteed that (x_i,y_i) lies on some road, and 0≤x_i,y_i,d_i≤10⁹ .

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

Output Q lines, where the ith line contains the current position of the ith cow.

SAMPLE INPUT:

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

SAMPLE OUTPUT:

14 5
7 13
6 15
6 16
110 4

The first two cows took the following paths:
(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

SCORING:
Inputs 2-4 satisfy N,Q,c_i,x_i,y_i,d_i≤100.
Inputs 5-9 satisfy N,Q≤3000.
Inputs 10-20 satisfy no additional constraints.

Problem credits: Benjamin Qi

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

咨询一对一备赛规划