J. Choreographer Problem

Codeforces

IDCF10050J

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

As you probably know, choreography is the art of making dances. But it is not a so well-known fact that it is also the science of making dances. There are n dancers numbered from 1 to n in the dance troupe, and all of them are working hard to create a new original dance. Before the dance starts each dancer puts on his special hand-made costume, and he has to wear this costume for the duration of the entire dance. It is known that the costume of i-th dancer is similar to the costumes of (i - 1)-th and (i + 1)-th dancers (therefore the dancers are similar too), but at the same time, i-th dancer is not similar to any other dancer. Therefore, (i - 1)-th and (i + 1)-th dancers are not similar. If n > 1, then the first dancer has the only similar dancer, the last dancer has the only similar dancer, and all other dancers have exactly two similar dancers. The dance starts and ends with an empty stage. The stage should not be empty during the dance. Each minute one of the following changes happens on the stage: At every moment of time the stage must not have more than k dancers, because spectators may lose attention if there are too many dancers on the stage. Now choreographer is thinking about arranging the dance in such a way that each set of the dancers containing no more than k dancers appears on the stage exactly once. Your job is to write a program to help the choreographer. The first line contains two positive integer numbers n, k (1 ≤ n ≤ 20;1 ≤ k ≤ n). Print the only line describing the dance. The substring «_+_i» means that the i-th dancer appears on the stage, the substring «_-_i» means that the i-th dancer leaves the stage. The substring «_++_i» means that the i-th dancer leaves while the similar (i + 1)-th dancer appears, and «_-–_i» means that the i-th dancer leaves while the similar (i - 1)-th dancer appears. The output will be processed from the left to the right. If there are many solutions, you may output any of them. If there is no solution, print 0 to the only line of output. ## Input The first line contains two positive integer numbers n, k (1 ≤ n ≤ 20;1 ≤ k ≤ n). ## Output Print the only line describing the dance. The substring «_+_i» means that the i-th dancer appears on the stage, the substring «_-_i» means that the i-th dancer leaves the stage. The substring «_++_i» means that the i-th dancer leaves while the similar (i + 1)-th dancer appears, and «_-–_i» means that the i-th dancer leaves while the similar (i - 1)-th dancer appears. The output will be processed from the left to the right.If there are many solutions, you may output any of them. If there is no solution, print 0 to the only line of output. [samples]

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 20 $, $ 1 \leq k \leq n $. Let $ D = \{1, 2, \dots, n\} $ be the set of dancers. Define a similarity relation: for $ i \in D $, dancer $ i $ is similar to $ i-1 $ and $ i+1 $ (if they exist). Let $ S \subseteq \mathcal{P}(D) $ be the set of all subsets of $ D $ with size at most $ k $. **Constraints** 1. $ |S| = \sum_{i=0}^{\min(k,n)} \binom{n}{i} $ 2. The dance is a sequence of transitions between subsets of $ D $, starting and ending at $ \emptyset $. 3. At every step, the current subset has size $ \leq k $. 4. Each subset in $ S \setminus \{\emptyset\} $ appears exactly once. 5. Transitions are restricted to: - Add dancer $ i $: $ +_i $ - Remove dancer $ i $: $ -_i $ - Swap $ i \to i+1 $: $ ++_i $ (remove $ i $, add $ i+1 $) - Swap $ i \to i-1 $: $ --_i $ (remove $ i $, add $ i-1 $) 6. Swaps are only allowed between similar dancers: $ ++_i $ requires $ i+1 \leq n $, $ --_i $ requires $ i-1 \geq 1 $. **Objective** Find a sequence of transitions such that: - The sequence starts at $ \emptyset $, ends at $ \emptyset $, - Every non-empty subset of size $ \leq k $ appears exactly once, - Each transition respects the allowed operations and similarity constraints. If such a sequence exists, output it as a concatenated string of transition tokens; otherwise, output `0`.

API Response (JSON)

{
  "problem": {
    "name": "J. Choreographer Problem",
    "description": {
      "content": "As you probably know, choreography is the art of making dances. But it is not a so well-known fact that it is also the science of making dances. There are n dancers numbered from 1 to n in the dance ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10050J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "As you probably know, choreography is the art of making dances. But it is not a so well-known fact that it is also the science of making dances.\n\nThere are n dancers numbered from 1 to n in the dance ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 20 $, $ 1 \\leq k \\leq n $.  \nLet $ D = \\{1, 2, \\dots, n\\} $ be the set of dancers.  \nDefine a similarity relation: for $ i \\in D $,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments