Internet Problem Solving Contest

• One possible correct output for A1
• Correct output for A2
• C++ program solving A1
• C++ program solving A2
• Python 3 program to check submissions

Easy subproblem

Sure, you could go with the spirit of the task and generate the output using a random generator, but why bother? It was much easier to output n ones, or simply to copy the sequence k₁, …, k_n from the input to the output.

But the actual “pro move” is to solve the hard subproblem and to submit its solution also as the solution to the easy subproblem.

Hard subproblem

When comparing two strings, we are looking at their characters from the left to the right, until we find the first difference. Hence, if we want to make sure that our string will be the lexicographically smallest of all possible strings, we have to construct it greedily from the left to the right. At each position we have to make sure we use the smallest character possible.

What is the best character we can use? There are three possible answers, in order of preference:

• The very best character is no character at all, i.e., the end of the string. This can only be chosen if we are already on the n-th wheel.
• The next best option is a 0. Whenever the next character can be a 0, we must make it a 0.
• If we cannot use a 0, we have to use a 1.
• We will never need to use any bigger digits, because one of the above will always apply.

Whenever we move to a new wheel, we have to use a 1 as the next character because the numbers on the wheel don’t start with a 0. Afterwards, we may have an option to add some 0s: one if k_i ≥ 10 and another if k_i = 100.

This gives us a very simple algorithm:

• For each of the wheels 1 through n − 1: use the largest of the numbers {1, 10, 100} that is on the wheel.
• For wheel n: use the number 1 (because stopping there is better than adding zeros).