题目描述
世界上最伟大的公司,lezeron 公司,找你定制一个奇怪的机器。
lezeron 公司搭建了一条流水线,生产一种价值 50 Coins 的产品。然而,由于流水线刚刚建成,难免会产生一些次品,你的机器需要找出这些次品。
流水线在搭建的时候考虑到了次品的问题,所以每个产品生产时都有一个 01 串编码,检查产品只需要检查:
- 初始产品编码的 0 和 1 数量相同。
- 初始产品编码的每一个前缀 0 的数量均不少于 1 的数量。
但同样由于产品的形态,性质等问题,你的机器在检查产品时有很大的限制。具体的说,你的机器由 $n$ 个检测仓构成,每个检测仓都是下面两者之一:
- 读取仓:读取并删除产品编码的第一个字符(如果存在),根据读取到的字符(或者没有),将产品运送到另一个检测仓。
- 追加仓:在产品编码末尾追加任意一个字符,并将产品运送到某个检测仓。
你的检测仓由 $1\sim n$ 编号,新生产的产品会出现在检测仓 $1$。还有两个编号特殊的检测仓,$0$ 和 $-1$,它们不属于上面两种,具体的,运送到 $0$ 的产品会被标记为“合格”,运送到 $-1$ 的产品会被标记为“次品”。
由于资金有限,你的检测仓不能超过 $302$ 个,即 $1\le n\le 300$。除了字符 0 和字符 1 外,你的追加仓还可以写其它字符,具体的,你可以设定一个字符集 $m$,你的追加仓可以写 $0\sim m-1$ 内每一个字符。由于可用字符有限,你需要保证 $2\le m\le 128$。
由于你的机器是需要有作用的,你的机器不能让同一个产品被运送超过 $10^6$ 次。如果产品在机器里待了过长时间,lezeron 公司的维修人员就会关闭机器取出产品,并将你的这次检测结果标记为“错误”。
当然,由于 lezeron 公司口碑极佳,少量的检测错误并不会带来很大的影响,因此,lezeron 公司允许你的机器有一定的出错率。当然完美的机器总是更好的,你的机器越优秀,你得到的薪酬越高。
lezeron 公司计划了 $10$ 种场景,每种场景完全独立。lezeron 公司对你的机器的评价就是每个场景你的机器的表现的和。设计更优秀的机器,拿到更高的薪酬(分数)!
输入格式
一行一个字符串 Print your beautiful answer!,因此你无法通过输入区分各个测试点。
输出格式
第一行两个正整数 $n,m$。
接下来 $n$ 行,每行若干个数,其中:
- 第一个数为 $t_i$,表示检测仓类型,$t_i$ 为 $0$ 表示读取仓,否则表示追加仓。
- 若检测仓为读取仓,接下来 $m+1$ 个整数 $c_0,c_1,\dots,c_{m-1},e$,$c_i$ 表示读取到字符 $i$ 时产品的运送去向,$e$ 表示当前产品编码为空时产品的运送去向。
- 若检测仓为追加仓,接下来两个整数 $v,w$,表示在产品编码末尾追加字符 $v$,并将产品运送到检测仓 $w$。
样例输入
Print your beautiful answer!
样例输出
2 2 1 0 2 0 0 -1 1
评分规则
本题一共 $10$ 个测试点,每个测试点 $10$ 分,对应 $10$ 个场景,每个场景都有 $100$ 个产品用于测试你的机器。集合 $S=\{67,75,84,88,92,93,95,98,99,100\}$,对于每个测试点,若你的你的机器正确检测了 $k$ 个产品,对于任意 $x\in S$,若 $k\ge x$,在这个测试点上你都可以获得一分。
样例输出在每个场景上都可以正确检测 $61$ 个产品,因此本样例可以获得 $0$ 分。
对于每个测试点,令所有初始产品编码的长度最大为 $L$,有:
| 测试点编号 | $L\le$ | 测试点编号 | $L\le$ |
|---|---|---|---|
| $1$ | $2\times 10^2$ | $6$ | $3\times 10^4$ |
| $2$ | $1\times 10^3$ | $7$ | $5\times 10^4$ |
| $3$ | $1.2\times 10^3$ | $8$ | $3\times 10^5$ |
| $4$ | $5\times 10^3$ | $9$ | $9\times 10^5$ |
| $5$ | $1\times 10^4$ | $10$ | $9.5\times 10^5$ |
我们下发了一个毫无意义的 checker,你可以使用任意 C++ 语言编译它(建议用 C++14),编译后(假设可执行文件名带后缀为 kzxwjm.exe),其会从标准输入中读入你的方案,从参数中读入 $L$,并使用随机生成的编码测试你的方案。
运作命令:./kzxwjm.exe Number_L(Linux),kzxwjm.exe Number_L(Windows),其中 Number_L 为数据范围中的 $L$。你可以在后面传入更多参数,尽管这没有意义。
你可以任意修改这个 checker 以满足自己的需求。