QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 256 MB Points totaux : 100

#491. 检测洗牌方法

Statistiques

你在人工智能实验室工作。现在,你正在训练你的 AI 来区分两种数据洗牌(shuffling)方式。你决定使用来自 Petrozavodsk 训练营的学生团队的解决方案作为训练数据。

考虑一个用 Java 或 C++ 编写的程序,它解决了 Petrozavodsk 训练营中的某个问题。将整个程序放入一个字符串 $s$ 中,其中所有 ASCII 码小于或等于 32(空格)的字符都被替换为空格。字符串 $s$ 的长度在 5 到 20 千字节之间,且 $s$ 被补足空格,直到其长度能被 4 整除。

你有两种长度为 $L$ 的字符串 $s$ 的洗牌方式需要区分。

第一种方式如下:随机选择一个从 1 到 $L$ 的排列 $\pi$,并根据 $\pi$ 对 $s$ 中的字符进行洗牌。我们称这种洗牌方式为“随机(random)”。

第二种方式如下:将 $s$ 分为若干个包含 4 个连续字符的块。选择一个从 1 到 $L/4$ 的随机排列,并根据该排列对块进行洗牌。然后,对于每个块,独立选择一个从 1 到 4 的随机排列,并用它对该块中的字符进行洗牌。之后,进行 $\lfloor L/10 \rfloor$ 次操作,每次随机选择两个从 1 到 $L$ 的位置,并交换对应位置上的字符。我们称这种洗牌方式为“块(block)”。

你将获得 $n$ 行数据,每一行都是同一个字符串 $s$ 的随机洗牌或块洗牌结果。其中恰好有一半是随机洗牌产生的,另一半是块洗牌产生的。对于每一行,请识别它是通过随机洗牌还是块洗牌产生的。在每个测试用例中,你必须正确识别至少 80% 的行。

输入格式

输入文件的第一行包含 $n$ —— 随后行的数量($10 \le n \le 100$,$n$ 为偶数)。

接下来的每一行都有相同的长度 $L$($5000 \le L \le 20000$),包含 ASCII 码在 32 到 126 之间的字符。其中 $n/2$ 行是通过随机洗牌产生的,另外 $n/2$ 行是通过块洗牌产生的。字符串 $s$ 是 Petrozavodsk 训练营中提交的某个 C++ 或 Java 源代码,其中所有代码小于 32 的字符都被替换为空格。

样例输入对应于一个 C++ 编写的“Hello World”程序,它违反了所有行长度在 5000 到 20000 之间的限制,任何正确格式化后的输入都将被接受(注意:评测程序也能正确处理此输入)。

输出格式

对于每一行,如果该行代表随机洗牌后的 $s$,则输出 random;如果该行代表块洗牌后的 $s$,则输出 block

题目描述中的样例输出是样例输入的正确答案。

样例

输入 1

10
c<( { ldulm ca}; p itno, loerWdd"!oi t">fsntrielH ) % ", si#inn)("
! dtn"or #iis np "Woo ,% )lfn) {clr m>t(ud; tl<idsec la, H} (i "ne"i
l s,tdio( n)p l { };ud ,tirnlroWc <slH"etn # o ema %inic " >f"(i"!)d
i e nirr ai )pi(; d cnt ,l o s"n {"W,l>!" m Htt <o }("uil#s %)nd c fodle
H ";niorWloidtldue"!)d { n ()le" > plm ,t,rn aio s"ini#cs <c(%ft }
lWcu# eniaf(eo dn !>) "dtisd oni %n tr l" lt,i)mc H(; <} p" s,"r { ilo
idtolrWa> n <csm o " s,ledur it itn%"f(i#cnlH el ,o )"d "{} (n ;} pi
lttdnri an" l# "ms o p>{i i ct r %o)osi ,nfHni!d "u;l (1 cd" W}e(<),e
iencsc< !d ""ilew{ olo rldu# }; ) n (s ,"tin "(f% ptHrntoidl), ami >
nnod)plo{c #" n%(elcu ", t d t,s") ( iims nWl ;iadt! r rf }i H> e "o<l

输出 1

block
random
block
random
block
random
block
random
block
random

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.