2023年2月 USACO青铜组题目中文版
USACO以后可能不会提供题目的中文版了，但国内小学生阶段，要能通顺地理解英文题意，可能会有一定难度。因此我每次在比赛开始前，会把题目翻译成中文，发在群里，供孩子们参考。我的翻译自我感觉还不错，比洛谷里的那些UASCO题目翻译得好多了 :p 。
Problem 1. 饥饿的奶牛 Hungry Cow
Bessie 是一头饥饿的奶牛。每天晚餐时，只要谷仓里有干草，她就会吃一捆。农夫John不想让Bessie挨饿，因此他会在某些天送去几捆干草，送达时间是在早上（晚餐之前）。具体来说，农夫John会在第di天，送bi捆干草过去。（1≤di≤10^14， 1≤bi≤10^9）
要求计算在前T天中，Bessie总共会吃掉多少捆干草。
输入格式 (标准输入):
第一行包括N和T（其中1 ≤ N ≤ 10^5， 1 ≤ T ≤ 10^14）(译者注：下标和上标在纯文本格式下不好表示，请自己转换，pdf版就好一点)
接下来N行，每一行包括di和bi，确保1 ≤ d1 < d2 < ⋯ < dN ≤ T
输出格式 (标准输出):
输出Bessie在前T天会吃掉的干草捆数。
注意：本题中的数字可能很大，需要使用64位整数类型。（例如，在c/c++中，需要用long long）
样例1输入:
1 5
1 2
样例1输出:
2
说明：在第1天早上，会有2捆干草送达。Bessie会在第1天吃掉一捆干草，在第2天吃掉另一捆干草。而在第3-5天，Bessie没有任何干草可以吃。那么，Bessie在前5天中，总共吃了2捆干草。
样例2输入:
2 5
1 2
5 10
样例2输出:
3
说明：在第1天早上，会有2捆干草送达。Bessie会在第1天和第2天各吃掉一捆干草。第3天和第4天Bessie没有干草吃。在第5天早上，10捆干草送到。Bessie在第5天的晚餐上吃掉一捆。这样Bessie在前5天中，总计吃掉3捆干草。
样例3输入：
2 5
1 10
5 10
样例3输出SAMPLE OUTPUT:
5
说明：10捆干草在第一天早上送达。Bessie在第一天到第四天各吃了一捆干草。在第五天早上，又有10捆干草送达，这意味着谷仓里有16捆干草。第五天的晚餐，Bessie又吃了一捆干草。Bessie在前5天里总共吃了5捆干草。
计分:
输入数据 4-7: T≤10^5；
输入数据 8-13: 没有额外限制。
Problem credits: Brandon Wang
Problem 2. 印章网格
印章画（stamp painting）是在N×N格子的画布上的黑白画，其中某些单元格涂上了墨水，而其他单元格是空白的。它可以用N×N的字符数组来描述(1≤N≤20)。如果画布的某方格内有墨水，那么数组中对应的第i行第j列元素为 * ，否则为 . 。
Bessie想创作一幅印章画, 因此农夫John借给了她一个K×K（1 ≤ K ≤ N）大小的印章和一张N×N空白画布。Bessie可以将印章顺时针旋转90度，而且只要印章完全落在画布的网格内，她就可以在画布上的任何地方盖章。正式地讲就是，在盖章时，Bessie会选择两整数i、j，满足i∈[1, N−K+1]和j∈[1, N−K+1]。那么，对于印章上的某一点（i′, j′）（满足1≤i′,j′≤K），如果印章的该（i′, j′）点上有墨水，那么画布上的单元格 ( i + i′- 1, j + j′- 1)就会被涂成黑色。一旦画布的某单元格被涂成黑色，它就会一直保持黑色。
农夫John想知道，Bessie用他的印章，能否创作出她想要的印章画。对于T (1 ≤ T ≤ 100)组数据中的每一组，帮助农夫John求出问题的答案。
输入格式 (标准输入):
输入的第一行包含T，即测试数据的数量。
每个测试数据以一个整数N开始。后面跟着N行，每一行包含一个由 * 和 . 组成的字符串，表示Bessie想要绘制的印章画。接下来一行是K。之后跟着K行，每一行包含一个 * 和 . 组成的字符串，代表农夫John的印章。
每一个连续的测试用例之间用换行符分隔。
输出格式 (标准输出):
对于每一个测试数据，在单独的行上输出“YES”或“NO”。
样例输入：SAMPLE INPUT:
4
2
**
*.
1
*
3
.**
.**
***
2
.*
**
3
...
.*.
...
3
.*.
...
...
3
**.
.**
..*
2
.*
*.
样例输出SAMPLE OUTPUT:
YES
YES
NO
YES
说明：在第一个测试用例中，Bessie可以执行以下盖章顺序:
在(1, 1)处盖章
在(1, 2)处盖章
在(2, 1)处盖章
在第二个测试用例中，Bessie可以执行以下盖章顺序:
在 (2, 2) 处盖章
在 (2, 1) 处盖章
旋转 90度
旋转90度
在(1, 2) 处盖章
在第三个测试用例中，无法绘制中间的单元格。
在第四个测试案例中，Bessie可以执行以下的盖章顺序:
旋转 90度
在(1, 1)处盖章
在(1, 2)处盖章
在(2, 2)处盖章
Problem credits: Benjamin Qi and Claire Zhang
Problem 3. 观看 Mooloo电视台
Bessie喜欢在Mooloo电视台观看节目。因为Bessie很忙，因此她已经为接下来的N(1 ≤ N ≤ 10^5)天制定了观看Mooloo的时间表。因为Mooloo是付费订阅服务，所以她现在需要决定如何将需要支付的金额降至最低。
Mooloo有一个有趣的订阅系统：连续d天订阅Mooloo需要花费d + K ( 1 ≤ K ≤ 10^9)个moony币。您可以在任何时候开始订阅，并且如果当前订阅到期了，您可以随时开始重新订阅，次数不限。给定这些条件，计算出Bessie为实现她的观看计划所需要支付的最少moony币数量。
输入格式 (标准输入):
第一行包含整数N和K.
第二行包含N个整数，描述了Bessie观看Mooloo的日子：
1 ≤ d1 < d2 < ⋯ < dN ≤ 10^14
输出格式 (标准输出):
注意，这个问题中涉及的大量整数可能需要使用64位整数数据类型(例如, C/C++中的"long long").
输入1样例SAMPLE INPUT:
2 47 9
输出1样例SAMPLE OUTPUT:
7
说明：Bessie在第7天购买了为期三天的订阅，花费 d + K = 3 + 4 = 7个moony币.
输入2样例SAMPLE INPUT:
2 31 10
输出2样例SAMPLE OUTPUT:
8
Bessie首先在第1天买了一天的订阅，花费d + K = 1 + 3 = 4个 moony币. Bessie还在第10天购买了为期一天的订阅，花费d + K = 1 + 3 = 4个moony币。Bessie总共花8个moony币。
计分SCORING:
输入样例 3-5: N≤10
输入样例 6-12: 没有额外限制
Problem credits: Danny Mittal
