#P5262. [ROI2007 / JSOI2013] 体育课
[ROI2007 / JSOI2013] 体育课
题目描述
体育课里一共有 个同学,学号从 到 。JYY 的体育老师 KFC 有一个特殊排队方法:
- KFC 先让班里的 个同学按照学号从小到大的顺序,从左到右站成一排,然后从到队列的最左边(也就是第一个学生面前)开始,一直向右走动到第 个学生面前;
- 接着 KFC 再回到第一个学生面前,继续开始向右走,就这样一共走动 次。
- 每次当 KFC 走到第 个学生面前时,KFC 会比较一下队列里第 个学生和第 个学生的身高,如果左边(第 个)的学生比右边(第 个)的学生高,那么 KFC 就会交换这两个学生在队列里的位置。
最终,在 次走动全部结束之后,KFC 会选出队列最右边的一些学生去搬桌子。自然地,JYY 希望能够站在尽量靠左的位置来增加自己踢足球的机会。
此外,JYY 还有一个绝招,那就是在 KFC 老师快走到自己面前的时候,开始蹲下来系鞋带!如果 JYY 蹲下来系鞋带了,那么在这一次走动中,好说话的 KFC 老师就不会让 JYY 和相邻的同学比较身高了,自然也就不会让 JYY 和相邻的同学交换位置(只有 JYY 最聪明会蹲下来系鞋带,其他同学都只会老老实实的让 KFC 老师比较身高)。
蹲下来系鞋带是很耗费体力的。为了留着体力踢足球,JYY 最多只能蹲下 次。
JYY 想知道,按照怎样的下蹲策略可以使自己在队列里站的尽量靠左。用一个长度为 的字符串来表示一个策略:如果字符串的第 个字符是 +
,则表示在第 次走动时 JYY 蹲下来系鞋带;如果第 个字符是 -
,则表示 JYY 会老老实实地比较身高。
输入格式
第一行包含三个整数 ,分别表示同学的数量、JYY 的学号、JYY 最多能蹲下的次数。
第二行包含 个整数,其中第 个整数表示 ,表示学号为 的同学的身高。
输出格式
第一行包含一个正整数,表示按照最佳策略时 JYY 可以排在的最靠左的位置。
第二行包含一个长度为 的字符串,表示最佳策略。如果有多个最佳策略,JYY 希望知道字典序最大的策略。
10 7 7
8 3 5 4 5 7 4 2 1 3
3
----+++++
提示
数据范围:,,。