分类： 赛事资讯

**Note: The time limit for this problem is 4s, 2x the default.**

To celebrate the start of spring, Farmer John's N cows (1≤N≤2⋅10⁵ ) have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way.

Specifically, there are N positions around the circle, numbered sequentially from 0 to N−1, with position 0 following position N−1. A cow resides at each position. The cows are also numbered sequentially from 0 to N−1. Initially, cow i starts in position i. You are told a set of K positions 0=A₁<A₂<…<A_K<N that are "active", meaning the cows in these positions are the next to move (1≤K≤N).

In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position A₁ moves to position A₂, the cow at position A₂ moves to position A₃, and so on, with the cow at position AK moving to position A₁. All of these K moves happen simultaneously, so the after the rotation is complete, all of the active positions still contain exactly one cow. Next, the active positions themselves shift: A₁ becomes A₁+1,A₂ becomes A₂+1, and so on (if A_i =N−1 for some active position, then Ai circles back around to 0).

Please calculate the order of the cows after T minutes of the dance (1≤T≤109).

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

The first line contains three integers N, K, and T.
The second line contains K integers representing the initial set of active positionsA₁,A₂,…A_K. Recall that A₁=0 and that these are given in increasing order.

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

Output the order of the cows after T minutes, starting with the cow in position 0, separated by spaces.

SAMPLE INPUT:

5 3 4
0 2 3

SAMPLE OUTPUT:

1 2 3 4 0
For the example above, here are the cow orders and A
for the first four timesteps:

Initial, T = 0: order = [0 1 2 3 4], A = [0 2 3]
T = 1: order = [3 1 0 2 4]
T = 1: A = [1 3 4]
T = 2: order = [3 4 0 1 2]
T = 2: A = [2 4 0]
T = 3: order = [2 4 3 1 0]
T = 3: A = [3 0 1]
T = 4: order = [1 2 3 4 0]

SCORING:

Inputs 2-7: N≤1000,T≤10000
Inputs 8-13: No additional constraints.
Problem credits: Claire Zhang

Farmer John is interested in better interacting with his fellow cows, so he decided he will learn the moo language!

Moo language is actually quite similar to English, but more minimalistic. There are only four types of words: nouns, transitive verbs, intransitive verbs, and conjunctions. Every two consecutive words must be separated by a space. There are also only two types of punctuation: periods and commas. When a period or comma appears after a word, it appears directly after the word, and is then followed by a space if another word appears next.

A sentence needs to follow one of the following formats:

Type 1: noun + intransitive verb.
Type 2: noun + transitive verb + noun(s). Specifically, at least one noun must follow the transitive verb, and there must be a comma in front of every following noun besides the first following noun.
Two sentences may be joined into a compound sentence if a conjunction is placed in between them. The resulting compound sentence cannot be further joined with other sentences or other compound sentences. Every sentence (or compound sentence, if two sentences are joined) must end with a period.

Farmer John has a word bank of N words, C commas, and P periods (1≤P,C≤N≤10³). He may only use a word or punctuation mark as many times as it appears in the word bank. Help him output a sequence of sentences containing the maximum possible number of words.

Each input file contains T (1≤T≤100) independent instances of this problem.

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

The first line contains T, the number of instances. Each instance is specified as follows:The first line consists of three integers, N, C, and P.

The N following lines will consist of two strings. The first string will be the word itself that FJ can use (a string of at least 1 and at most 10 lowercase letters), and the second string will be either one of the following: noun, transitive-verb, intransitive-verb, or conjunction, denoting the type of the word. It is possible the same word occurs more than once in FJ's word bank, but it will always have the same type each time it appears.

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

In the first line, output the maximum possible number of words.
In the second line, output any sequence of sentences with the maximum possible number of words. Any valid sequence will be accepted.

The grader is sensitive to whitespace, so make sure not to output any extraneous spaces, particularly at the end of each line.

SAMPLE INPUT:

3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

SAMPLE OUTPUT:

0

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.
For the first test case, the only valid sequence is the empty sequence. For each of the next two test cases, it is possible to construct a sequence of sentences using every word from the word bank except for one.

SCORING:

Inputs 2-6: N≤10
Inputs 7-11: N≤100
Inputs 12-16: N≤1000
Inputs with remainder 2 when divided by 5: There are no transitive verbs.
Inputs with remainder 3 when divided by 5: There are no intransitive verbs.
Inputs with remainder 4 when divided by 5: There are no conjunctions.

Problem credits: Chongtian Ma

Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out over N (1≤N≤2⋅10⁵) text messages. Their conversation can be represented by a string S of length N where S_i is either B or E, meaning the ith message was sent by Bessie or Elsie, respectively.

However, Farmer John hears of the plan and attempts to intercept their conversation. Thus, some letters of S are F, meaning Farmer John obfuscated the message and the sender is unknown.

The excitement level of a non-obfuscated conversation is the number of times a cow double-sends - that is, the number of occurrences of substring BBor EE in S. You want to find the excitement level of the original message, but you don’t know which of Farmer John’s messages were actually Bessie’s / Elsie’s. Over all possibilities, output all possible excitement levels of S.

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

The first line will consist of one integer N.
The next line contains S.

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

First output K, the number of distinct excitement levels possible. On the next K
lines, output the excitement levels, in increasing order.

SAMPLE INPUT:

4
BEEF

SAMPLE OUTPUT:

2
1
2

SAMPLE INPUT:

9
FEBFEBFEB

SAMPLE OUTPUT:
2
2
3

SAMPLE INPUT:
10
BFFFFFEBFE

SAMPLE OUTPUT:
3
2
4
6

SCORING:
Inputs 4-8: N≤10
Inputs 9-20: No additional constraints.
Problem credits: William Yue and Claire Zhang

**Note: The time limit for this problem is 4s, 2x the default.**

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string "bqessiyexbesszieb", Farmer John's eyes ignore some of the letters and all he sees is "bessiebessie".

Given a string s, let B(s)represent the maximum number of repeated copies of "bessie" one can form by deleting zero or more of the characters from s. In the example above, B("bqessiyexbesszieb")=2.

Computing B(s) is an interesting challenge, but Farmer John is interested in solving a challenge that is even more interesting: Given a string t of length at most 3⋅105 consisting only of characters a-z, compute the sum of B(s) over all contiguous substrings s of t.

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

The input consists of a nonempty string of length at most 3⋅105
whose characters are all lowercase English letters.
OUTPUT FORMAT (print output to the terminal / stdout):
Output a single number, the total number of bessies that can be made across all substrings of the input string.

SAMPLE INPUT:

bessiebessie

SAMPLE OUTPUT:

14

Twelve substrings contain exactly 1 "bessie", and 1 string contains exactly 2 "bessie"s, so the total is 12⋅1+1⋅2=14.

SAMPLE INPUT:

abcdefghssijebessie

SAMPLE OUTPUT:

28

SCORING:

Inputs 3-5: The string has length at most 5000.
Inputs 6-12: No additional constraints.
Problem credits: Brandon Wang and Benjamin Qi

**Note: The time limit for this problem in Python is 15s. Other languages have the default time limit of 2s.**

Each of Farmer John's N barns (2≤N≤10⁵) has selected a team of C cows (1≤C≤18) to participate in field day. The breed of every cow is either a Guernsey or a Holstein.

The difference between two teams is defined to be the number of positions i
(1≤i≤C) at which the breeds of the cows in the ith positions differ. For every team t from 1…N, please compute the maximum difference between team t
and any other team.

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

The first line contains C and N.
The next N lines each contain a string of length C of Gs and Hs. Each line corresponds to a team.

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

For each team, print the maximum difference.

SAMPLE INPUT:

5 3
GHGGH
GHHHH
HGHHG

SAMPLE OUTPUT:

5
3
5

The first and third teams differ by 5. The second and third teams differ by 3.

SCORING:

Inputs 2-5: C=10
Inputs 6-9: All answers are at least C−3.
Inputs 10-20: No additional constraints.

Problem credits: Benjamin Qi

Note: The time limit for this problem is 4s, 2x the default.

Farmer John's N cows (1≤N≤1.5⋅10⁵) have integer milk production values a₁,…,a_N. That is, the i th cow produces a_i units of milk per minute, with 0≤ a_i ≤10⁸.

Each morning, Farmer John starts with all N cows hooked up to his milking machine in the barn. He is required to unhook them one by one, sending them out for their daily exercise routine. The first cow he sends out is unhooked after just 1 minute of milking, the second cow he sends out is unhooked after another minute of milking, and so on. Since the first cow (say, cow x) only spends one minute on the milking machine, she contributes only a_x units of total milk. The second cow (say, cow y) spends two total minutes on the milking machine, and therefore contributes 2a_y units of total milk. The third cow (say, cow z) contributes 3az total units, and so on. Let T represent the maximum possible amount of milk, in total, that Farmer John can collect, if he unhooks his cows in an optimal order.

Farmer John is curious how T would be affected if some of the milk production values in his herd were different. For each of Q queries (1≤Q≤1.5⋅10⁵), each specified by two integers i and j , please calculate what would be the new value of T if a_i were set to j(0≤j≤108). Note that each query is considering a temporary potential change independent of all other queries; that is, a_i reverts back to its original value before the next query is considered.

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

The first line contains N.

The second line contains a1…aN.

The third line contains Q.

The next Q lines each contain two space-separated integers i
and j.

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

Please print the value of T for each of the Q queries on separate lines.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

55
81
98
For the first query, a would become [1,1,4,2,6], and T=1⋅1+2⋅1+3⋅2+4⋅4+5⋅6=55.

For the second query, a would become [1,8,4,2,6], and T=1⋅1+2⋅2+3⋅4+4⋅6+5⋅8=81.

For the third query, a would become [1,10,4,5,6], and T=1⋅1+2⋅4+3⋅5+4⋅6+5⋅10=98.

SCORING:

Inputs 2-4: N,Q≤1000
Inputs 5-11: No additional constraints.
Problem credits: Benjamin Qi

2023 年美国公开赛的特色是算法编程问题，涵盖了广泛的技术和难度级别。

在为期 6672 天的时间内，共有 4 名不同的用户登录了比赛。共有来自4913个不同国家的74名参与者提交了至少一个解决方案：

2751 USA 1341 CHN 147 CAN 99 KOR 54 IND 43 ISR 36 DEU
35 SGP 29 ROU 27 ARM 25 EGY 23 TWN 21 VNM 20 AUS
19 POL 17 GBR 14 HKG 12 FRA 11 TUR 11 SLV 11 GEO
9 MYS 8 TUN 8 NZL 8 MNG 7 UZB 7 SYR 7 JPN
7 BRA 6 CHE 5 ZAF 5 UKR 5 KGZ 5 BGD 4 RUS
4 KAZ 4 FIN 4 AZE 3 THA 3 PER 3 PAK 3 NLD
3 IRL 3 IDN 3 GRC 3 BLR 3 BGR 2 TKM 2 SRB
2 SAU 2 NGA 2 MEX 2 IRN 2 ETH 2 EST 2 CUB
2 COL 1 SVK 1 REU 1 PRK 1 PHL 1 MLT 1 MKD
1 LTU 1 LKA 1 KWT 1 KHM 1 ITA 1 ISL 1 ESP
1 COD 1 CHL 1 ARE 1 AFG

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

5573 C++17
1878 C++11
1862 Java
1360 Python 3.6.9
38 C
13 Python 2.7.17

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

USACO 2023 美国公开赛，白金

白金组共有396名参与者，其中280名是大学预科生。最佳射手的成绩在这里。恭喜所有顶级参与者取得优异成绩！

1 Pareidolia
查看问题 | 测试数据 | 解决方案
2 Good Bitstrings
查看问题 | 测试数据 | 解决方案
3 Triples of Cows
查看问题 | 测试数据 | 解决方案

USACO 2023 年美国公开赛，金牌

黄金组共有880名参与者，其中648名是大学预科生。所有在本次比赛中得分达到或更高的参赛者将自动晋升到白金组。所有晋升者的详细结果都在这里。

1 Custodial Cleanup
查看问题 | 测试数据 | 解决方案
2 Pareidolia
查看问题 | 测试数据 | 解决方案
3 Tree Merging
查看问题 | 测试数据 | 解决方案

USACO 2023 年美国公开赛，银牌

白银组共有2610名参与者，其中2071名是大学预科生。所有在本次比赛中得分达到或更高的参赛者将自动晋升为黄金组。请注意，由于“现场日”的某些测试数据意外不足 问题，对数据进行了调整，并重新对该问题的提交进行了评分;在这种情况下，晋升授予那些在重新评分之前或之后通过截止时间的人（请记住，在比赛结束后，测试数据总是可能需要调整的）。

1 Milk Sum
查看问题 | 测试数据 | 解决方案
2 Field Day
查看问题 | 测试数据 | 解决方案
3 Pareidolia
查看问题 | 测试数据 | 解决方案

USACO 2023 年美国公开赛，铜牌

青铜组共有2960名参与者，其中2313名是大学预科生。所有在本次比赛中得分达到或更高的参赛者将自动晋升为银级。

1 FEB
查看问题 | 测试数据 | 解决方案
2 Moo Language
查看问题 | 测试数据 | 解决方案
3 Rotate and Shift
查看问题 | 测试数据 | 解决方案

结语

美国公开赛的结束结束了我们的 2022-2023 赛季，我很高兴看到它既有强大的参与度，也有 强劲的成绩。看看最近的计算挑战和趋势， 对那些强大的人的需求从未如此强烈 计算问题解决能力。看看我们的比赛结果， 看到如此强大的未来人才管道令人鼓舞。

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

我们期待在下个赛季开始时再次见到大家。 请祝我们在训练营中好运，当我们参加IOI和 今年的EGOI！