#P11773. 巅峰手速
巅峰手速
题目背景
“老妹儿啊,今天该你做家务吧……”
龙牙哥于是自愿体验了阿绫为他量身定制的游戏,把做家务的命运推上赌桌——
题目描述
阿绫给了龙牙哥 张卡牌,它们已经整齐码在了桌上,从左至右第 张的卡牌上的数字为 ,龙牙哥需要通过一系列操作让卡牌上的数字从左至右不降。每次操作中,他可以抽出从左至右第 ( 为给定常数)张卡牌,然后将它放在这些牌的最左侧或最右侧。请帮助龙牙判断自己是否有可能完成目标,如果能,请顺便告诉他一种比较简单的操作方案。
输入格式
首先输入一个整数 ,表示数据组数。
对于每组数据,输入两行:
第一行为两个整数 ,分别表示卡牌数量和给定常数。
第二行为 个整数,第 个数表示第 卡片上的数字 。
输出格式
对于每组数据,输出若干行。格式如下:
-
若龙牙哥无法完成目标,只输出一行
No
。 -
若他能够完成目标,先输出一行
Yes
,然后若干行形如l c
或r c
,表示他连续做了c
次将第 张卡牌放到最左侧或最右侧的操作。最后再输出一个o
,表示操作结束。
你的得分将与操作方案的行数(而非操作次数)有关。(详见得分计算方式)
5
3 2
3 2 1
7 3
4 1 3 2 5 7 6
3 3
2 1 3
7 5
1 2 3 4 5 6 7
6 4
1 1 4 5 1 4
Yes
l 1
r 1
l 1
o
No
No
Yes
o
Yes
r 1
l 1
o
提示
样例解释
对于第一组样例:
将第二张卡牌()放到最左侧,卡牌数字变为 。
将第二张卡牌()放到最右侧,卡牌数字变为 。
将第二张卡牌()放到最左侧,卡牌数字变为 。
此时卡牌上的数字不降,操作结束。
得分计算方式
在一个测试数据中,是否有解判断正确可获得 的分数。如果操作方案也正确,则会跟据操作方案的行数(不包含最后一行的 o
)按下表得分。
行数 | 得分 |
---|---|
一个测试点的得分是其中每组测试数据得分的最小值。
注意事项
为了方便选手调试,本题下发了校验器用于本地自测校验得分,使用方法见后。需要注意下发的校验器与实际使用校验器的可能并不相同。我们保证实际使用的校验器在输出的操作序列行数不超过 的情况下用时不超过 500ms。
如果输出格式有误,你将会获得 分。因此,如果你会判断是否有解但无法给出操作方案,也需要在判断有解后输出一行 o
表示操作结束。
为了避免无意义的反复操作,你需要保证每一次操作均有 ,否则将会获得 分。
校验器使用方法
下载文件 testlib.h
与 checker.cpp
并将其置于同一文件夹。在该目录下运行命令 g++ checker.cpp -o checker -std=c++14
编译得到可执行文件 checker.exe
(windows) / checker
(linux)。
假如自测输入为 in.txt
,程序输出为 out.txt
。由于校验器无法判断是否有解,你需要创建一个答案文件(假如叫作 ans.txt
),并在其中每行一个地写入每组数据的有解情况。例如对于样例,答案文件应为
Yes
No
No
Yes
Yes
将上述提到的输入、输出、答案三个文件与刚刚编译出来的校验器可执行文件置与同一文件夹。
-
如果是 Windows Powershell,输入
.\checker.exe in.txt out.txt ans.txt
。 -
如果是 Linux 终端,输入
./checker in.txt out.txt ans.txt
。
校验器有三种可能的输出:wrong answer
/ ok
/ points x
,分别表示对于该测试点你没有分 / 满分 / 获得了占比为 x
的分。
数据规模与约定
本题采用捆绑测试并开启所有合理的子任务依赖
对于 的数据,,,,。
对于不同的子任务,作如下约定:
子任务编号 | 子任务分值 | ||
---|---|---|---|