YLT C++ 3级 2024.12

N3133 [CIE 202412 三级 T1] 最近的斐波那契数

题目描述

斐波那契数列 $F_n$ 的定义为：对 $n \ge 0$ 有 $F_{n+2} = F_{n+1} + F_n$，初始值为 $F_0 = 0$ 和 $F_1 = 1$。所谓与给定的整数 $N$ 最近的斐波那契数是指与 $N$ 的差之绝对值最小的斐波那契数。本题就请你为任意给定的整数 $N$ 找出与之最近的斐波那契数。

输入格式

输入在一行中给出一个正整数 $N(\le 10^8)$。

输出格式

在一行输出与 $N$ 最近的斐波那契数。如果解不唯一，输出最小的那个数。

样例

样例 1
输入：

305

输出：

233

提示

样例解释：部分斐波那契数列为 $\{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, \ldots \}$。可见 $233$ 是与 $305$ 最近的斐波那契数。

N3134 [CIE 202412 三级 T2] 构造性证明

题目描述

关于数学定理证明，也有高下之分。最暴力的证明方法是“构造性证明”，即当需要证明某种解存在时，直接把解构造出来，而不是仅通过推理证明解之存在。
下面有一个定理：
设 $a_i$（$i=1, \ldots, 5$）均为正实数。则一定存在 $4$ 个互不相同的下标 $i$、$j$、$k$、$l$，使得 $|a_i / a_j - a_k / a_l| < 1/2$。
作为程序员，就请你编写程序构造出正确的下标，验证这个结论。

输入格式

输入在一行中顺序给出 $5$ 个正实数。为保证计算中不产生浮点溢出，我们令输入的数字在 $[10^{-10}, 10^{10}]$ 区间内，且小数点后不超过 $10$ 位小数。

输出格式

在一行中首先输出使得定理结论成立的下标有多少套，随后输出最小的一套下标。数字间以 $1$ 个空格分隔，行首尾不得有多余空格。注：所谓下标集 $\{i_1, \ldots, i_4\}$ 小于下标集 $\{j_1, \ldots, j_4\}$，是指存在 $1 \le k \le 4$ 使得 $i_l = j_l$ 对所有 $l < k$ 成立，且 $i_k < j_k$。

样例

样例 1
输入：

3.12 5.27 0.0007 9825.4413 10

输出：

18 1 4 3 2

提示

样例解释：易验证 $|a_1 / a_4 - a_3 / a_2| = |3.12 / 9825.4413 - 0.0007 / 5.27| < 1/2$。
满足条件的解有 $18$ 个，例如 $5$、$4$、$3$、$2$ 就是另一套解。

N3135 [CIE 202412 三级 T3] 环形公路出口

题目描述

一条环形高速路上有 $N$ 个出口。给定任意一对出口，请你算出这两个出口之间的最短距离。

输入格式

输入第一行给出区间 $[3, 10^5]$ 内的整数 $N$，以及 $N$ 个整数距离 $D_1$ $D_2$ $\ldots$ $D_N$，其中 $D_i$ 是第 $i$ 和第 $i+1$ 个出口之间的距离，$D_N$ 是第 $N$ 和第 $1$ 个出口之间的距离。同行数字间以空格分隔。
第二行给出正整数 $M$（$\le 10^4$）。
随后 $M$ 行，每行给出一对出口的编号（出口从 $1$ 到 $N$ 顺序编号）。
题目保证公路全长不超过 $10^7$。

输出格式

输出 $M$ 行，每行给出对应输入的一对出口之间的最短距离。

样例

样例 1
输入：

5 1 2 4 14 9
3
1 3
2 5
4 1

输出：

3
10
7

N3136 [CIE 202412 三级 T4] 子串和子列

题目描述

子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt 是一个子串，而 pat 就是一个子列。
现给定一个字符串 $S$ 和一个子列 $P$，本题就请你找到 $S$ 中包含 $P$ 的最短子串。若解不唯一，则输出起点最靠左边的解。

输入格式

输入在第一行中给出字符串 $S$，第二行给出 $P$。$S$ 非空，由不超过 $10^4$ 个小写英文字母组成；$P$ 保证是 $S$ 的一个非空子列。

输出格式

在一行中输出 $S$ 中包含 $P$ 的最短子串。若解不唯一，则输出起点最靠左边的解。

样例

样例 1
输入：

atpaaabpabttpcat
pat

输出：

pabt

N3137 [CIE 202412 三级 T5] 拼大数

题目描述

如何随机生成一个有 $n$ 位数的大数呢？一种方法是，找到 $n$ 个小朋友，每人发一张卡片，卡片一面写着编号（这里假设小朋友们从 $1$ 到 $n$ 编号），另一面让他们随便写下一个 $1$ 位数字。然后让小朋友们把自己的卡片在墙上钉成一排，要求一张挨着一张，按他们的编号升序排列，显示他们自己写的数字。
但是，让十万个孩子都按指令行动，可太难了。结果是卡片乱七八糟满墙都是，有些甚至显示的不是正确的面。例如第 $23$ 号小朋友在卡片上写了 $8$，我们应该在墙上看到 $8$，但是却看到了 $23$…… 你的任务就是把这些卡片整理好，得到我们真想要拼成的大数。

输入格式

输入第一行给出一个正整数 $n$（$\le 10^5$），随后 $n$ 行，每行按 $n_1\ n_2$ 的格式给出一张卡片两面的数字。

输出格式

在一行中输出我们真想要拼成的 $n$ 位大数。如果卡片两面都是 $1$ 位数，那么就很难说哪个数字是编号，哪个数字是小朋友自己写的，所以解可能是不唯一的。这时候需要输出能得到的最小的数字。

样例

样例 1
输入：

12
7 11
8 9
3 1
2 12
4 6
10 0
5 1
2 5
6 8
1 4
7 2
9 3

输出：

359114268072