Hướng dẫn giải của Bedao Regular Contest 12 - GEN


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Dễ thấy, nếu độ dài của các tên file là ~k~ thì số lượng test tối đa luôn là ~10^k - 1~.

Lúc này, để tìm số lượng test tối thiểu, ta sẽ xét file được đánh số lớn nhất. Nếu tên file có chứa số ~0~ ở đầu, số lượng test tối thiểu sẽ là ~10^{k - 1}~; ngược lại, con số được đánh trên file đó chính là số lượng test tối thiểu.

Độ phức tạp: ~O(nk)~ với ~k~ là độ dài của các tên file.

Code mẫu

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int k;
    cin >> k;
    int len = 0;
    int maxv = 0;
    bool nz = false;
    for (int i = 0; i < k; i++) {
        string s;
        cin >> s;
        len = s.size();
        if (s[0] != '0') {
            nz = true;
        }
        while (s[0] == '0') {
            s.erase(0, 1);
        }
        maxv = max(atoi(s.c_str()), maxv);
    }

    if (nz) {
        cout << maxv << endl;
    } else {
        cout << '1';
        for (int i = 0; i < len - 1; i++) {
            cout << '0';
        }
        cout << endl;
    }
    for (int i = 0; i < len; i++) {
        cout << '9';
    }
    cout << endl;

    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.