\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1}}\)

• Xét các trường hợp \(n = 2 \times k\), \(n = 4 \times k + 3\), \(n = 4 \times k + 1\)

\(\color{orange}{\text{Hint <Implementation>}}\)

• Nếu cần tìm số số có độ dài chẵn:

Ta sẽ in xen kẽ chẵn lẻ

Khi đảo ngược ta được một số xen kẽ lẻ chẵn

Các chữ số đều là lẻ khi tổng chẵn lẻ không quá 9

Ví dụ: \(1212 + 2121 = 3333\) (\(|1|2|1|2| + |2|1|2|1| = |3|3|3|3|\))

• Nếu cần tìm số có độ dài \(n = 4 \times k + 3\)

Ta đan xen (chẵn và 0) ở phần đầu và (0 và lẻ) ở phần sau

Khi đảo ngược lại ta được số đan xen (lẻ và 0) ở phần đầu và (0 và chẵn) ở phần sau

Các chữ số đều là số lẻ khi tổng chúng là số có 2 chữ số và lẻ

Ví dụ \(2020909 + 9090202 = 111111\) (\(|02|02|09|09| + |09|09|02|02| = |11|11|11|11\))

• Nếu cần tìm số có độ dài \(n = 4 \times k + 1\)

Bạn đọc tự chứng minh rằng không tồn tại cách sắp xếp số thỏa đề

\(\color{green}{\text{Preference AC Code }}\): Implementation

\(^{^{\color{purple}{\text{Complexity : }} O(1)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int n = readInt();

    if (n % 2 == 0) {
        for (int i = 0; i < n; ++i) cout << (i % 2 == 1 ? 2 : 1);
        return 0;
    }

    if (n % 4 == 3) {
        for (int i = 0; i < n / 4; ++i) cout << "20";
        cout << "209";
        for (int i = 0; i < n / 4; ++i) cout << "09";
        return 0;
    }

    cout << -1;
    return 0;
}

\(\color{green}{\text{Preference AC Code }}\): Bitwise, Implementation

\(^{^{\color{purple}{\text{Complexity : }} O(1)\ \color{purple}{\text{time}}\ ||\ O(1)\ \color{purple}{\text{memory}}}}\)

int main()
{
    int n = readInt();

    if ((n & 1) == 0) {
        for (int i = 0; i < n; ++i) cout << (i & 1) + 1;
        return 0;
    }
    if ((n & 3) == 3) {
        n >>= 2;
        for (int i = 0; i < n; ++i) cout << "20";
        cout << "209";
        for (int i = 0; i < n; ++i) cout << "09";
        return 0;
    }

    cout << -1;
    return 0;
}