作者： chenchen

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试题答案+详细解析

咨询一对一备赛规划

Farmer John has N cows on his farm (2≤N≤2⋅10⁵), conveniently numbered 1…N
. Cow i is located at integer coordinates (x_i,y_i) (1≤x_i,y_i≤N). Farmer John wants to pick two teams for a game of mooball!

One of the teams will be the "red" team; the other team will be the "blue" team. There are only a few requirements for the teams. Neither team can be empty, and each of the N cows must be on at most one team (possibly neither). The only other requirement is due to a unique feature of mooball: an infinitely long net, which must be placed as either a horizontal or vertical line in the plane at a non-integer coordinate, such as x=0.5. FJ must pick teams so that it is possible to separate the teams by a net. The cows are unwilling to move to make this true.

Help a farmer out! Compute for Farmer John the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 10⁹+7.

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

The first line of input contains a single integer N.

The next N lines of input each contain two space-separated integers x_i and y_i. It is guaranteed that the x_i form a permutation of 1…N, and same for the y_i.

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

A single integer denoting the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 10⁹+7.

SAMPLE INPUT:
2
1 2
2 1

SAMPLE OUTPUT:
2
We can either choose the red team to be cow 1 and the blue team to be cow 2, or the other way around. In either case, we can separate the two teams by a net (for example, x=1.5).

SAMPLE INPUT:

3
1 1
2 2
3 3

SAMPLE OUTPUT:

10

Here are all ten possible ways to place the cows on teams; the ith character denotes the team of the ith cow, or . if the ith cow is not on a team.

RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR

SAMPLE INPUT:

3
1 1
2 3
3 2

SAMPLE OUTPUT:

12

Here are all twelve possible ways to place the cows on teams:

RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR

SAMPLE INPUT:

40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40

SAMPLE OUTPUT:

441563023

Make sure to output the answer modulo 109+7.

SCORING:

Input 5: N≤10
Inputs 6-9: N≤200
Inputs 10-13: N≤3000
Inputs 14-24: No additional constraints.
Problem credits: Dhruv Rohatgi

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

咨询一对一备赛规划

**Note: The memory limit for this problem is 512MB, twice the default.**

Bessie is having fun playing a famous online game, where there are a bunch of cells of different labels and sizes. Cells get eaten by other cells until only one winner remains.

There are N (2≤N≤5000) cells in a row labeled 1…N from left to right, with initial sizes s₁,s₂,…,s_N (1≤s_i≤10⁵). While there is more than one cell, a pair of adjacent cells is selected uniformly at random and merged into a single new cell according to the following rule:

If a cell with label a and current size c_a is merged with a cell with label b and current size c_b , the resulting cell has size c_a +c_b and label equal to that of the larger cell, breaking ties by larger label. Formally, the label of the resulting cell is

For each label i in the range 1…N , the probability that the final cell has label i
can be expressed in the form where b_i≢0 ( mod 10⁹+7). Output a_ib⁻¹_i ( mod 10⁹+7).

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

The first line contains N.
The next line contains s₁,s₂,…,s_N

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

The probability of the final cell having label i modulo 10⁹+7
for each i in 1…N on separate lines.

SAMPLE INPUT:

3
1 1 1

SAMPLE OUTPUT:

0
500000004
500000004

There are two possibilities, where (a,b)→c means that the cells with labels a and b merge into a new cell with label c.

(1, 2) -> 2, (2, 3) -> 2
(2, 3) -> 3, (1, 3) -> 3

So with probability 1/2 the final cell has label 2 or 3.

SAMPLE INPUT:

4
3 1 1 1

SAMPLE OUTPUT:

666666672
0
166666668
166666668
The six possibilities are as follows:

(1, 2) -> 1, (1, 3) -> 1, (1, 4) -> 1
(1, 2) -> 1, (3, 4) -> 4, (1, 4) -> 1
(2, 3) -> 3, (1, 3) -> 1, (1, 4) -> 1
(2, 3) -> 3, (3, 4) -> 3, (1, 3) -> 3
(3, 4) -> 4, (2, 4) -> 4, (1, 4) -> 4
(3, 4) -> 4, (1, 2) -> 1, (1, 4) -> 1

So with probability 2/3 the final cell has label 1, and with probability 1/6
the final cell has label 3 or 4.

SCORING:

Input 3: N≤8
Inputs 4-8: N≤100
Inputs 9-14: N≤500
Inputs 15-22: No additional constraints.
Problem credits: Benjamin Q_i

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

咨询一对一备赛规划