QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

#14582. 产品检测

统计

题目描述

世界上最伟大的公司,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 以满足自己的需求。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.