CF733C.Epidemic in Monstropolis
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There was an epidemic in Monstropolis and all monsters became sick. To recover, all monsters lined up in queue for an appointment to the only doctor in the city.
Soon, monsters became hungry and began to eat each other.
One monster can eat other monster if its weight is strictly greater than the weight of the monster being eaten, and they stand in the queue next to each other. Monsters eat each other instantly. There are no monsters which are being eaten at the same moment. After the monster A eats the monster B, the weight of the monster A increases by the weight of the eaten monster B. In result of such eating the length of the queue decreases by one, all monsters after the eaten one step forward so that there is no empty places in the queue again. A monster can eat several monsters one after another. Initially there were n monsters in the queue, the i-th of which had weight a__i.
For example, if weights are [1, 2, 2, 2, 1, 2] (in order of queue, monsters are numbered from 1 to 6 from left to right) then some of the options are:
- the first monster can't eat the second monster because _a_1 = 1 is not greater than _a_2 = 2;
- the second monster can't eat the third monster because _a_2 = 2 is not greater than _a_3 = 2;
- the second monster can't eat the fifth monster because they are not neighbors;
- the second monster can eat the first monster, the queue will be transformed to [3, 2, 2, 1, 2].
After some time, someone said a good joke and all monsters recovered. At that moment there were k (k ≤ n) monsters in the queue, the j-th of which had weight b__j. Both sequences (a and b) contain the weights of the monsters in the order from the first to the last.
You are required to provide one of the possible orders of eating monsters which led to the current queue, or to determine that this could not happen. Assume that the doctor didn't make any appointments while monsters were eating each other.
蒙斯特罗波利斯爆发了一场瘟疫,所有怪物都生病了。为了康复,所有怪物排成一队,依次前往城市中唯一的医生处就诊。
很快,怪物们感到饥饿,开始互相吞食。
一个怪物可以吞食另一个怪物,当且仅当它的体重严格大于被吞食怪物的体重,且它们在队列中相邻。怪物之间的吞食是瞬间完成的,且任意时刻至多只有一个吞食行为发生(即不存在多个怪物同时被吃掉的情况)。当怪物 A 吞食怪物 B 后,怪物 A 的体重增加为 A 与 B 的体重之和。吞食发生后,队列长度减少 1,所有位于被吞食怪物之后的怪物均向前移动一位,从而保证队列中没有空位。一个怪物可以连续吞食多个怪物(每次只吞食其相邻的、体重更小的怪物)。初始时队列中有 n 个怪物,其中第 i 个怪物的体重为 ai。
例如,若初始体重序列为 [1,2,2,2,1,2](按队列顺序,怪物从左到右编号为 1 至 6),则以下是一些可能的情形:
- 第一个怪物无法吞食第二个怪物,因为 a1=1 不大于 a2=2;
- 第二个怪物无法吞食第三个怪物,因为 a2=2 不大于 a3=2;
- 第二个怪物无法吞食第五个怪物,因为它们在队列中不相邻;
- 第二个怪物可以吞食第一个怪物,队列将变为 [3,2,2,1,2]。
过了一段时间,有人讲了一个好笑话,所有怪物都痊愈了。此时队列中剩下 k(k≤n)个怪物,其中第 j 个怪物的体重为 bj。序列 a 和 b 均按队列从前到后的顺序给出怪物体重。
你需要给出一种可能的怪物吞食顺序,使其最终得到当前队列;或者判定该情况不可能发生。假设在怪物互相吞食期间,医生未进行任何就诊安排。
输入格式
The first line contains single integer n (1 ≤ n ≤ 500) — the number of monsters in the initial queue.
The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 106) — the initial weights of the monsters.
The third line contains single integer k (1 ≤ k ≤ n) — the number of monsters in the queue after the joke.
The fourth line contains k integers _b_1, _b_2, ..., b__k (1 ≤ b__j ≤ 5·108) — the weights of the monsters after the joke.
Monsters are listed in the order from the beginning of the queue to the end.
第一行包含一个整数 n(1≤n≤500)—— 初始队列中怪物的数量。
第二行包含 n 个整数 a1,a2,...,an(1≤ai≤106)—— 初始时各怪物的重量。
第三行包含一个整数 k(1≤k≤n)—— 笑话之后队列中剩余怪物的数量。
第四行包含 k 个整数 b1,b2,...,bk(1≤bj≤5⋅108)—— 笑话之后各怪物的重量。
怪物按队列从前到后的顺序列出。
输出格式
In case if no actions could lead to the final queue, print "NO" (without quotes) in the only line.
Otherwise print "YES" (without quotes) in the first line. In the next n - k lines print actions in the chronological order. In each line print x — the index number of the monster in the current queue which eats and, separated by space, the symbol 'L' if the monster which stays the x-th in the queue eats the monster in front of him, or 'R' if the monster which stays the x-th in the queue eats the monster behind him. After each eating the queue is enumerated again.
When one monster eats another the queue decreases. If there are several answers, print any of them.
如果不存在任何操作序列能到达最终队列,则在唯一一行中输出 "NO"(不带引号)。
否则,在第一行输出 "YES"(不带引号)。接下来的 n−k 行按时间顺序输出各次操作。每行输出一个整数 x —— 表示当前队列中第 x 位的怪物进行吞噬,随后空格分隔,若该第 x 位怪物吞噬其前方的怪物则输出 'L',若吞噬其后方的怪物则输出 'R'。每次吞噬后,队列重新编号。
当一只怪物吞噬另一只时,队列长度减小。若存在多种可行方案,输出任意一种即可。
输入输出样例
输入#1
6 1 2 2 2 1 2 2 5 5
输出#1
YES 2 L 1 R 4 L 3 L
输入#2
5 1 2 3 4 5 1 15
输出#2
YES 5 L 4 L 3 L 2 L
输入#3
5 1 1 1 3 3 3 2 1 6
输出#3
NO
说明/提示
In the first example, initially there were n = 6 monsters, their weights are [1, 2, 2, 2, 1, 2] (in order of queue from the first monster to the last monster). The final queue should be [5, 5]. The following sequence of eatings leads to the final queue:
- the second monster eats the monster to the left (i.e. the first monster), queue becomes [3, 2, 2, 1, 2];
- the first monster (note, it was the second on the previous step) eats the monster to the right (i.e. the second monster), queue becomes [5, 2, 1, 2];
- the fourth monster eats the mosnter to the left (i.e. the third monster), queue becomes [5, 2, 3];
- the finally, the third monster eats the monster to the left (i.e. the second monster), queue becomes [5, 5].
Note that for each step the output contains numbers of the monsters in their current order in the queue.
在第一个例子中,初始时有 n=6 只怪物,它们的重量依次为 [1, 2, 2, 2, 1, 2](按队列顺序,从第一只怪物到最后一只是从前到后排列)。最终队列应为 [5, 5]。以下是一系列吞噬操作,可得到最终队列:
- 第二只怪物吞噬其左侧的怪物(即第一只怪物),队列变为 [3, 2, 2, 1, 2];
- 第一只怪物(注意:它在上一步中是第二只)吞噬其右侧的怪物(即第二只怪物),队列变为 [5, 2, 1, 2];
- 第四只怪物吞噬其左侧的怪物(即第三只怪物),队列变为 [5, 2, 3];
- 最后,第三只怪物吞噬其左侧的怪物(即第二只怪物),队列变为 [5, 5]。
注意:每一步输出中所列数字表示当前队列中怪物的编号(按队列顺序)。
输入解题思路,AI测评打分。不知道怎么写?