Hướng dẫn giải của Mật khẩu _VP10

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.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, 111_LeQuangTam, oqtn75, vutientuan_001

Hiểu bài toán

Cho một số nguyên dương N (được biểu diễn dưới dạng chuỗi S có độ dài L). Tìm số nguyên dương X lớn nhất thỏa mãn:

  1. X ≤ N.
  2. X là một số ‘xâu lặp’ (periodic string). Tức là, X có thể được tạo thành bằng cách lặp lại một chuỗi con M (gọi là ‘xâu cơ sở’) ít nhất 2 lần. Ví dụ: 121212 là số xâu lặp (M='12', lặp 3 lần).

Đề bài yêu cầu tìm giá trị lớn nhất của X. Dữ liệu đầu vào có thể lên đến 10^18, do đó cần một thuật toán hiệu quả.

Các cách tiếp cận

Cách Quy hoạch động / Xây dựng theo độ dài xâu cơ sở
#include <bits/stdc++.h>
using namespace std;

string s;
long long res = -9e18;
long long L;
long long p10[21];

int main() {
    cin >> s;
    L = s.size();

    // Precompute powers of 10
    p10[0] = 1;
    for(int i=1; i<=20; i++) p10[i] = p10[i-1] * 10;

    // 1. Xử lý các số có độ dài nhỏ hơn L
    // Số lớn nhất có độ dài k là 10^k - 1 (số chỉ toàn 9)
    // Chỉ xét các độ dài >= 2
    for (int k = 2; k < L; k++) {
        res = max(res, p10[k] - 1);
    }

    // 2. Xử lý các số có độ dài bằng L
    // Duyệt độ dài xâu cơ sở i từ 1 đến L/2
    for (int i = 1; i <= L/2; i++) {
        if (L % i != 0) continue;
        int k = L / i; // số lần lặp
        if (k < 2) continue;

        // Lấy xâu cơ sở ban đầu từ N
        string base = s.substr(0, i);
        if (base[0] == '0') continue;

        // Kiểm tra xâu tạo ra từ base có <= s không
        string u = "";
        long long m = 0;
        for (char c : base) m = m * 10 + (c - '0');

        bool ok = true;
        for (int j = 0; j < k; j++) {
            string tmp = to_string(m);
            // Xử lý tràn số (nếu m có số chữ số > i)
            if ((long long)tmp.size() > i) { ok = false; break; }
            while ((long long)tmp.size() < i) tmp = "0" + tmp;
            u += tmp;
        }

        if (ok && u.size() == (size_t)L) {
            if (u <= s) {
                res = max(res, stoll(u));
            } else {
                // Nếu lớn hơn, thử giảm xâu cơ sở đi 1
                long long mm = m - 1;
                if (mm >= p10[i-1]) { // Phải đảm bảo không bị mất chữ số đầu
                    u = "";
                    for (int j = 0; j < k; j++) {
                        string tmp = to_string(mm);
                        if ((long long)tmp.size() > i) { ok = false; break; }
                        while ((long long)tmp.size() < i) tmp = "0" + tmp;
                        u += tmp;
                    }
                    if (ok && u.size() == (size_t)L) {
                        res = max(res, stoll(u));
                    }
                }
            }
        }
    }

    cout << res << endl;
    return 0;
}
  • Time Complexity: O(L^2)
  • Space Complexity: O(L)

Thuật toán chia làm 2 trường hợp:

  1. Độ dài X nhỏ hơn độ dài N (L): Số lớn nhất có độ dài k là số có k chữ số 9. Ta chỉ cần duyệt k từ 2 đến L-1 để tìm max.
  2. Độ dài X bằng L:
    • Duyệt độ dài xâu cơ sở i từ 1 đến L/2.
    • Chỉ xét các i mà L chia hết cho i (vì X phải tạo thành bằng cách lặp lại M).
    • Lấy xâu cơ sở M là phần đầu của N.
    • Kiểm tra việc lặp M k lần có tạo ra số ≤ N không.
      • Nếu có: Đây là ứng cử viên lớn nhất cho độ dài này.
      • Nếu không: Thử M' = M - 1 (giảm giá trị xâu cơ sở). Nếu M' vẫn giữ được độ dài i (tức không bị mất số 0 ở đầu), lặp M' k lần để tạo ứng cử viên.
    • Cập nhật kết quả tối ưu.
Cách Tối ưu hóa Logic (Cải tiến)
// (Logic tương tự Solution 2/3)
// Tối ưu ở việc tạo chuỗi u và xử lý số 0 ở đầu
#include <bits/stdc++.h>
using namespace std;

string s;
long long res = -9e18;
long long L;
long long p10[21];

int main() {
    cin >> s;
    L = s.size();
    p10[0] = 1;
    for(int i=1; i<=20; i++) p10[i] = p10[i-1] * 10;

    // Case 1: độ dài < L
    for (int k = 2; k < L; k++) res = max(res, p10[k] - 1);

    // Case 2: độ dài = L
    for (int i = 1; i <= L/2; i++) {
        if (L % i != 0) continue;
        int k = L / i;
        if (k < 2) continue;

        string t = s.substr(0, i);
        if (t[0] == '0') continue;

        long long m = 0;
        for (char c : t) m = m * 10 + (c - '0');

        // Xây dựng xâu u từ m
        string u = "";
        bool valid = true;
        for (int j = 0; j < k; j++) {
            string tmp = to_string(m);
            if (tmp.size() > i) { valid = false; break; } // Tràn số
            u += tmp;
        }

        if (valid && u.size() == (size_t)L) {
            if (u <= s) res = max(res, stoll(u));
            else {
                // Thử m - 1
                if (m - 1 >= p10[i-1]) {
                    long long mm = m - 1;
                    string v = "";
                    bool valid2 = true;
                    for (int j = 0; j < k; j++) {
                        string tmp = to_string(mm);
                        if (tmp.size() > i) { valid2 = false; break; }
                        v += tmp;
                    }
                    if (valid2 && v.size() == (size_t)L) {
                        res = max(res, stoll(v));
                    }
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}
  • Time Complexity: O(L^2)
  • Space Complexity: O(L)

Đây là phiên bản chi tiết hóa của Approach 1, bám sát các giải pháp được chấp nhận (Accepted Solutions) trong dữ liệu.

Các bước:

  1. Khởi tạo mảng p10 để tính toán các số lũy thừa 10, cần thiết cho việc kiểm tra điều kiện độ dài số.
  2. Duyệt độ dài xâu cơ sở i từ 1 đến L/2. Điều kiện L % i == 0 là bắt buộc.
  3. Lấy phần đầu t của s làm xâu cơ sở.
  4. Kiểm tra u (số được tạo bởi t lặp lại) ≤ s.
    • Nếu u > s, ta cần giảm giá trị xâu cơ sở. Xâu cơ sở giảm đi 1 đơn vị sẽ tạo ra số nhỏ hơn.
    • Nếu u ≤ s, đây là đáp án lớn nhất cho cấu trúc này.
  5. Nếu u > s, ta thử xâu cơ sở m-1. Lưu ý kiểm tra m-1 có bị mất chữ số đầu tiên hay không (ví dụ: 100 - 1 = 99, giảm từ 3 chữ số xuống 2 chữ số).

Lưu ý: Cần chú ý việc ép kiểu long long và xử lý chuỗi con khi số lặp tạo ra số lượng chữ số thay đổi.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(L^2) O(L) Quy hoạch động / Xây dựng theo độ dài xâu cơ sở
2 O(L^2) O(L) Tối ưu hóa Logic (Cải tiến)

Bài học kinh nghiệm

  • Bài toán có thể chia thành 2 trường hợp lớn dựa trên độ dài của X so với N: X ngắn hơn N hoặc X có cùng độ dài.
  • Nếu X cùng độ dài với N, X được xác định hoàn toàn bởi xâu cơ sở M. M phải là một tiền tố của N (hoặc nhỏ hơn).
  • Nếu xâu lặp từ M lớn hơn N, ta thử M - 1. Nếu M - 1 vẫn giữ nguyên số lượng chữ số, nó sẽ tạo ra số lặp nhỏ hơn N và là số lớn nhất cho độ dài này.

Lỗi thường gặp

  • Lỗi tràn số (overflow) khi nhân số: Cần kiểm tra độ dài chuỗi số sinh ra có vượt quá i không.
  • Quên kiểm tra số 0 ở đầu xâu cơ sở (ví dụ: M='01' là không hợp lệ).
  • Xử lý sai trường hợp giảm 1 đơn vị làm mất chữ số (ví dụ: M='10' (2 chữ số), M-1='9' (1 chữ số)).

Bình luận

Please read the guidelines before commenting.

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