#P16987. [SGU459] Choreographer Problem

[SGU459] Choreographer Problem

题目描述

一个舞团有 nn 名舞者,编号为 1,2,,n1,2,\dots,n

ii 名舞者只与编号相邻的舞者相似,即可能与第 i1i-1 名和第 i+1i+1 名舞者相似;除此之外,他与其他舞者都不相似。

舞蹈开始前舞台为空,舞蹈结束时舞台也必须为空。在舞蹈进行过程中,舞台不能为空。

每一分钟只能发生下列四类变化之一:

  • 一名当前不在舞台上的舞者 ii 上台,记作 +i
  • 一名当前在舞台上的舞者 ii 下台,记作 -i
  • 舞者 ii 下台,同时与他相似的舞者 i+1i+1 上台,记作 ++i
  • 舞者 ii 下台,同时与他相似的舞者 i1i-1 上台,记作 --i

任意时刻舞台上的舞者数不能超过 kk

编舞者希望安排一场舞蹈,使得每一个人数不超过 kk 的舞者集合都恰好在舞台上出现一次。开始和结束时的空舞台分别作为舞蹈的起点和终点;舞蹈过程中不能再次出现空舞台。

请构造任意一种满足条件的舞蹈方案。如果不存在方案,输出 0

输入格式

一行两个正整数 n,kn,k

1n201\le n\le201kn1\le k\le n

输出格式

输出一行字符串,依次描述整个舞蹈。

  • +i:舞者 ii 上台;
  • -i:舞者 ii 下台;
  • ++i:舞者 ii 下台、舞者 i+1i+1 上台;
  • --i:舞者 ii 下台、舞者 i1i-1 上台。

输出从左到右解析。

若有多种方案,可以输出任意一种;若无解,输出 0

样例

2 1
+1++1-2