Connection Status:
Competition Arena > FormTriples

FormTriples

SRM 851 · 2023-12-06 · by misof

SRM 851 · 2023-12-06 · by misof · Greedy, Math
Class Name: FormTriples
Return Type: String
Method Name: solve
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

There are three character types: digits, lowercase letters and uppercase letters. Digits are D = "0123456789". Lowercase letters are L = "abcdefghij". Uppercase letters are U = "ABCDEFGHIJ".

(We will use just the first 10 letters of the English alphabet.)

Within each type, the individual characters have indices corresponding to their 0-based index in the corresponding string given above. For example, the index 2 corresponds to the digit '2', the lowercase letter 'c', and the uppercase letter 'C'.


You are given the int N, meaning that we will only be using the first N characters of each type.

You are also given the int C containing N positive integers. For each i and each character type X, take exactly C[i] copies of the character X[i].

Divide all characters you took in the previous step into triples (digit, lowercase letter, uppercase letter) in such a way that within each triple the three characters have three mutually distinct indices.

Concatenate each triple (in the order given above) and then concatenate all triples to form one long string. Return that string. If there are multiple solutions, you may return any one of them. If there are no solutions, return an empty string instead.

Constraints

  • N will be between 1 and 10, inclusive.
  • C will have exactly N elements.
  • All elements of C will be positive.
  • sum(C) will not exceed 1000.
Examples
0)
2
{2, 3}
Returns: ""

We have the following characters: "00aaAA111bbbBBB". Using these, we cannot even form a single valid triple: regardless of which three characters we pick, at least two will share the same index.

1)
3
{1, 1, 1}
Returns: "0bC1cA2aB"

We have the characters "0aA1bB2cC". One valid solution is to form the triples (0, b, C), (1, c, A), and (2, a, B). The example return value describes these three triples, in this order.

2)
4
{3, 12, 1, 4}
Returns: ""
3)
4
{2, 3, 3, 2}
Returns: "2dA1cD1cA0bC2dB1cD2aB3bC0bC3aB"
4)
10
{75,333,74,74,74,74,74,74,74,74}
Returns: "0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bF0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG0bG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cG1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1cH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dH1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1dI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eI1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1eJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fJ1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1fA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA1gA2gA2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2gB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB2hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3hB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB3iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4iB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB4jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5jB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB5aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6aB6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC6bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bC7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD7bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bD8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE8bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bE9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF9bF"

Submissions are judged against all 49 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FormTriples with a public method string solve(int N, vector<int> C) · 49 test cases · 2 s / 256 MB per case

Submitting as anonymous