The 2023 Zhejiang SCI-TECH University Freshman Programming Contest
A. Locked Calculator
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

一个计算器上有 $$$0,1,2,3,4,5,6,7,8,9,+,-,\times,\div,=$$$ 这十五个按键。

现在所有的按键都被锁上了，给你一个非负整数 $$$n$$$ ，请问最少需要激活几个按键才能够打出这个数？

被激活的按键可以使用任意次。

Input

输入第一行包含一个整数 $$$T$$$ $$$(1\le{T}\le{10^3})$$$ ，代表测试组数。

随后 $$$T$$$ 行，每行包含一个非负整数 $$$n$$$ $$$(0\le{n}\le{10^{9}})$$$ 。

Output

输出 $$$T$$$ 行，代表第 $$$i$$$ 个测试点最少需要的按键数。

Example
Input
3
0
123
1296
Output
1
3
3
Note

对于 $$$0$$$ ，可以直接使用按键 $$$0$$$ 打出。

对于 $$$123$$$ ，可以直接使用按键 $$$1,2,3$$$ 打出。

对于 $$$1296$$$ ，可以使用按键 $$$6$$$ 和按键 $$$\times$$$ 打出 $$$6\times{6}\times 6\times 6$$$ ，再使用按键 $$$=$$$ 得到 $$$1296$$$ 。

B. おはよう 学弟
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

小 A 和小 B 正在玩一个游戏，游戏规则如下：

盒子中初始有 $$$n$$$ 个小球，两人轮流从中取出小球。若在当前回合开始时，有 $$$a$$$ 个小球，令 $$$a$$$ 在十进制表示下每位数字和为 $$$x$$$ ，则当前回合的玩家可以取出小球的个数在 $$$1$$$ 到 $$$\text{min}(a,x)$$$ 之间。若当前回合的玩家进行操作后盒为空，则此玩家胜利。

例如，当前盒中有 $$$365$$$ 个小球，则能够被取出 $$$1$$$ 到 $$$14$$$ $$$(14=3+6+5)$$$ 之间个数的小球。

由于比赛的奖品是印有 "おはよう学妹" 字样的限量款 T 恤，小 A 和小 B 非常想赢得这场比赛，所以他们都会做出对自己最优的操作。

现给出盒中初始小球的个数 $$$n$$$ ，请你预测谁能赢下这场惊险的比赛，小 A 先手进行操作。

Input

输入第一行包含一个正整数 $$$T$$$ $$$(1\le{T}\le{10^6})$$$，代表测试组数。

随后 $$$T$$$ 行，每行包含一个正整数 $$$n$$$ $$$(1\le{n}\le{10^6})$$$ ，代表盒中初始的小球个数。

Output

输出 $$$T$$$ 行，其中第 $$$i$$$ 行代表第 $$$i$$$ 个测试的胜方，如果是小 A 则输出 A ，如果是小 B 胜出则输出 B 。

Example
Input
2
1331
70
Output
A
B

C. おはよう 学妹
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定两个长度为 $$$n$$$ 的数组 $$$a,b$$$，一个正整数 $$$k$$$ ，确保 $$$k$$$ 的最大质因子大小不超过 $$$10^6$$$ 。

请问有多少个二元组 $$$(i,j),1\le{i,j}\le{n}$$$ 满足 $$$\text{lcm}(a_i,b_j)=k$$$ ？

其中 $$$\text{lcm}(x,y)$$$ 代表的是 $$$x$$$ 和 $$$y$$$ 的最小公倍数。

Input

输入第一行包含一个正整数 $$$T$$$ $$$(1\le{T}\le{10})$$$ ，代表测试组数。

对于每组测试第一行包含两个正整数 $$$n,k$$$ $$$(1\le{n}\le{10^6},1\le{k}\le{10^{18}})$$$ ，其中 $$$n$$$ 代表 $$$a,b$$$ 数组大小，确保 $$$k$$$ 的最大质因子大小不超过 $$$10^6$$$ 。

第二行包含 $$$n$$$ 个正整数 $$$a_1,a_2,...,a_n$$$ $$$(1\le{a_i}\le{10^{18}})$$$ ，代表 $$$a$$$ 数组。

第三行包含 $$$n$$$ 个正整数 $$$b_1,b_2,...,b_n$$$ $$$(1\le{b_i}\le{10^{18}})$$$ ，代表 $$$b$$$ 数组。

确保 $$$\sum{n}\le{10^6}$$$ 。

Output

输出 $$$T$$$ 行，每行包含一个整数代表二元组的数量。

Example
Input
1
2 6
2 2
3 3
Output
4

D. LR SORT
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

定义 LR SORT 为对一个大小为 $$$n$$$ 的数组 $$$a$$$ 进行 LR SORT 时，从 $$$1$$$ 到 $$$n$$$ 遍历 $$$a_i$$$，每当 $$$i$$$ 为奇数时，将 $$$a_i$$$ 移动至数组 $$$b$$$ 的最左侧，当 $$$i$$$ 为偶数时，将 $$$a_i$$$ 移动至数组 $$$b$$$ 的最右侧，数组 $$$b$$$ 初始为空，代表排序后的数组。

如对于数组 $$$a=[3,1,4,5,2]$$$ ，数组 $$$b$$$ 在排序过程中依次序为 $$$[3]$$$ , $$$[3,1]$$$ , $$$[4,3,1]$$$, $$$[4,3,1,5]$$$, $$$[2,4,3,1,5]$$$ 。

请构造一个大小为 $$$n$$$ 的排列 $$$p$$$ ，使得经过 LR SORT 后其严格上升，即不存在 $$$i$$$ 满足 $$$p_i\ge{p_{i+1}}$$$ 。

一个大小为 $$$n$$$ 的排列指的是一个数组的大小为 $$$n$$$ 且元素 $$$1 \sim n$$$ 都恰好出现一次。

Input

输入第一行包含一个正整数 $$$T$$$ $$$(1\le{T}\le{10^3})$$$ ，代表测试组数。

随后 $$$T$$$ 行，每行包含一个正整数 $$$n$$$ $$$(1\le{n}\le{10^5})$$$ 。

确保 $$$\sum n\le{2\times{10^5}}$$$ 。

Output

输出 $$$T$$$ 行，每行包含一个大小为对应测试点 $$$n$$$ 的排列。

Example
Input
2
1
3
Output
1 
2 3 1

E. 我要打 k 个
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个长为 $$$n$$$ 的数组 $$$a$$$ ，你当前拥有 $$$m$$$ 能量，你能做两种操作：

  1. 在 $$$a$$$ 数组中选择一个元素 $$$a_i$$$ 删除它，随后 $$$a_{i-1}$$$ 和 $$$a_{i+1}$$$ 变为相邻元素，这将花费 $$$a_i$$$ 能量;
  2. 选择数组 $$$a$$$ 中连续的 $$$k$$$ 个元素 $$$a_i,a_{i+1},a_{i+2},...,a_{i+k-1}$$$ 并删除，删除后 $$$a_{i-1}$$$ 和 $$$a_{i+k}$$$ 变为相邻元素；数组元素不足 $$$k$$$ 个则不能进行该操作，这个操作将花费 $$$x$$$ 能量。

若要删除的元素 $$$a_{i}$$$ 为数组唯一元素，则删除后数组为空。

若数组大小大于 $$$1$$$ 且 $$$a_i$$$ 位于数组最左侧，则删除后最左侧元素变为 $$$a_{i+1}$$$ 。

若数组大小大于 $$$1$$$ 且 $$$a_i$$$ 位于数组最右侧，则删除后最右侧元素变为 $$$a_{i-1}$$$ 。

你的剩余能量应当始终是非负的，请问你最多能删除几个 $$$a$$$ 数组中的元素？

Input

输入第一行包含四个正整数 $$$n,m,k,x$$$ $$$(1\le{k}\le{n}\le{2\times10^5},1\le{m,x}\le{10^9})$$$ ，分别代表 $$$a$$$ 数组初始元素个数，初始能量的大小，$$$k$$$ 和 $$$x$$$ 的含义见题目描述。

第二行包含 $$$n$$$ 个正整数 $$$a_1,a_2,...,a_n$$$ $$$(1\le{a_i}\le{10^9})$$$ ，代表 $$$a$$$ 数组。

Output

输出一个整数代表最多能删除的元素个数，

Example
Input
5 12 2 6
6 4 1 5 9
Output
4
Note

对于样例，你可先使用一操作删除 $$$a_{3}=1$$$ ，花费 $$$1$$$ ，随后数组变为 $$$\{6,4,5,9\}$$$ ，然后再使用一次二操作删除 $$$a_{1}=6,a_{2}=4$$$ ，花费 $$$x=6$$$ ，随后数组变为 $$$\{5,9\}$$$ ，然后使用一次一操作删除 $$$a_{1}=5$$$ ，随后数组变为 $$$\{9\}$$$ ，花费 $$$5$$$ 。

F. 舌切雀（Easy Version）
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

这是该问题的 Easy 版本，它与 Hard 版本的唯一区别是在本题中 $$$n\le{10^{12}}$$$ 。

令 $$$f(x) = \begin{cases} 0 &\text{if }\forall k(k\in{\mathbb{N}\land k \gt 1})\to x^{\frac{1}{k}}\notin {\mathbb{Q}} \\ 1 &\text{if } \exists k(k\in{\mathbb{N}\land k \gt 1})\to x^{\frac{1}{k}}\in {\mathbb{Q}} \end{cases}$$$

求 $$$ \sum_{i=1}^{n} f(i) $$$。

其中 $$$\mathbb{N}$$$ 代表自然数集， $$$\mathbb{Q}$$$ 代表有理数集。

Input

输入一个正整数 $$$T$$$ $$$(1\le{T}\le{2\times{10^3}})$$$ ，代表测试组数。

随后 $$$T$$$ 行，每行包含一个正整数 $$$n$$$ $$$(1\le{n\le{10^{12}}})$$$ 。

Output

输出 $$$T$$$ 行，每行包含一个整数代表答案。

Example
Input
2
5
13
Output
2
4

G. 舌切雀（Hard Version）
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

这是该问题的 Hard 版本，它与 Easy 版本的唯一区别是在本题中 $$$n\le{10^{18}}$$$ 。

令 $$$f(x) = \begin{cases} 0 &\text{if }\forall k(k\in{\mathbb{N}\land k \gt 1})\to x^{\frac{1}{k}}\notin {\mathbb{Q}} \\ 1 &\text{if } \exists k(k\in{\mathbb{N}\land k \gt 1})\to x^{\frac{1}{k}}\in {\mathbb{Q}} \end{cases}$$$

求 $$$ \sum_{i=1}^{n} f(i) $$$。

其中 $$$\mathbb{N}$$$ 代表自然数集， $$$\mathbb{Q}$$$ 代表有理数集。

Input

输入一个正整数 $$$T$$$ $$$(1\le{T}\le{2\times{10^3}})$$$ ，代表测试组数。

随后 $$$T$$$ 行，每行包含一个正整数 $$$n$$$ $$$(1\le{n\le{10^{18}}})$$$ 。

Output

输出 $$$T$$$ 行，每行包含一个整数代表答案。

Example
Input
2
5
13
Output
2
4

H. Sterling
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

定义操作为对于长为 $$$4$$$ 的子串删除第二个和第三个字符。

询问是否可以通过若干操作（包括不操作）将字符串 $$$s$$$ 变为字符串 $$$t$$$ 。

子串指的是字符串中连续的子序列，例如对于字符串 $$$s_{1}=\text{sdfsfee}$$$ ,字符串 $$$s_{2}=\text{s},s_{3}=\text{dfs},s_{4}=\text{sdfsfee}$$$ 都是它的子串，其中 $$$s_{5}=\text{sdfs},s_{6}=\text{dfsf},s_{7}=\text{fsfe},s_{8}=\text{sfee}$$$ 是 $$$s_{1}$$$ 所有的长为 $$$4$$$ 的子串。

Input

第一行输入包含一个正整数 $$$T$$$ $$$(1\le{T}\le{10^5})$$$ ，代表测试组数。

对于每组测试数据包含两行输入，第一行为一个仅包含小写字母的字符串 $$$s$$$ ，第二行为一个仅包含小写字母的字符串 $$$t$$$ 。$$$(1\le|t|\le|s|\le{10^5})$$$

确保 $$$\sum(|t|+|s|)\le{2\times{10^5}}$$$ 。

Output

对于每个测试数据，如果 $$$s$$$ 能通过若干次操作变为 $$$t$$$ ，输出 YES ，反之则输出 NO 。

Example
Input
3
yxsz
yz
jaabfabba
jaaaa
acakbba
acakb
Output
YES
YES
NO

I. A = B
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个等式，两侧各包含一个整数，等式右侧代表左侧对某个整数数据类型强制类型转换的结果，等式左侧的数的数据类型为 int 。

数据类型是未知的，可能是有符号也可能无符号，MAX也不确定；若存在合法的方案，则输出其中任意一个的类型及其 MAX ，否则输出 $$$-1$$$ 。

对于一个数据类型，在其溢出时，会向其取值范围另一侧移动对应的溢出值，如对于 int 类型，INT_MAX+1=-INT_MAX-1; 对于 unsigned int 类型，UINT_MAX+1=0 。

INT 类型为有符号整数类型，其 MAX 为 $$$2^{31}-1$$$ 。

Input

输入第一行包含一个正整数 $$$T$$$ $$$(1\le{T}\le{10^5})$$$ ，代表测试组数。

随后 $$$T$$$ 行，每行包含一个等式，两侧各包含一个整数 $$$x_i,y_i$$$ $$$(-2^{31}\le{x_i,y_i}\le{2^{31}-1})$$$ 。

Output

输出 $$$T$$$ 行，对于每个测试点，如果没有答案，输出 $$$-1$$$ 。

如果有答案，如果为有符号整数类型，输出 signed ，如果为无符号整数类型，输出 unsigned ，随后输出该数据类型的 MAX，MAX 应为一个不大于 $$$10^{18}$$$ 的 非负整数。

注意：请不要输出多余的空格，输出每个测试点的答案后请输出一个换行。

Example
Input
5
6 = 1
-3 = 5
4 = -4
-5 = 3
0 = 1
Output
unsigned 4
unsigned 7
signed 3
signed 3
-1
Note

对于无符号数据类型的，其范围为 [0,MAX] 。

对于有符号数据类型的，其范围为 [-MAX-1,MAX] 。

J. Devil's Recitation Ⅰ
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个高为 $$$n$$$ 的形如下图的图形 (下图 $$$n=4$$$)

$$$n=4$$$.

其中最后一行仅包含一个矩形，随后每向上一行都会在两侧多出两个矩形，最后一行的那个矩形下方是出口。

你可以在第一行的任意一个矩形中放入一颗小球，小球会径直向下抵达到下一行，小球在抵达某一行的最左侧时会向右一格，抵达某一行的最右侧时会向左一格，抵达最后一行时会继续向下抵达出口。

除此之外，还存在 $$$m$$$ 个矩形内存在一个小洞，小球抵达存在小洞的矩形时会直接消失。

请问从第一行的哪些矩形放入小球能使小球从出口离开？

Input

输出第一行包含正整数 $$$T$$$ $$$(1\le{T}\le{10^4})$$$ ，代表测试组数。

对于每组测试： 第一行包含两个整数 $$$n,m$$$ $$$(1\le{n}\le{{10^5}},0\le{m}\le{\min(n^2,2\times{10^5})})$$$ ，分别代表图形的深度和存在小洞的矩形个数。

随后 $$$m$$$ 行每行包含两个正整数 $$$r_i,c_i$$$ $$$(1\le{r_i}\le{n},1\le{c_i}\le{2\times{(n-r_i)}+1})$$$ ，代表第 $$$r_i$$$ 行第 $$$c_i$$$ 个矩形有小洞，确保小洞的位置两两不同。

确保 $$$\sum n\le{10^5},\sum m\le{2\times{10^5}}$$$ 。

Output

输出 $$$T$$$ 行，对于每个测试，输出一个长为 $$$2n-1$$$ 的 $$$01$$$ 字符串，其中第 $$$i$$$ 个字符为 $$$1$$$ 则代表第一行第 $$$i$$$ 个矩形放下小球后能到达出口，反之则代表不能。

Example
Input
1
4 3
2 1
1 5
3 3
Output
0011000

K. Devil's Recitation Ⅱ
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个高为 $$$n$$$ 的形如下图的图形 (下图 $$$n=4$$$)

$$$n=4$$$.

其中最后一行仅包含一个矩形，随后每向上一行都会在两侧多出两个矩形，最后一行的那个矩形下方是出口。

你可以在第一行的任意一个矩形中放入一颗小球，小球会径直向下抵达到下一行，小球在抵达某一行的最左侧时会向右一格，抵达某一行的最右侧时会向左一格，抵达最后一行时会继续向下抵达出口。

除此之外，还存在 $$$m$$$ 个矩形内存在一个传送带，小球抵达存在传送带的矩形时会沿着传送带的方向向左或右移动一个矩形的距离（确保传送带不在每行的最左侧和最右侧）。

请问从第一行的哪些矩形放入小球能使小球从出口离开？

Input

输出第一行包含正整数 $$$T$$$ $$$(1\le{T}\le{10^4})$$$ ，代表测试组数。

对于每组测试： 第一行包含两个整数 $$$n,m$$$ $$$(1\le{n}\le{{10^5}},0\le{m}\le{\min((n-1)^2,2\times{10^5})})$$$ ，分别代表图形的深度和存在传送带的矩形个数。

随后 $$$m$$$ 行每行包含两个正整数和一个字符 $$$r_i,c_i,d_i$$$ $$$(1\le{r_i}\le{n-1},2\le{c_i}\le{2\times{(n-r_i)}},d_i\in{(L,R)})$$$ ，代表第 $$$r_i$$$ 行第 $$$c_i$$$ 个矩形有传送带，$$$d_i=L$$$ 代表方向向左，$$$d_i=R$$$ 代表方向向右，确保有传送带的矩形的位置两两不同。

确保 $$$\sum n\le{10^5},\sum m\le{2\times{10^5}}$$$ 。

Output

输出 $$$T$$$ 行，对于每个测试，输出一个长为 $$$2n-1$$$ 的 $$$01$$$ 字符串，其中第 $$$i$$$ 个字符为 $$$1$$$ 则代表第一行第 $$$i$$$ 个矩形放下小球后能到达出口，反之则代表不能。

Example
Input
1
4 3
2 2 L
1 6 R
1 2 R
Output
0001100

L. 兀突骨之死
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

兀突骨正在参加一场紧张刺激的三国杀战斗，战斗共有 $$$n$$$ 个回合。

战火燃尽英雄胆！

兀突骨的初始生命值为 $$$x$$$，当兀突骨的生命值小于等于 $$$0$$$ 时兀突骨死亡。在每个回合结束时，兀突骨会受到一次 "燃殇" 伤害，初始时燃殇伤害为 $$$0$$$。每当兀突骨受到火焰伤害时，燃殇伤害就会增加一点。

现给出一个长为 $$$n$$$ 的序列 $$$a$$$，表示兀突骨在第 $$$i$$$ 个回合是否会受到一点火焰伤害。$$$a_i$$$ 为 $$$1$$$ 时表示会受到一点火焰伤害，$$$a_i$$$ 为 $$$0$$$ 时表示不会受到火焰伤害。

请问兀突骨在 $$$n$$$ 个回合内是否会死亡。如果会，请输出 YES，然后输出兀突骨死亡的回合；如果不会，请输出 NO。

Input

输入第一行，包含两个正整数 $$$n,x$$$ $$$(1\le{n}\le{10^6},1\le{x}\le{10^9})$$$，表示战斗的回合数与兀突骨的初始生命值。

第二行包含 $$$n$$$ 个整数 $$$a_i$$$ $$$(0\le{a_i}\le{1})$$$，表示第 $$$i$$$ 个回合兀突骨是否会受到一点火焰伤害。

Output

如果兀突骨在 $$$n$$$ 个回合内死亡，请输出 YES，然后输出兀突骨会在哪一个回合死亡。如果不会，请输出 NO。

Examples
Input
3 3
0 1 0
Output
YES
3
Input
3 3
0 0 1
Output
NO

M. 渚千夏的串
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

我们定义一个 $$$01$$$ 串的权值，是其子序列为 $$$01$$$ 的个数。

先给定权值 $$$m$$$ ，试构造一个合法的 $$$01$$$ 串使其权值为 $$$m$$$ 且长度在 $$$10^5$$$ 以内。

$$$01$$$ 串即字符集仅包含 $$$0,1$$$ 的字符串。

注意:序列 $$$a$$$ 是字符串 $$$b$$$ 的子序列，当且仅当 $$$a$$$ 可以通过删除 $$$b$$$ 中的若干(可能为零或全部)元素得到。例如：对于串 $$$01011$$$，字符串 $$$1011,111$$$ 都是它的子序列。

Input

输入包含一个正整数 $$$m$$$ $$$(0\le{m} \le{10^9})$$$ ，代表 $$$01$$$ 子序列的个数。

输入数据保证有解。

Output

输出第一行，包含一个正整数 $$$n$$$ $$$(1\le{n\le{10^5}})$$$，表示 $$$01$$$ 串的长度。

输出第二行，包含一个 $$$01$$$ 串，长度不超过 $$$10^5$$$。

Examples
Input
2
Output
3
001
Input
5
Output
6
010001

N. 桂林精八件
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$\text{ff}$$$ 从桂林带回来了一些特产，我们称它们为桂林精八件。顾名思义，桂明精八件共有八种不同的物品，第 $$$i$$$ 种物品最开始有 $$$a_i$$$ 个。

桂林精八件.

现在有 $$$n$$$ 个人想要得到桂林精八件中的其中一个物品，第 $$$i$$$ 个人想要的物品为 $$$b_i$$$。请问 $$$n$$$ 个人中有多少人可以获得自己想要的物品。

Input

输入第一行包含一个正整数 $$$n(1\le{n}\le{2\times{10^5}})$$$，表示人的数量。

第二行包含 $$$n$$$ 个正整数 $$$b_i(1\le{b_i}\le{8})$$$，表示第 $$$i$$$ 个人想要的物品的种类。

第三行包含八个正整数 $$$a_i(0\le{a_i}\le{2\times{10^5}})$$$，表示桂林精八件的数量。

Output

输出一行，包含一个整数表示答案。

Example
Input
5
1 1 1 2 3
2 1 0 1 1 0 0 0
Output
3