# 菜就多练

## A. 土拨鼠，上灯台

# 故事背景

“土拨鼠，上灯台，偷油吃，下不来……”这是小盆友们最熟悉的歌谣。今天，n只土拨鼠真要去上灯台。

# 题目描述

为了防止土拨鼠上灯台时被猫发现（不要问我为什么不要被猫发现，因为它叫土拨“鼠”），只有体型小于k的土拨鼠才能不被猫发现。请你编写一个程序，判断n只土拨鼠中有几只能顺利的上灯台。
# 输入

两行。第一行为整数n（0<n<101）和k(4<k<21)，表示n只土拨鼠和不让猫发现的最大的k体型。第二行为n个整数，表示每只土拨鼠的体型（1~100）。

# 输出

一个整数m，表示有几只土拨鼠能够上灯台，没有输出-1。

# 样例

```样例输入
5 10
12 13 6 9 10
```

```样例输出
3
```


---

## B. 土拨鼠比沙雕

# Background

n只沙雕又愚蠢的土拨鼠，他们要比谁最沙雕

# Description

给出n只土拨鼠的沙雕程度，输出最沙雕的土拨鼠的编号

# Format

## Input

第一行一个整数，n

后面n行，每行一个整数，表示第i个土拨鼠的沙雕程度。

## Output

一个整数，表示最沙雕土拨鼠的编号，沙雕土拨鼠们的沙雕程度互不相同。

# Samples

```input1
5
78
87
98
35
10
```

```output1
3
```

# Limitation

n<=1000
每只土拨鼠最多能有多沙雕呢？答：最沙雕的土拨鼠的沙雕程度大于long long long的范围，但也不会超过10^1000次方，输入的数字没有前导零



---

## C. 土拨鼠跑酷

# Background

众所周知，土拨鼠跑酷是一款很有意思的游戏

# Description

数轴就是游戏的赛道，0我们不管他，1就是起点，后面的数，质数就是岩浆，合数就是陆地。在n的地方藏有宝藏，就算n是质数，那n也是陆地。土拨鼠桐桐想找到宝藏，他可以在陆地上走，记为walk(走过方块的个数)，他还可以可以跳过1～2个岩浆，记为jump(跳过岩浆的个数)，如果跳不过去，他就会用飞行器飞过去，记为fly(飞过岩浆的个数)。请你规划桐桐找到宝藏的路径。

# Format

## Input

一个数，n，表示宝藏在n

## Output

若干行，找到宝藏的路径。

# Samples

```input1
13
```

```output1
jump(2)
jump(1)
jump(1)
walk(2)
jump(1)
walk(1)
```

# Limitation

$n \le 2*10^6$
站在陆地上，跳到陆地上。站在陆地上，飞到陆地上。
如果无需走，就不必要走。

# 注意

文件重定向, run.in, run.out。8.31增加一组hack



---

## D. 土拨鼠炒果子2

# Background

土拨鼠结婚后迷上了炒果子, 他想通过炒"果子"获取更多的收益改变生活, 土拨鼠只能选择 **某一天** 买入这只果子，并选择在 **某一天** 卖出该果子。设计一个算法来计算你所能获取的最大利润。

# Description

在每一天, 你都可以买入或者卖出果子, 在任何时候你最多只能持有一个果子, 你也可以在今天买入今天卖出. 但是你不可以在没有果子的时候卖出果子. 计算买卖的最大利润.

# Format

## Input

第1行为n

第2行为n个元素的一个数组 `a` ，它的第 `i` 个元素 `a[i]` 表示果子第 `i` 天的价格。

## Output

你可以从交易中获取的最大利润。如果你不能获取任何利润，返回 `0` 。

# Samples

### 样例1

```input1
6
7 1 5 3 6 4
```

```output1
7
```

### 样例2

```input2
5
1 2 3 4 5
```

```output2
4
```

# 样例解析

样例1解释：在第 2 天（果子价格 = 1）的时候买入，在第 3 天（果子价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（果子价格 = 3）的时候买入，在第 5 天（果子价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

# Limitation

1 <= n <= 10^5

0 <= a[i] <= 10^4



---

## E. 进步的土拨鼠

# 故事背景

期末考试结束了，土拨鼠总算放下了心中的负担。成绩发下后，土拨鼠想看看自己的期末成绩和复习时的模拟考试的成绩相比有没有进步。请你编写一个程序，看看土拨鼠进步了没有。

# 题目描述

给定土拨鼠所有模拟考试时的成绩以及这份试卷的难易程度，和土拨鼠真正期末考试的成绩和难度，判断土拨鼠进步了还是退步了。判断方法如下：

假设第1场模拟考试难度为5，土拨鼠是290分，则第一场考试的最终成绩为5 * 290 = 1450 分。给出 $n$ 组模拟考试的难度和成绩，计算出最终得分后取平均值。再给出真正期末考试的难度和成绩，判断期末的最终得分与模拟的平均成绩，大则为进步，小则为退步，相等也为退步。

# 输入

$n$ + 2 行。

第一行为一个整数 $n（2 \leq n \leq 100）$，表示模拟期末考试的次数。

接下来 2 到 $n$ + 1 行，每行一个实数 $x（1 \leq x \leq 4）$ 和整数 $y（0 \leq y \leq 100）$，表示这次模拟考试的难度和土拨鼠的得分。

最后一行为两个整数，表示真正期末考试的难度和土拨鼠的得分。

# 输出

输出土拨鼠是进步还是退步。如果进步输出`1`，退步输出`0`。并输出土拨鼠进步或退步了多少分（保留1位小数）。

# 样例

```input1
5
0.2 295
2.4 260
0.6 300
3.2 252
1.1 298
1.5 295
```

```output1
1
43.1
```

# 提示

土拨鼠经历了5次模拟考试，其最终得分为：

* 第1次：0.2 * 295 = 59
* 第2次：2.4 * 260 = 624
* 第3次：0.6 * 300 = 180
* 第4次：3.2 * 252 = 806.4
* 第5次：1.1 * 298 = 327.8

所以，土拨鼠模拟考试的平均分为：
（59 + 624 + 180 + 806.4 + 327.8）/ 5 = 399.44

土拨鼠正式期末考试的最终得分为：

1.5 * 295 = 442.5

因此，土拨鼠进步了：
442.5 - 399.44 = 43.06
保留一位小数为43.1。





---

## F. 土拨鼠跑步

# 故事背景

为了参加新一届的跑步比赛，土拨鼠决定好好训练一下。今天训练时，他给自己定了一个目标，今天的训练距离要大于 $k$。可土拨鼠的体力有限，每跑一分钟体力就会下降。请你编程计算一下，今天土拨鼠至少要跑多长时间。

# 题目描述

假设第一分钟土拨能跑的距离是1，那么它第二分钟只能跑 $\frac 12$，第三分钟只能跑  $\frac 13$ …… 以此类推，当土拨鼠的体力逐渐下降，跑的距离也就越来越短。当土拨鼠跑的距离大于 $k$ 时，他一共训练了多长时间？

# 输入

一个整数 $k$（2 $\leq$  $k$ $\leq$ 20），表示土拨鼠今天要跑大于 $k$ 米。

# 输出

一个整数，表示土拨鼠今天最少的训练时长。

# 样例

```input1
5
```

```output1
83
```

```input2
1
```

```output2
2
```

# 提示

土拨鼠跑的距离要**大于k**，不是大于等于k



---

## G. 质量不好的空调

# 故事背景

夏天到了，土拨鼠去买了一台空调。可这台空调的质量不是很好，风力不稳定，一会儿风大一会儿风小。可土拨鼠怕热，它打算连续开 n 个小时的空调。

在这 n 个小时里，土拨鼠可能在**运动 do exercises** 或**看电视 watch TV** 或**读书 read books**。当土拨鼠在运动时，如果空调风力小于 k ，那么土拨鼠就会感到热。

现在知道了在接下来 n 个小时中每个小时空调的风力和土拨鼠在干什么，请你编程计算出土拨鼠有几个小时**没有感到热**。

# 题目描述

给定 n 个小时中每个小时空调的风力和土拨鼠在干什么，计算出土拨鼠有几个小时**没有感到热**。

### 土拨鼠感到热的条件：

* 正在运动，且空调风力**小于 k 时**感到热。

### 土拨鼠不感到热的条件：

* 正在看电视或读书时不感到热。
* 正在运动，但空调风力**大于等于 k 时**不感到热。

# 输入

n+1 行。
第 1 行是两个整数 n 和 k 。表示空调要连续开 n 个小时，和土拨鼠在运动时希望空调达到的风力 k 。
第 2 到 n+1 行，每行一个整数 m 和字符串 s 。表示在第 i 个小时空调的风力 m 和土拨鼠此时正在干的事情s（运动 do_exercises  ,   看电视 watch_TV  ,   读书 read_books）

# 输出

输出有几个小时土拨鼠**没有感到热**。

# 样例

```input1
5 4
3 read_books
3 do_exercises
6 do_exercises
4 read_books
2 watch_TV
```

```output1
4
```

```input2
3 6
6 do_exercises
9 read_books
1 watch_TV
```

```output2
3
```

# 提示

在输入时，第2行到第n+1行每行的第二个字符串表示土拨鼠此时正在干的事情s：

* 运动是 do_exercises
* 看电视是 watch_TV
* 读书是 read_books

注意有   _  （下划线）。



---

## H. 土拨鼠打乒乓球

# 故事背景

今年是土拨鼠历2022年

$r$ 年在 $M$ 国举行的奥运会马上就要到了，而土拨鼠就是中国乒乓球队的一员，马上也要去 $M$ 国参加奥运会了！

可是土拨鼠第一次参加奥运会，心中总存在着忧虑。这时，土拨鼠和它的教练请你通过现在已经知道的数据，帮土拨鼠预测一下奥运赛场上土拨鼠的成绩，同时土拨鼠也需要加紧训练。

由于打乒乓球是两个人对打，因此“知己知彼 百战不殆”。现在勤劳的土拨鼠和他的教练通过观察其他各国乒乓球运动员的以往比赛，知道了它们的水平，也知道了它们的进步速度，请你帮助土拨鼠预测一下赛场上土拨鼠能赢几位选手。

# 题目描述

给定奥运赛赛场上土拨鼠面临的对手数量 $n$，和这些对手现在的水平 $a_i$ 以及进步速度 $b_i$（进步速度指的是从现在2022年到 $r$ 年之间的这几年中，平均每年的进步）。再给出土拨鼠自己现在的水平和进步速度。请你帮助土拨鼠预测一下赛场上土拨鼠一定能赢几位选手。(如果两只土拨鼠战斗力相同, 则不能一定战胜对手)

# 输入格式

第一行包含两个整数 $n(1\leq n\leq 32767)$ 和 $r(2023\leq r\leq32767)$ ，表示奥运会上土拨鼠的对手数量和奥运会的年份。

第二行包含两个整数 $x(1\leq x\leq 32767)$ 和 $y(1\leq y\leq 32767)$，表示土拨鼠现在的水平和土拨鼠的进步速度。

接下来 $n$ 行，每行包含一个字符串 $s_i$ 和两个整数 $a_i(1\leq a_i\leq 32767)$ 和 $b_i(1\leq b_i\leq 32767)$，分别表示每名对手的名字，以及它们现在的水平和进步速度。

# 输出格式

按字典序输出你预测的土拨鼠能赢得选手的名字（以空格分开，每5个名字换一行），并在最后一行输出赢的选手的数量。如果土拨鼠输给了所有对手，则只输出一行-1。

# 样例

```input1
7 2024
10 2
Sam 9 2
Peter 11 1
David 10 3
Marco 3 5
Billy 6 1
Ana 5 2
Tom 1 1
```

```output1
Ana Billy Marco Peter Sam
Tom
6
```

# 提示

注意每行包含5个名字



---

## I. 约瑟“人”环

# 故事背景

$n$ 只愚蠢的人类被抓到了土拨鼠浚庭的家中。而这时，浚庭发现他抓的人类数量比它想要的多了一只，于是想将这只幸运的人类吃掉。浚庭觉得，幸运的人类应该味道鲜美，于是就想把这只幸运的人类找到并吃掉。土拨鼠浚庭千思百想，想到了一个找到这只幸运的人类的好方法。

# 题目描述

首先土拨鼠浚庭将 $n$ 只愚蠢的人类摆成一个圈。

- 第一次浚庭要淘汰**2**个人类,
  人类从1号位置开始报数。数到2的人类出列。
- 第二次浚庭要淘汰**3**个人类,
  人类从刚才出列的人类的下一个位置开始报数，数到3的人类出列。
- 第三次浚庭要淘汰**5**个人类,
  人类从刚才出列的人类的下一个位置开始报数，数到5的人类出列。
- 第四次浚庭要淘汰**7**个人类,
  人类从刚才出列的人类的下一个位置开始报数，数到7的人类出列。
- ……

每次淘汰的人数就是数到几要淘汰的数字。而且这个数字就是前一个数之后的第一个质数。

最后只剩一只愚蠢的人类时，这只人类就是最幸运的土拨鼠，浚庭就要将它吃掉。请你编程计算一下，最幸运的人类站在几号位置。

# 输入

一个整数 $n（1\leq n\leq 32767）$ ，表示土拨鼠的总只数。

# 输出

最美味的人类的编号。

# 样例

```input1
1
```

```output1
1
```

```input2
11
```

```output2
5
```

# 提示

【样例2】说明：

11只人类：

![image](file://c_qEqQwSFZHIwHMkqp15T.png)

第一轮，淘汰2只人类：

![image](file://CovHeG98Y7ju18HUBezXP.png)

第二轮，淘汰3只人类：

![image](file://-DuIwe5I0hVDPUK3nYF5S.png)

第三轮，淘汰5只人类：

![image](file://VPR_f0Pf27-jW1faIi0dH.png)

因此站在5号位置的人类是最幸运且美味的。



---

## J. 麦森数（超级难！！）

# 题目背景

形如 $2^p$-1 的素数称为麦森数，这时 P 一定也是个素数。但反过来不一定，也就是如果 P 为素数， $2^p$ -1 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 P=3021377，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。

*PS：这和题目没什么太大关系 ^ _ ^*

### 重要说明：此题为转载题目，来源在最后

# 题目要求

输入一个正整数 P ， 输出 $2^p$ - 1的位数，并在下一行输出它的后500位数字，不够的补0。

## 输入

输入 P ， $1000\leq P\leq 310000$ .

## 输出

两行，第一行是 $2^p-1$ 的位数， 第二行是$2^p-1$的后500位（不够补0）

# 样例

```input1
1279
```

```output1
386
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
```

# 时限

一秒钟，125MB

## 来源

洛谷题库 | 计算机教育



---

## K. jyfuj

# 题目

输入一个字符串，解析出src,dst,no




---

## L. 土拨鼠的约分

# 题目描述

给定一个分数，帮助土拨鼠将它约分到最简分数。

# 输入

一个字符串。字符串由 分子/分母 的形式表示，而且其中的 '/' 号个数不限，也就是说输入`5/2`或`5/////////2`都表示的是$\frac{5}{2}$这个分数。分子分母均在long long范围内的正整数（不包括0）。

# 输出

输出3行，为约分后的分数。

第一行为分子；

第二行为分数线 ------- （减号的个数由分子与分母中位数最多的个数所决定）；

第三行为分母；

重要提示：如果最后约出分母为1的情况，则输出一行，为一个整数。

# 样例

```input1
3//////6
```

```output1
1
-
2
```

```input2
30////////////////////4
```

```output2
15
--
2
```

```input3
1/1
```

```output3
1
```

# 提示

输入字符串中 '/' 号的个数不大于80个。



---

## M. 土拨鼠和猴子

# 土拨鼠和猴子打架

一只土拨鼠和n只喜欢吃shi味干脆面的猴子打架 土拨鼠输了 伤心的回家找妈妈

# 题目

猴子因为经常吃 shi味干脆面 所以他进化了 两只土拨鼠妈妈可以在一个小时内打败一只猴子 而猴子因为喜欢乱喷shi 每隔半个小时就会变得虚弱 如果超过一个小时吃不shi味干脆面 就会缩水 变成一只狗 丧失战斗能力

## 输入

输入猴子数量

# 输出

输出最少需要多少土拨鼠妈妈

```




---

## N. 土拨鼠凯旋~战斗胜利!

# Background

经过短暂的战争, 土拨鼠军团战胜了人类, 抓获了不少人类俘虏.

# Description

土拨鼠舒舒想要从土拨鼠团长处购买至少m个人类奴隶, 而人类奴隶是一车车的往回运输, 每一车有不同数量的人数$a_i$, 一共有$n$车. 为了方便, 团长要求舒舒必须整车的买入奴隶, 也可以连续的购买几车奴隶.

由于人类奴隶饭量很大, 舒舒希望尽量少的购买奴隶.

问舒舒最少可以购买多少奴隶?

# Format

## Input

第1行两个整数$n, m$
第2行$n$个整数$a_i$

## Output

第1行1个整数, 表示舒舒购买的奴隶个数.
第2行1个整数, 表示应该从第几车开始购买, 如果有多个选择, 则输出第一个选择.

如果无法购买到m个奴隶, 则直接输出-1;

# Samples

```input1
10 15
5 1 3 5 10 7 4 9 2 8
```

```output1
15
4
```

## 样例1解释

从第4车开始购买, 连续买两车, 可以购买得到15个人类奴隶

```input2
10 100
5 1 3 5 10 7 4 9 2 8
```

```output2
-1
```

# Limitation

1s, 1024KiB for each test case.



---

## O. 绝世好题

# Background

小 $Q$ 去爬山啦！

# Description

小 $Q$ 有两种方式爬山：

> 1.`爬` 从一个山峰爬到相邻山峰，花费 $\max(0, h_i - h_j)$。
> 
> 2.`瞬移` 移到任意一个山峰，花费 $P$

小 $Q$ 想知道他从 $1$ 号山峰开始经过 $n$ 个山峰所需要的最小体力。

# Format

## Input

第一行两个整数 $n, P$。
然后 $n$ 个数字，代表山峰的高度 $h_i$。

## Output

一行，代表答案

# Samples

```input1
6 5
100 1 3 0 10 100
```

```output1
7
```

# Limitation

$2 \le n \le 5 \times 10^5$

$0 \le P \le 10^{10}$

$0 \le h_i \le 10^{20}$

保证答案不超 `long long`。



---

## P. 123

# Background
Special for beginners, ^_^

# Description
Given two integers x and y, print the sum.

# Format

## Input
Two integers x and y, satisfying $0\leq x,y\leq 32767$ .

## Output
One integer, the sum of x and y.

# Samples

```input1
123 500
```

```output1
623
```

# Limitation
1s, 1024KiB for each test case.

---

## Q. 打印三角形(有数据，20个!)

# 背景

老土要去参加一年一度的土拨鼠国际三角形选美大赛，他想请你帮忙编一个程序，打印美观的三角形。

# 说明

* 配合样例看！！
* 一共有4种三角形
* 第0种：必须全部由'*'组成的三角形
* 第1种：每行都是由一个 '#'，一个 '*'，依次排列组成的三角形，第一行必须是 '#'
* 第2种：一行 '*'，一行 '#' 组成的三角形，最后一行必须是 '#'
* 第3种：一列 '*'，一列 '#' 组成的三角形，最后一列必须是 '#'

# Format

## Input

两个数，n，q；n表示三角形的大小（即行数），q表示打印第q种三角形

## Output

第q种，大小（行数）为n的三角形

# Samples

```input1
4 0
```

```output1
      *
    * * *
  * * * * *
* * * * * * *
```

```input2
4 1
```

```output2
      #
    # * #
  # * # * #
# * # * # * #
```

```input3
4 2
```

```output3
      *
    # # #
  * * * * *
# # # # # # #
```

```input4
5 2
```

```output4
        #
      * * *
    # # # # #
  * * * * * * *
# # # # # # # # #
```

```input5
4 3
```

```output5
      *
    # * #
  * # * # *
# * # * # * #
```

```input6
5 3
```

```output6
        #
      * # *
    # * # * #
  * # * # * # *
# * # * # * # * #
```

# Limitation

n<=100   q是0~3的整数



---

## R. 幻想乡 Wi-Fi 搭建计划


## 题目描述

傲娇少女幽香是一个很萌很萌的妹子。随着科技的进步，幻想乡的大家也开始使用手机了。这时幽香发现没人来她的太阳花田玩了，她感到很伤心，于是向别人打听了一下，才知道原来大家都嫌弃这里没有 Wi-Fi，手机上网还需要流量。

怎么办呢？幽香决定赶快搭建几个 Wi-Fi 点，让所有人都能在太阳花田里畅快地上网。

我们可以近似地把太阳花田看成一个 $y$ 轴在 $[0,R]$ 之间，$x$ 坐标在 $(-\infty,+\infty)$（也就是在 $x$ 轴上无限延伸）的无限长方形。

太阳花田里面有 $n$ 个景点，是游客们经常光顾的，幽香认为只要让这些景点尽量被 Wi-Fi 覆盖，那么游客们就肯定心满意足了。

八云紫表示她可以帮幽香架设 Wi-Fi 路由器。现在通用的路由器，每个的覆盖半径正好也是 $R$。八云紫扫视了一遍地图，发现在太阳花田外面，只有 $m$ 个有网络的地点，她只可以在那里架设路由器。如果你在点 $p$ 搭建了路由器，那么位于 $q$ 的地点，只要 $p$ 和 $q$ 的欧几里得距离小于等于 $R$，$q$ 点就会被 Wi-Fi 覆盖。

同时八云紫表示，架设难度随着地点的不同而不同，所以收费也不一样，在第 $i$ 个位置架设需要 $c_i$ 的钱。

现在幽香想要覆盖尽量多的景点，在这个前提下，幽香也想要尽量节省钱。你能帮助她吗？

## 输入格式

输入第一行三个整数 $n,m,R$，分别表示景点的数量，网络架设地点的数量和太阳花田的宽度。

接下来 $n$ 行，每行两个整数 $x,y$，满足 $|x|\le 10^8,0\le y\le R$，表示一个景点。两个景点的位置不会重合。

接下来 $m$ 行，每行三个整数 $x,y,c$，满足 $|x|\le 10^9$，$-10^8\lt y\lt 0$ 或者 $R\lt y\lt 10^8$，表示一个网络架设点的位置和花费。两个网络架设点不会重合。

## 输出格式

输出第一行表示最多覆盖的景点数。

第二行表示在覆盖景点数最多的前提下，最少的花费。

## 样例 #1

### 样例输入 #1

```
10 10 10000
6743 2963
3505 1986
3565 7235
1735 5522
16877 5597
11621 6
3100 8243
1750 6173
5709 7671
7915 3915
14339 -438 3075
4278 15210 8371
13996 19000 6750
17049 -4969 7788
737 16339 2934
904 14023 2322
8982 14759 4311
13102 11458 5554
4135 12183 576
5087 -2459 6787
```

### 样例输出 #1

```
10
10438
```

## 提示

- 对于 $10\%$ 的数据，$n,m\le 20$；
- 对于另 $30\%$ 的数据，$n,m\le 100$，所有网络架设点的 $y$ 坐标都大于 $R$；
- 对于另 $60\%$ 的数据，$n,m\le 100$。

对于全部数据，$1\le R\le 10^8,0\le c\le 10^4$。



---

## S. 土拨鼠的幸运数字1

## 题面翻译

【题目描述】愚蠢的土拨鼠喜欢数字，他将4和7视为幸运数字。如果一个数能由4与7组成，它就是幸运数字，只要能被幸运数字整除的也算幸运数字！现给定一个数字，判断它是否是幸运数。
【输入格式】一个整数n(1<=n<=1000000)
【输出格式】若n是幸运数或接近幸运数，输出“YES”；否则输出“NO”。（“”不用输出）

## Samples

```input1
47
```

```output1
YES
```

```input2
16
```

```output2
YES
```

```input3
78
```

```output3
NO
```


---