J. Juicy Candies

Codeforces

IDCF10152J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Alex enjoys eating snacks, in particular candies. Recently he discovered a brand of berry-themed juicy candies, with three flavors: blueberry (B), raspberry (R), and strawberry (S). For brevity, we would, for example, use the term _B-candy_ to refer to blueberry-flavored candy. Alex has B B-candies, R R-candies, and S S-candies. He now wants to form sequences of candies, such that: For each candy sequence, there is a string of length (B + R + S) corresponding to it. If the i-th candy in the sequence is strawberry-flavored, for example, then the i-th character of the string would be _S_. Similarly for blueberry- and raspberry-flavored candies. Before enjoying the candies, Alex would like to solve the following challenge: among all strings which corresponds to a candy sequence, what is the K-th lexicographically smallest string? For two strings s[1...L] and t[1...L], s is said to be lexicographically smaller than t, if there exists an index i (1 ≤ i ≤ L), such that s[j = t[j]] for 1 ≤ j < i, and s[i < t[i]]. We naturally use the character relation _B_ < _R_ < _S_. The first and only line of input consists of four space-separated integers B, R, S, and K. For all test cases, 1 ≤ B, R, S ≤ 200, 1 ≤ K ≤ 1018. If the total number of strings is less than K, output _None_. Otherwise, output the K-th lexicographically smallest string that corresponds to a candy sequence with B B-candies, R R-candies, and S S-candies. ## Input The first and only line of input consists of four space-separated integers B, R, S, and K.For all test cases, 1 ≤ B, R, S ≤ 200, 1 ≤ K ≤ 1018. ## Output If the total number of strings is less than K, output _None_.Otherwise, output the K-th lexicographically smallest string that corresponds to a candy sequence with B B-candies, R R-candies, and S S-candies. [samples]

**Definitions** Let $ B, R, S \in \mathbb{Z}_{\geq 0} $ denote the counts of B-, R-, and S-candies, respectively. Let $ L = B + R + S $. Let $ \Sigma = \{B, R, S\} $ with lexicographic order $ B < R < S $. Let $ \mathcal{S}(B, R, S) $ be the set of all strings of length $ L $ over $ \Sigma $ with exactly $ B $ occurrences of $ B $, $ R $ occurrences of $ R $, and $ S $ occurrences of $ S $. **Constraints** 1. $ 1 \leq B, R, S \leq 200 $ 2. $ 1 \leq K \leq 10^{18} $ 3. $ |\mathcal{S}(B, R, S)| = \binom{L}{B, R, S} = \frac{L!}{B! \, R! \, S!} $ **Objective** If $ \binom{L}{B, R, S} < K $, output "None". Otherwise, output the $ K $-th lexicographically smallest string in $ \mathcal{S}(B, R, S) $.

API Response (JSON)

{
  "problem": {
    "name": "J. Juicy Candies",
    "description": {
      "content": "Alex enjoys eating snacks, in particular candies. Recently he discovered a brand of berry-themed juicy candies, with three flavors: blueberry (B), raspberry (R), and strawberry (S). For brevity, we wo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10152J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alex enjoys eating snacks, in particular candies. Recently he discovered a brand of berry-themed juicy candies, with three flavors: blueberry (B), raspberry (R), and strawberry (S). For brevity, we wo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ B, R, S \\in \\mathbb{Z}_{\\geq 0} $ denote the counts of B-, R-, and S-candies, respectively.  \nLet $ L = B + R + S $.  \nLet $ \\Sigma = \\{B, R, S\\} $ with lexicographic order $ B...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments