\(\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 <Implementation>}}\)

• Số chia hết cho 30 là số chia hết cho cả 3 và chia hết cho 10 (vì 3 và 10 nguyên tố cùng nhau)

Số chia hết cho 3 khi tổng chữ số chia hết cho 3

Số chia hết cho 10 khi chữ số cuối cùng là số 0

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

• Gọi tổng các chữ số nhận được là \(sum\)

Khi \(sum\) chia hết cho 3, ta xuất kết quả

Khi \(sum\) chia 3 dư 1, ta thử xóa 1 số chia 3 dư 1 hoặc thử xóa 2 số chia 3 dư 2

Khi \(sum\) chia 3 dư 2, ta thử xóa 1 số chia 3 dư 2 hoặc thử xóa 2 số chia 3 dư 1

Khi xóa ta ưu tiên từ nhỏ tới lớn, từ ít chữ số sang nhiều chữ số

• Nếu không có số 0 hoặc không có cách xóa thỏa mãn khi cần xóa, ta xuất -1

• Nếu không có cách xuất các chữ số khác 0 thì ta chỉ xuất 1 số 0

• Ngược lại ta xuất kết quả, ưu tiên số lớn trước số bé hơn

\(\color{orange}{\text{Hint 2 <Space-Optimization>}}\)

• Thay vì lưu kiểu xâu ta có thể dùng mảng tần số \(cnt[x]\) là số lượng phần tử \(x\) có trong mảng

Ta có tổng \(sum = \underset{v \in [0, 9]}{\Sigma}(v \times cnt[v])\)

Thêm một phần tử \(x\) là \(cnt[x] = cnt[x] + 1\)

Xóa một phần tử \(x\) là \(cnt[x] = cnt[x] - 1\)

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

\(^{^{\color{purple}{\text{Complexity : }} O(n + alphabet)\ \color{purple}{\text{time}}\ ||\ O(alphabet)\ \color{purple}{\text{memory}}}}\)

int main()
{
    vector<int> cnt(10, 0);
    for (int n = readInt(); n--; cnt[readInt()]++);

    int sum = 0;
    for (int v = 0; v <= 9; ++v)
        sum += v * cnt[v];

    bool ok = cnt[0] > 0;
    if (sum % 3 == 1)
    {
             if (cnt[1] >= 1) cnt[1]--;
        else if (cnt[4] >= 1) cnt[4]--;
        else if (cnt[7] >= 1) cnt[7]--;
        else if (cnt[2] >= 2) cnt[2]--, cnt[2]--;
        else if (cnt[5] >= 2) cnt[5]--, cnt[5]--;
        else if (cnt[8] >= 2) cnt[8]--, cnt[5]--;
        else if (cnt[2] >= 1 && cnt[5] >= 1) cnt[2]--, cnt[5]--;
        else if (cnt[5] >= 1 && cnt[8] >= 1) cnt[5]--, cnt[8]--;
        else if (cnt[8] >= 1 && cnt[2] >= 1) cnt[8]--, cnt[2]--;
        else ok = false;
    }

    if (sum % 3 == 2)
    {
             if (cnt[2] >= 1) cnt[2]--;
        else if (cnt[5] >= 1) cnt[5]--;
        else if (cnt[8] >= 1) cnt[8]--;
        else if (cnt[1] >= 2) cnt[1]--, cnt[1]--;
        else if (cnt[4] >= 2) cnt[4]--, cnt[4]--;
        else if (cnt[7] >= 2) cnt[7]--, cnt[7]--;
        else if (cnt[1] >= 1 && cnt[4] >= 1) cnt[1]--, cnt[4]--;
        else if (cnt[4] >= 1 && cnt[7] >= 1) cnt[4]--, cnt[7]--;
        else if (cnt[7] >= 1 && cnt[1] >= 1) cnt[7]--, cnt[1]--;
        else ok = false;
    }

    if (ok == false)
    {
        cout << -1;
        return 0;
    }

    int t1 = cnt[1] + cnt[4] + cnt[7];
    int t2 = cnt[2] + cnt[5] + cnt[8];
    int t3 = cnt[3] + cnt[6] + cnt[9];
    if (t1 + t2 + t3 == 0)
    {
        cout << 0;
        return 0;
    }

    for (int v = 9; v >= 0; --v)
        while (cnt[v]-->0)
            cout << v;
    return 0;
}