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.
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ả:
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