Igor Perić

Original problem statement taken from this link.

Madoka and Math Dad

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

Madoka finally found the administrator password for her computer. Her father is a well-known popularizer of mathematics, so the password is the answer to the following problem.

Find the maximum decimal number without zeroes and with no equal digits in a row, such that the sum of its digits is N.

Madoka is too tired of math to solve it herself, so help her to solve this problem!

Input

Each test contains multiple test cases. The first line contains a single integer T (1 <= T <= 1000) — the number of test cases. Description of the test cases follows.

The only line of each test case contains an integer N (1 <= N <= 1000)— the required sum of the digits

Output

For each test case print the maximum number you can obtain.

Example input:

5
1
2
3
4
5

Example output:

1
2
21
121
212

Note:

The only numbers with the sum of digits equal to 22 without zeros are 22 and 1111. But the last one has two ones in a row, so it’s not valid. That’s why the answer is 22.

The only numbers with the sum of digits equal to 33 without zeros are 111111, 1212, 2121, and 33. The first one has 22 ones in a row, so it’s not valid. So the maximum valid number is 2121.

The only numbers with the sum of digits equals to 44 without zeros are 11111111, 211211, 121121, 112112, 1313, 3131, 2222, and 44. Numbers 11111111, 211211, 112112, 2222 aren’t valid, because they have some identical digits in a row. So the maximum valid number is 121121.

Solution

The first observation is that if the constraint for two successive digits being distinct didn’t exist, we could simply generate the solution as N successive digits 1. Due to the limitation, we are forced to alternate between 1 and other digits.

The next observation is we never want to use any digits other than 1 and 2. The reason for this is simple. Imagine we have a candidate solution with X digits containing only digits 1 and 2 and a single digit higher than 2. We can replace this candidate solution with another number by subtracting 1 from that higher digit and adding it as a new digit 1. This new number would be made up of X+1 digits and, as such, guaranteed to be higher.

Knowing these observations the solution can be built by generating alternating series of digits 1 and 2 until we sum up to our number N. The only remaining thing to determine is should we start with 1 or 2.

We could observe generating pairs of digits instead of one digit at a time. This way we have two possibilities: 12 or 21. Among these two it makes sense to pick 21 to make the number higher. It is worth of noting generating pair “21” adds 3 to total sum of the digits, so it is worth considering how do various values of N behave with respect to division by 3. In other words, how many of this pairs “21” can we generate to approach the sum of N.

1. if N mod 3 == 0, we know we can generate exactly n/3 pairs of “21” and we are done. I.e. for N = 9 solution would be 212121, for N = 15 solution would be 2121212121
2. if N mod 3 == 1, we know we can generate floor(n/3) pairs of “21” and we are left with 1 to reach the sum of N. We add this missing “1” as the first digit of the number (since adding it to the back would violate the non-consecutive digits rule). I.e. for N = 7 solution is 1212121.
3. if N mod 3 == 2, we know we can generate floor(n/3) pairs of “21” and we are left with 2 to reach the sum of N. We add this missing “2” as the last digit of the number (since adding it to the front would violate the non-consecutive digits rule). I.e. for N = 8 solution is 2121212.

This is how one possible implementation would look like:

#include <iostream>
#include <vector>

using namespace std;

int mainA(int argc, const char * argv[]) {
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int d = (n % 3) == 1 ? 1 : 2;
        while (n) {
            cout << d;
            n -= d;
            d = (d == 2) ? 1 : 2;
        }
        cout << endl;
    }
    
    return 0;
}