第一届 Hello World 程序设计竞赛题目

Hello_World

A. 逃脱游戏

分值：15 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：刘蒙蒙

题目描述

小明走在森林中，突然有一只大怪兽拦住他，大怪兽还是很仁慈的，只要小明答对了它的题，它就会放过小明。不过大怪兽只喜欢比 $3$ 小的自然数，大于 $3$ 的数它就会对 $3$ 取余得到比 $3$ 小的数。
它给小明三个数 $a$, $b$, $c$，只有选择对 $3$ 取余最大的那个才会放过小明。可小明数学不好，你可以帮他逃出去吗？

输入

输入包含三个自然数，$a$, $b$, $c$,含义如题。

输出

输出对 $3$ 取余最大的数，当取余结果相同时，输出第一个取余最大的数字。

样例

数据范围

对于 $20\%$ 的数据，$0\leq a,b,c\leq 10^5$
对于 $90\%$ 的数据，$0\leq a,b,c\leq 2^{64}-1$
对于 $100\%$ 的数据，$0\leq a,b,c\leq 10^{100}$

B. 卖火柴的小女孩（节选）

分值：15 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

小女孩又擦亮一根火柴，火光把四周照得通亮，奶奶在火光中出现了。奶奶朝着她微笑着，那么温柔，那么慈祥。
“奶奶——”小女孩激动得热泪盈眶，扑进了奶奶的怀抱，“奶奶，请把我带走吧，我知道，火柴一熄灭，您就会不见了！”
“我亲爱的孙女儿，奶奶不会离开你的。奶奶学会了一种膜法，只要你能用三根火柴拼出一个三角形，这三根火柴就永远不会熄灭！”
“真的吗？太好了！奶奶，我现在就可以拼出来。看！还是个三边相等、有三条对称轴的正三角形呢！”小女孩激动得手舞足蹈。
“傻孩子，膜法怎么会这么简单就能完成的呢，火柴的长度需要满足一定的条件，它们的长度都为整数，也必须在 $[l, r]$ 的区间内，且任意两条根火柴的长度不能相等。”
这可难倒小女孩了，你能帮她达成心愿吗？

输入

输入包含两个正整数，$l$, $r$，含义如题，其中 $1\leq l\leq r\leq 10^5$。

输出

如果小女孩的心愿能够达成，则输出 “YES”，并在第二行输出三个整数，表示答案，否则输出 “NO”。若有多种可能的答案，输出任意一种即可。

样例

C. 深井中的蜗牛

分值：15 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

一只蜗牛在一口深 $x$ 米的枯井井底，它每天白天向上爬 $a$ 米，晚上向下滑 $b$ 米。请问：蜗牛几天后能爬出枯井?

输入

输入包含三个正整数 $x$, $a$, $b$，含义如题，其中 $1\leq x,a,b\leq 100$。

输出

输出蜗牛将在第几天到达井口，若蜗牛永远都无法爬到井口，则输出 “impossible”。

样例

D. 修路工程

分值：25 分 | 时间限制：4 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

县政府想要在 $n$ 个两两互相不能到达的村子之间修建一些道路，使得这些村子能够相互到达。若村子 $a$ 能够到达村子 $b$，$b$ 与村子 $c$ 能够相互到达，则 $a$ 与 $c$ 也能相互到达。
每户村子的人口数为 $w_i$，如果想要在两个村子之间修建一条道路，就要先通知这两个村子的所有人。因此若要在村子 $u$ 与村子 $v$ 之间修建一条道路，就要通知 $w_u+w_v$ 个人，告知他们这条道路将通往的另一个村子。如果想要从 $u$ 村出发再修建一条通往 $t$ 村的道路，那么县政府仍然要通知 $w_u+w_t$ 个人。
现在县政府想要使得修建的道路至少能够使所有村子之间互相到达，应如何修建这些道路，使得通知的人口总数最少，为多少？

输入

第一行为一个整数 $n$，表示村子的数量，第二行有 $n$ 个整数，第 $i$ 个整数 $w_i$ 表示第 $i$ 个村子的人口数。

输出

输出在保证所有村子都能互相到达的情况下，最少需要通知的人口数。

样例

数据范围

对于 $20\%$ 的数据，$2\leq n\leq200$
对于 $70\%$ 的数据，$2\leq n\leq1000$
对于 $100\%$ 的数据，$2\leq n\leq10^6,1\leq w_i\leq10^5$

E. 算积分

分值：25 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：张梓祺

题目描述

$GBF$ 是个非常非常讨厌高数的人！她只要看到高数的题，就会头脑发晕，不知所措。（因为体积太大所以不会被水淹没）。
有一天她碰到一道这样的题，计算以下定积分：

$$\int_{a}^{b}(e^{-x^2} + \frac{\sin{x}}{x} + \frac{1}{\ln{x}} )\text{d}x$$
对于她这种高数渣来说，自然是不会做的。你能写个程序帮帮她吗？

输入

第一行一个整数 $T$，表示有 $T$ 组数据($T\leq100$)
每组每行有两个数 $a$, $b$。（$2<a<b<12$ 且 $b-a<2$，保证给的 $a$, $b$ 小数点后不超过 $2$ 位）。

输出

每行输出一个数表示答案，答案保留两位小数。

样例

提示

你需要头文件 math.h 提供一些函数：
1. double log (double) 以 e 为底的对数
2. double exp (double) 求取自然数 e 的幂
3. double sin (double) 计算正弦函数

F. 解密

分值：25 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：袁丞蕾

题目描述

$gzp$ 的朋友听说 $Hello~World$ 协会要举办比赛，就友情贡献了一个题目，但是为了保密，给文件设置了密码 $p$，并将密码 $p$ 加密后给了 $gzp$，加密后的密码是一个长度为 $n$ 的序列 $s$。
已知正确密码 $p$ 满足以下条件：

1. 正确的密码 $p$ 和加密后的密码 $s$ 都由 $1-n$ 组成，且每个数字都只出现一次（不会不出现也不会重复出现）；
2. 把所有满足条件 $1$ 的密码按字典序（字典序比较规则与 $strcmp$ 函数比较规则相同）排序，$p$ 的次序比 $s$ 大 $k$。

现在由你来完成解密工作。

输入

第一行为两个整数 $n$ 和 $k$，第二行包含 $n$ 个不同的正整数，表示加密后的密码序列 $s$，数据保证满足条件 $1$。($0\lt n\leq10^4,0\leq k\leq1000$)

输出

解密后的密码 $p$，如果不存在，输出 “impossible”。

样例

G. 一键复制粘贴

分值：30 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

$lx$ 想约 $wyz$ 一起去武大赏樱花，无奈 $wyz$ 的导师也正催着他交科研立项的开题报告，$lx$ 为了帮助 $wyz$ 尽早完成任务陪她赏樱，送给了 $wyz$ 一个神奇的 Ctrl 键，一旦点下这个 Ctrl 键，就会自动完成 “全选-复制-粘贴” 这三个动作，且只能用一次，例如 $wyz$ 已经敲出文本 “miao”，按下 Ctrl 键后，整个文本就会被复制一遍变为 “miaomiao”。
$wyz$ 已经计划好开题报告的所有内容，现在想要在这个 Ctrl 键的帮助下，尽快完成文本内容，问他最少需要敲几次键盘？（按下 Ctrl 键也算一次）

输入

一个只包含小写字母的字符串 $s$，表示 $wyz$ 将要输入的文本。

输出

输出 $wyz$ 最少需要敲几次键盘。

样例

数据范围

对于 $20\%$ 的数据，$1\leq\left|s\right|\leq100$
对于 $50\%$ 的数据，$1\leq\left|s\right|\leq1000$
对于 $100\%$ 的数据，$1\leq\left|s\right|\leq10^6$

H. 香槟酒

分值：30 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：官展鹏

题目描述

为了庆祝“第一届 $Hello~World$ 程序设计竞赛”圆满结束，活动台前幕后的工作人员们开了一场香槟酒会。
所有酒杯被摞成一个金字塔，接着由 $xzh$ 从最顶层的酒杯往下倒酒，如果顶层的酒杯被倒满了酒，多出来的酒就会溢出到第二层（向左右两边溢出的速率相等，如下图）。现在我们按照从上到下、从左到右的顺序对酒杯从 $1$ 开始编号，第 $i$ 层第 $j$ 个酒杯的编号为 $(i,j)$，例如顶层的酒杯编号为：$(1,1)$。
每一个酒杯的容积都相同，我们设为一个单位体积，问如果想要把酒杯 $(i,j)$ 装满，最少需要多少单位体积的香槟酒？

输入

输入为两个正整数 $a,b$，表示被询问的酒杯编号，其中 $1\leq b\leq a\leq30$。

输出

输出一个实数，表示至少需要向最顶端的酒杯倒多少单位体积的香槟，才能倒满酒杯 $(a,b)$。
如果你的输出与标准输出的绝对值不超过 $10^{-6}$，则认为你的程序是正确的。

样例

I. 送分题 A+B

分值：45 分 | 时间限制：1 s | 空间限制：262144 KB | 出题人：许子涵，官展鹏，孙昊哲

题目描述

$xzh$ 看了出题组出的题目后，觉得这些题目或多或少都有些难度，要是有人一道题都做不出来怎么办，为了良好的比赛体验，$xzh$ 决定加一道所有人都会做的题目。
虽然我们是 $Hello~World$ 社团，但是我们也不能单纯让大家输出 "Hello World" 吧，这样太侮辱大家的智商了，main 函数内的代码至少要有三四行吧。
$xzh$ 与 $gzp$ 经过一番激烈的讨论，$gzp$ 与 $shz$ 又经过一番激烈的讨论后，我们最终决定出这样一道题目：
这是我们出过的最简单的题目了，题目的要求非常简单，输入两个整数 $A$ 和 $B$，然后输出这两个整数的和与差，怎么样，非常简单吧！为了让大家能有保底分数，我们故意将这道题的分值设为了 45 分，简直就是送分题啊~~~

输入

输入只有一行，只有两个整数 $A$ 和 $B$，数据保证输入为数字的自然表示（若数字的值为 0，则输出 0，若小于零则带有负号。除零外，最高的数字位是一个非零数字，如 0、-31、500 是自然表示的数字，00、-031、-00 不是自然表示的数字）

输出

输出两个整数各占一行，第一行为 $A+B$ 的值，第二行为 $A-B$ 的值。
输出也必须为自然表示的数字。

样例

数据范围

对于 $10\%$ 的数据，$-18\times10^{18}\leq A,B\leq18\times10^{18}$
对于 $50\%$ 的数据，$A\times B>0$
对于 $100\%$ 的数据，$-10^{100000}\leq A,B\leq10^{100000}$