Hướng dẫn giải

Cho số ~S~ gồm ~N~ chữ số không có số ~0~ ở đầu. Được xóa một số chữ số (không nhất thiết liên tiếp) và sắp xếp lại các chữ số còn lại, sao cho số thu được là số Ebne: không có số ~0~ ở đầu, chữ số cuối lẻ, và tổng các chữ số chẵn. Nếu không làm được thì in ~-1~.

Nhận xét quan trọng: số Ebne phải có chữ số cuối lẻ và tổng chữ số chẵn, nên số chữ số lẻ được giữ lại phải chẵn và ít nhất bằng ~2~. Nếu ~S~ có ít hơn hai chữ số lẻ thì không làm được.

Lưu ý: một số test trong bộ dữ liệu có ~S~ bắt đầu bằng chữ số 0 (trái đảm bảo của đề); chương trình chỉ xét tiền tố của ~S~ nên vẫn khớp đáp án mẫu (in tiền tố đến chữ số lẻ thứ hai, kể cả số 0 đầu).

Sub 1: Vét cạn theo tiền tố — ~O(N^2)~, dùng khi ~N \le 100~

Thử lần lượt mọi tiền tố ~S[0..L)~ với ~L = 1, 2, \dots, N~. Với mỗi tiền tố, kiểm tra điều kiện Ebne bằng cách tính lại tổng chữ số. In tiền tố đầu tiên thỏa mãn, hoặc in ~-1~ nếu không có.

Kết quả chấm riêng sub này: đúng 21/21 test (các test đều chạy kịp giờ).

Sub 2: Lấy tiền tố đến chữ số lẻ thứ hai — ~O(N)~

Chọn tiền tố ngắn nhất kết thúc bằng chữ số lẻ có tổng chẵn. Tiền tố đến chữ số lẻ thứ hai có đúng hai chữ số lẻ (tổng chẵn), kết thúc bằng chữ số lẻ, và chữ số đầu khác ~0~ theo đề. Các tiền tố ngắn hơn chỉ có một chữ số lẻ nên tổng là số lẻ. Vì vậy chỉ cần quét một lần, đếm chữ số lẻ, và dừng khi đếm được hai.

Bẫy cần chú ý: không cần sắp xếp lại các chữ số, và không cần xóa chữ số ở giữa. Xóa tất cả các chữ số sau vị trí đó là đủ.

Kết quả chấm riêng sub này: chưa đo được riêng (xem ghi chú bên dưới).

Chương trình hoàn chỉnh

Chương trình đọc ~T~, rồi với mỗi bộ dữ liệu đọc ~N~ và ~S~. Nếu ~N \le 100~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.

#include <bits/stdc++.h>
using namespace std;

int N;
string S;

// Kiểm tra chuỗi w có là số Ebne không: chữ số cuối lẻ và tổng chữ số chẵn
// (không cần kiểm tra số 0 ở đầu: mọi tiền tố của S đều bắt đầu bằng chữ số đầu của S, đề đảm bảo khác 0)
bool isEbne(const string& w) {
    if (w.empty()) return false;
    if ((w.back() - '0') % 2 == 0) return false;
    int sum = 0;
    for (char c : w) sum += c - '0';
    return sum % 2 == 0;
}

// Sub 1: vét cạn — thử lần lượt mọi tiền tố S[0..L) (xóa hết các chữ số phía sau),
// mỗi tiền tố tính lại tổng chữ số từ đầu. Độ phức tạp O(N^2). Dùng khi N <= 100
void sub1() {
    for (int L = 1; L <= N; L++)
        if (isEbne(S.substr(0, L))) { cout << S.substr(0, L) << "\n"; return; }
    cout << -1 << "\n";
}

// Sub 2: nhận xét — tiền tố ngắn nhất hợp lệ kết thúc đúng ở chữ số lẻ thứ hai.
// Lý do: chữ số đầu S[0] khác 0 (đề đảm bảo), tiền tố đến chữ số lẻ thứ hai có đúng 2 chữ số lẻ
// (tổng chẵn) và kết thúc bằng chữ số lẻ. Tiền tố ngắn hơn chỉ có một chữ số lẻ nên tổng lẻ.
// Nếu S có ít hơn hai chữ số lẻ thì không có đáp án. Độ phức tạp O(N)
void sub2() {
    int cntOdd = 0;
    for (int i = 0; i < N; i++) {
        if ((S[i] - '0') % 2 == 1) cntOdd++;
        if (cntOdd == 2) { cout << S.substr(0, i + 1) << "\n"; return; }
    }
    cout << -1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> N >> S;
        if (N <= 100) sub1();   // N nhỏ: vét cạn cho chắc
        else sub2();            // N lớn: lấy ngay tiền tố đến chữ số lẻ thứ hai
    }
    return 0;
}