Tsawke's Exam Standard

注意事项

1. 所有文件名均保证为小写（友情提示：请格外注意文件名）。
2. C++ 中 main() 函数返回值必须为 int 且为 $0$$0$。
3. C++ 编译器开启 C++14 标准及 O2 优化。
4. 提交的程序源文件需独立文件夹。
5. 结果比较方式为全文比较（忽略行末空格及行尾回车）。
6. 程序可使用的栈空间限制与对应题目内存限制一致。
7. 评测采用机器配置为：11th Gen Intel(R) Core(TM) i5-11320H @ 3.20GHz。
8. 编译选项为：g++ -o sample sample.cpp -lm -Wl,--stack=2147483647 -std=c++14 -O2。
9. 对于本地 Linux 环境下调试时，可以添加编译选项：-fsanitize=undefined,signed-integer-overflow,address 以检测未定义行为、整数溢出，地址越界等问题。
10. 对于提答题请将 .out 为扩展名的文件统一放到子目录下。

Tsawke的学习资料（hddd）

题目背景

tsawke 电脑里的学习资料太多了，但他不舍得删除，于是他决定将其存到硬盘里，但是硬盘只有一种且容量有限，买硬盘的价格又很贵，tsawke 想知道至少需要多少块硬盘才可以将他的全部学习资料存下来。

Tips：每个学习资料不可被拆分。

题目描述

给出 tsawke 电脑里 $n$$n$ 个学习资料的文件大小 $s_i$$s_i$，并给出每个硬盘的容量 $m$$m$，求最少需要多少块硬盘。

Tips：这道题的做法非常多。

输入格式

第一行两个整数 $n,m$$n, m$。

接下来 $n$$n$ 行每行一个整数，第 $i$$i$ 行表示 $s_i$$s_i$。

输出格式

一行一个整数，表示最少需要的硬盘块数。

数据范围

对于 $10\mathrm{\%}$$10\%$ 的数据，满足 $1\le n,m\le 10,1\le s_i\le 10$$1 \le n, m \le 10, 1 \le s_i \le 10$。这部分分给的真足

对于 $100\mathrm{\%}$$100\%$ 的数据，满足 $1\le n\le 18,1\le m\le {10}^8,1\le s_i\le {10}^8$$1 \le n \le 18, 1 \le m \le 10^8, 1 \le s_i \le 10^8$，保证 $s_i\le m$$s_i \le m$。

Tips：数据不是很友好。

Examples

Input_1

xxxxxxxxxx
5
1
4 10 
2
5 
3
6 
4
3 
5
7 

Output_1

xxxxxxxxxx
1
1
3

又是SET（settttttt）

是的这道题寄掉了。

想出这道题，已经改完了，但是因为我自己写不出来 std 所以寄了。

于是这套题就变成了三道题。。。

所以这里再次强调一下这道题已经被删了

不过你们如果有时间也可以尝试去写个std

题目背景

在知名游戏 SET 中，存在着一些数字、形状、颜色等不同的卡片，玩家的目标是确定一个存在的 triplet of cards（即卡片的三元组，也就是三张卡片构成的组合），使其符合特定的要求。 Marin 和 Josip 很快就对这个游戏感到无趣，并对其进行了加强。

然而 tsawke 很快又对这个游戏感到了无趣，于是将这题变得更加毒瘤，我们的目标变为寻找一个存在的 multiplet of cards（即多元组）。

题目描述

在本题中，定义每张卡片代表着一个仅由 $1,2,\cdots ,k$$1, 2, \cdots, k$ 构成的长度为 $l$$l$ 的序列，共有 $n$$n$ 张卡片，卡片之间是无序的。 定义一个 SET 表示，当且仅当一个无序的 multiplet of cards 其中的 $k$$k$ 个序列的每一位均相同或各不相同，用原文中的话就是 same 或 pairwise different，更严谨地表示，我们令这多个序列为 $S_{n_1},S_{n_2},\cdots ,S_{n_k}$$S_{n_1}, S_{n_2}, \cdots, S_{n_k}$，则一定满足如下条件：

• $n_1<n_2<\cdots <n_k$$n_1 \lt n_2 \lt \cdots \lt n_k$
• $\mathrm{\forall }x\in [1,l]$$\forall x \in \left[1, l\right]$，满足 $S_{n_1}(x)=S_{n_2}(x)=\cdots =S_{n_k}(x)$$S_{n_1}(x) = S_{n_2}(x) = \cdots = S_{n_k}(x)$ 或 $S_{n_1}(x)\ne S_{n_2}(x)\ne \cdots \ne S_{n_k}(x)$$S_{n_1}(x) \neq S_{n_2}(x) \neq \cdots \neq S_{n_k}(x)$ 例如 $(1123,1322,1221,1424)$$(1123, 1322, 1221, 1424)$ 便满足 $1,3$$1, 3$ 位均相同，$2,4$$2,4$ 位各不相同。 给你这些序列，求可以组成多少种本质不同的 $\mathtt{\text{SET}}$$\texttt{SET}$。

输入格式

第一行为三个整数正整数 $n,l,k$$n, l, k$。

接下来 $n$$n$ 行中每一行包含一个仅由 $1,2,\cdots ,k$$1, 2, \cdots, k$ 构成的长度为 $l$$l$ 的序列，代表着一张卡片。 保证每张卡片上的序列不同。

输出格式

仅一行一个整数，表示可以组成的本质不同的 SET 的数量。

数据范围

对于全部数据，满足 $1\le l\le 8,l\le n,1\le n\le k^l,2\le k\le 9$$1 \le l \le 8, l \le n, 1 \le n \le k^l, 2 \le k \le 9$，$S_{n_i}$$S_{n_i}$ 互不相同且满足 $1\le S_{n_i}\le k$$1 \le S_{n_i} \le k$。

这tm也是传统题？？？（what_tht_fxxk）

什么骗分过样例

题目背景

众所周知，llq 的网站是很安全的。

tsawke 很想获得 llq 的网站 jdoi 中所有题目的 std 代码，但是 tsawke 学艺不精，尝试了很久也没能成功破解 llq 的服务器。

但是经过他的不懈努力，他通过找到的一个漏洞成功提升了自己的 WEBSHELL 权限，并尝试下载 llq 的数据库后删库跑路。

但是 llq 很快便发现了 tsawke 的行动，立刻线下物理阻止了 tsawke 的入侵，不过最终 tsawke 仍然下载到了 llq 网站中 $16$$16$ 道题的一个输入输出样例，而对于源代码，tsawke 虽然下载下来了，但是其中的内容却被狡猾的 llq 加密了，只剩下每个源代码残缺的文件名。

而为了通过这些信息来勒索 llq，tsawke 找到了你，为了机房的未来，你需要通过源文件文件名 + 输入样例 + 输出样例来推断出这道题需要实现的内容。

题目描述

Q & A

• Q：我的程序具体需要实现哪些功能？
• A：不知道。
• Q：那我怎么写？
• A：。。。

是的，你需要通过源文件文件名 + 输入样例 + 输出样例，来推断出每个文件具体要实现什么功能。

输入格式

第一行一个字符串表示需要实现程序的文件名。

接下来若干行根据不同程序的功能有不同的输入，详见下发的文件。

说明

关于文件

所有需要的文件已经下发到 /what_the_fxxk/。

Q & A again

• Q：这发的文件是啥？我要干什么？
• A：下发文件即为输入输出样例，下方还会有一个对于每个测试点的文件名。
• A：你要实现的功能就是在输入是对应的 .in 的时候输出对应的 .out。
• Q：那我直接打 $16$$16$ 个表？？？
• A：显然这是可以的，但是一般仅允许提交 100KiB 的文件，肯定打不完，不过还是可以得到一些部分分的。
• A：当然既然这道题被 tsawke 搬过来了，就不可能这么容易让你拿到 pts，你提交文件的大小被限制到了 10KiB。
• tsawke 最终决定将文件限制改回 100KiB。

程序文件名表

提示

Tips：这里的提示很有用！

在你使用 C/C++ 的 int 类型时，如果发生了溢出，比较可能的情况是按照模 $2^{32}$$2^{32}$ 同余的前提下，在 int 范围内取一个合理的值。例如在计算 $2147483647+2$$2147483647 + 2$ 时，就有可能会得到 $-2147483647$$-2147483647$。

然而，C/C++ 标准将这种情况归类为“未定义行为”。当你的程序试图计算会溢出的 int 运算时，除了上述结果外，编译器还可能会让你的程序在此时计算出错误结果、死循环、运行错误等，这也是符合 C/C++ 标准的。

如果你的程序希望利用 int 的自然溢出的特性，请转换为 unsigned 类型运算。例如将 a + b 改写为 (int) ((unsigned) a + (unsigned) b)，以避免出现不预期的错误。

提示again

Tips：源文件名也是很重要的依据！

如果看到这你还是很迷，不知道这道题到底在干什么，那么这里再详细解释一下。

你需要实现的和传统题形式上一样，仅为一个 .cpp 文件，在这个程序里你需要实现：

首先读入一个字符串代表着表格中的“源文件名称”，然后你便需要实现其对应序号的程序。

简而言之，就是你需要让输入为任意 .in 文件时，你的程序的输出为对应的 .out 文件。

文件均已下发到 Tsawke's Exam - Issue/what_the_fxxk/。

快打开GeoGebra（dddddddraw）

题目背景

当你不想检查前面的水题的时候，就可以开始考虑这道题了~

是的这是一道提答。

题目描述

tsawke 有若干个已知的几何图形，一天他心血来潮突然想要通过尺规作图来得到一个要求的点，但是他太弱了，于是找到了你来为他生成方案。

你可以进行如下两个操作：

1. 以一个已知点为圆心，另一个已知点为圆上一点作圆。
2. 连结任意两个已知点形成一条直线。

你需要输出你的作图步骤，来帮助 tsawke 解决他的困惑。

输入格式

第一行一个整数，表示测试点编号。

第二行一个整数 $n$$n$，表示已知点的数量。

接下来 $n$$n$ 行，第 $i$$i$ 行两个实数 $x_i,y_i$$x_i, y_i$，表示第 $i$$i$ 个点的坐标。

接下来一个整数 $n_1$$n_1$，表示已知线段的数量。

接下来 $n_1$$n_1$ 行，每一行两个整数 $u,v$$u, v$，表示有一条连接点 $u$$u$ 和点 $v$$v$ 的线段。

接下来一个整数 $n_2$$n_2$，表示已知直线的数量。

接下来 $n_2$$n_2$ 行，每一行两个整数 $u,v$$u, v$，表示有一条经过点 $u$$u$ 和点 $v$$v$ 的直线。

接下来一个整数 $n_3$$n_3$，表示已知圆的数量。

接下来 $n_3$$n_3$ 行，每一行两个整数 $u,v$$u, v$，表示有一个以点 $u$$u$ 为圆心，点 $v$$v$ 为圆上一点的圆。

接下来两个实数 $x,y$$x, y$，表示要求点的坐标。

接下来 $10$$10$ 个整数 $a_1$$a_1$ 到 $a_{10}$$a_{10}$，表示此测试点的评分参数，详见说明。

输出格式

第一行一个整数 $m$$m$，表示你需要的步数。

接下来 $m$$m$ 行描述你的作图步骤：

首先一个整数 $1$$1$ 或 $2$$2$，$1$$1$ 表示你要画一个圆，$2$$2$ 表示你要连一条直线。

接下来四个实数 $x_1,y_1,x_2,y_2$$x_1, y_1, x_2, y_2$：

如果你要画一个圆，表示你要以 $(x_1,y_1)$$(x_1,y_1)$ 为圆心，$(x_2,y_2$$(x_2,y_2$) 为圆上一点画圆；

如果你要连一条线，表示你要将 $(x_1,y_1)$$(x_1,y_1)$ 与 $(x_2,y_2)$$(x_2,y_2)$ 连接起来。

说明/提示

对于每一个测试点，如果你用的步数小于等于前 $i$$i$ 个评分参数，那么你会得到 $i$$i$ 分。

注意事项如下：

1. 所有的 $x,y$$x, y$ 必须是你已经得到的点，这里的已经得到是指输入数据中的点或者已知几何图形的交点（也就是说你不能随便选择一个点来作图，也不能通过选择一个合适的点来得到要求的点）。 更准确地说，每次你输出一个坐标，Special Judge 会选择当前你已经得到的所有点中和你的输入坐标欧几里得距离最近的点作为你这一次的选择点。如果距离最近的点距离大于了 ${10}^{-5}$$10^{-5}$，那么这次操作会被判定为不合法，同时这一个点你将得到 $0$$0$ 分。

2. 你不能根据圆心和半径作圆，而只能根据圆心和圆上一点作圆。

3. 你画出的答案与要求的点绝对误差或相对误差不超过 ${10}^{-5}$$10^{-5}$ 即为正确（因为不知道怎么写没有误差的 Special Judge，并且搬题的我也不会）。 更准确地说，假设你得到的点是 $(x_1,y_1)$$(x_1, y_1)$，而要求的点是 $(x_2,y_2)$$(x_2, y_2)$，则你的输出被认为正确，当且仅当满足

   $${\displaystyle \frac{|x_1-x_2|}{max(|x_2|,1)}}\le {10}^{-5}\wedge {\displaystyle \frac{|y_1-y_2|}{max(|y_2|,1)}}\le {10}^{-5}$$

4. 下发文件中的 data1.in 到 data10.in 分别为 $10$$10$ 个输入数据，其中第 $1,2,3,7,8$$1,2,3,7,8$ 这五个测试点配有图解。

5. 下发的 checker 可以判断你的得分。使用方法如下（其中 data.in 是输入文件，data.out 是你的输出文件）：

• Windows-32/64：

xxxxxxxxxx
1
1
checker data.in data.out data.out

• Linux/MacOS：

xxxxxxxxxx
1
1
./checker data.in data.out data.out

6. 文件均已下发到 Tsawke's Exam - Issue/dddddddraw/。

Examples

Input_1

xxxxxxxxxx
10
1
0
2
2
3
0.0000000000 0.0000000000
4
0.0000000000 1.0000000000
5
1
6
1 2
7
0
8
0
9
0.8660254038 0.5000000000
10
11 10 9 8 7 6 5 4 3 2

Output_1

xxxxxxxxxx
3
1
2
2
1 0.0000000000 0.0000000000 0.0000000000 1.0000000000
3
1 0.0000000000 1.0000000000 0.0000000000 0.0000000000

样例说明

显然我们要画出的是已知线段的中垂线，做两个圆，交点即为所求。