算法题应有的出题规范（写给sastoj）

给算法竞赛出题涉及题面，测试点等多个方面，由于没有规范的情况下，出题人容易出格式千奇百怪，题面表达不清等问题，所以在这里给出sastoj特色出题规范 当然，关于题面，数据点等方法也同样适用于任何其他oj。

题面书写

此部分的规范不对愚人节比赛的题目有任何约束力。但应遵守本文档的其他部分。

组成部分

通常来说一道完整的题面应包含一下部分（*表示可省略）：

1. *题目背景。讲述一道题目的背景，可以不写。题目背景用于介绍题目所属故事，便于读者理解，也可以用于增加题目趣味性。

2. 题目描述。题目的核心部分。要 没有歧义 地符合格式地指出任务的要求。

3. 输入/输出格式。指出输入的形式，类型和数据范围。

4. 输入/输出样例。表示给出的一种输入以及正确程序应该输出的结果。样例可以有多个。

5. *补充。对题目可能产生歧义的部分作出解释，或对样例进行说明。

题目描述的规范

题目描述是对于一道题目的核心部分。对于一个合格的题面，题目描述部分应当没有任何歧义地指出一个题目所要求解决的问题。有以下几条可能出现失误的要点必须遵守：

• 对于一个需要解释的名词（尽管约定俗成）， 必须指出它的具体定义。必要时可以使用数学表达式。

下面给出一部分常用名词的具体定义：

排列(Permutation)：一段1~n的整数序列。保证1~n每个数字有且仅出现一次。

子序列(subsequence):从给定序列中去除一些元素，而不改变其他元素之间相对位置而得到的。

子串(substring):表示 $S$ 串中从 $i$ 到 $j$ 这一段，也就是顺次排列 $S[i],S[i+1],\ldots,S[j]$ 形成的字符串。

自环 (loop)：对 $E$ 中的边 $e = (u, v)$，若 $u = v$，则 $e$ 被称作一个自环。

更多相关基础词语的定义，参见oi-wiki或者维基百科等资源。

• 对于每一个需要作为输入输出数据的数（或作为运算时的中间变量），必须使用不同的字母进行标识。字母旁边最好标上对应数据范围。（若没有，则须在补充中说明）

比如，下面这样的题目（a+b problem）的描述是不被允许的：

给出两个整数，请输出它们的和。

正确的表述如下:

给出两个整数$a$, $b$ （$a, b \leq 10^8$），输出$a+b$。

• 题目描述可以延续题目背景所说的世界观所描述。但是在写出要求（约束条件）的时候，必须要标准写出。不能掺杂任何模棱两可的词汇。

写题目的大忌是认为做题者会往理所应当的思路上来理解自己的题目。然而事实上，不同人可能会有各种的理解（这可能也是赛时clarification的意义）。我们要保证的是在不能让做题者产生任何不符合标准程序的理解。一种解决方式是给自己的题面 “找茬” 。

IO格式、样例及补充

输入输出格式部分：

输入格式应该标明总共的行数，以及每行需要输入的内容。请注意，这里要输入的所有内容也一定要给出字母。

sastoj给出了可以选择行末空格以及文末换行的功能，所以应当在体面中也对此有所表明。

输入输出样例：

每一个样例应该给出（输入/输出）#序号的小标题。并在下面给出多行代码块。

补充：

补充内容一定要写上样例解释（样例解释的规范参见“题目描述的规范”）便于做题者进行理解。如果有参考的资料，引用，或者附件，都应该在这一段中标明。

如果题目描述中没有数据范围，则务必在此补充上。

题面格式

关于markdown

我们使用markdown来书写题面。markdown是一种设计来易于阅读、编写和理解的标记语言。

要学习markdown语法可见官方教程

在题面书写部分，我们已经列出了一道题面的组成部分，这些部分应当都使用二级标题，一级标题则用来写此题的题面。

具体来说，markdown应如下图所示：

# 标题
## 题目背景
## 题目描述
## 输入格式
## 输出格式
## 输入输出样例
### 输入#1
### 输出#1
### 输入#2
### 输出#2
## 补充

关于markdownlint

The Markdown markup language is designed to be easy to read, write, and understand. It succeeds - and its flexibility is both a benefit and a drawback. Many styles are possible, so formatting can be inconsistent. Some constructs don’t work well in all parsers and should be avoided. The CommonMark specification standardizes parsers - but not authors.

markdownlint 是一套用来规范markdown书写格式的工具。有了markdownlint，写作者的语法将更为规范。

使用markdownlint可以按照GitHub官网的方式，使用nodejs进行下载，也可以使用vscode，obsidian等工具自带的markdownlint扩展。

关于sastoj的markdownlint规范，请点击此链接。

使用方式：将上述链接中的文件复制到你所写markdown文件所在的同一工作环境中以使markdownlint按照规定的.markdownlint.jsonc文件所述的规范进行错误提醒。

题面中所涉及的markdown规范

1. 所有出现的变量，数字，数学符号，公式等，必须使用$Latex$。

2. 在一些需要注意的要点中，可以使用加粗符号来重点说明。

3. 一些专有的英文名词，可以使用代码块标注。

4. 输入输出样例，必须包含在多行代码块中。

5. 如果必须要插入图片（用作样例的解释或者具体说明等）须提前存在图床中再使用![]()的格式。

6. 不要滥用 markdown的特殊$格式$。

测试点设置

sastoj目前仅支持常规题的测试点。测试点可以有多个，每一个都可以有对应的分数点。如果你程序的输出结果与数据点的.out或.ans文件相同，视为通过该测试点，应该获得对应分数。

出数据的原则

我们在生成一个题目的数据时，应当遵守如下原则：

• 如果是新手向的比赛（非ICPC赛制），最好在数据点中加入样例。

作为初次接触程序设计竞赛的新手，他们可能对一道题目如何提交，如何判分等步骤产生困惑，只能根据样例来判断自己的代码是否正确。为了不让他们感到困惑，最好在数据点中加入样例。

• 对于非ICPC赛制的比赛，数据范围的设置应当有一定梯度。

根据算法的优劣的区别，一道题目的分数也应当有所区别，分数在一定程度上更是对于一道题目完成度的体现。比如说，对一道数据结构题目，应当至少提供$30\%$的答案正确的暴力算法分数。

• 一道完整数据点的题目应当有针对特判的数据。

在许多题目中，对于一些特殊的数据，不能使用常规的算法来解决问题。为了考察参赛者思维的严谨性，应当有一些特殊的数据来考察参赛者是否考虑到了这种情况。

• 只有复杂度优秀的算法才能够获得满分，但尽量不要卡常数。

这要求出题者需要一定程度上严格把握时间、空间限制。既不能出现数据偏弱，可以用暴力卡过去的情况，也不能出现数据太强，参赛者屡屡被卡常的情况。出题者应对比赛用评测机有一定估量，在写标准程序的时候，可以故意把常数写的大一点。

• 对于ICPC赛制的比赛，应当有能hack掉每一种错误算法的数据。

常用(臭名昭著)的方法有：生成菊花图，生成链，卡单哈希等等。当然，这些不一定要做，但是针对生成错误答案的程序应该将其hack掉。

• 使用lf进行换行，而非crlf。

算法竞赛的评测机采用Linux系统，在 Linux 和 Mac 上，LF相当于新文本行的开始。如果采用windows系统所输出的回车+换行符CRLF的话，可能会产生一下不确定的错误。

虽然sastoj有将CRLF转化为LF的功能，但我们仍然建议在出数据的时候就以LF进行换行。

工具与方法

对于较大的数据点，手动输入肯定是不现实的。下面有一部分出数据的工具与方法介绍：

编写python程序

python由于其轻量化的优势，常常用来生成一道题目的测试数据（当然，您也可以使用其他的语言）。这里仅介绍python编写数据生成器的方法。

以a+b problem为例，下面是生成数据的代码。

import random
import os

for i in range(1，11): # 我们生成1.in,1.out,2.in,2.out....
    with open(f"{i}.in", "wb") as f:
        a = random.randint(1, 100000)
        b = random.randint(1, 100000)
        # 我们生成1~100000范围内的整数a和b 
        f.write(bytes(f"{a} {b}\n", "utf-8"))
        #将生成的数据写入文件。
        #注意：为了保证写入lf而不是crlf，我们将字符串以utf-8编码，转化为二进制写入
        os.system(f".\std.exe < {i}.in > {i}.out")
        # std.exe为出题者所写的标准程序。这条命令表示以{i}.in为输入，以std.exe为程序，将输出写入{i}.out文件。

使用CYaRon

CYaRon是洛谷开发的一款开源的数据生成工具。其中支持生成不同类型的树、图等数据。当然，CYaRon也是基于Python的。

CYaRon的稳定版本可以从pip获取:

pip install cyaron

在此之前，需要准备好Python。

当然，您可以参照文档进行学习。

配置文件

为了设置题目的时空限制，设置题目类型以及配置数据点结构， sastoj 设置了一套配置文件的规则。

对于不同题型的题目的配置文件方法，详情见示例

作为出题者，一般情况下我们使用.toml格式写配置文件。配置文件中能够标明题目的时空限制，分数分布以及数据点的关系等等。

使用yapyto生成配置文件

yapyto是一款基于python的sastoj专用配置文件生成工具。主要功能有

1. 根据当前的数据点自动生成所需的配置文件

2. 将hydro上的题目便捷转化为sastoj所需的格式。

3. 给定标程以及对应的数据生成器，直接生成输入输出文件和对应的配置文件。

您需要把yapyto的GitHub仓库clone到本地进行使用。