Tóm tắt đề bài

Cho một danh sách gồm \(n\) số nguyên dương. Một số được gọi là "mã đẹp hợp lệ" nếu thỏa mãn đồng thời hai điều kiện:

1. Chữ số nhỏ nhất của nó (\(m\)) khác \(0\).
2. Chữ số lớn nhất của nó (\(M\)) chia hết cho chữ số nhỏ nhất (\(m\)).

Yêu cầu: Đếm số lượng mã đẹp hợp lệ trong danh sách đã cho.

Phân tích

• Điều kiện: \(n \leq 10^5\), các số \(a_i\) có giá trị lên đến \(10^{18}\).
• Nhận xét:
  • Vì \(a_i \leq 10^{18}\), mỗi số có tối đa 19 chữ số. Việc tách các chữ số của một số để tìm \(M\) và \(m\) diễn ra rất nhanh.
  • Ta có thể xử lý từng số một cách độc lập.
  • Với mỗi số \(a_i\), ta cần:
    • Tách từng chữ số của \(a_i\).
    • Tìm chữ số lớn nhất \(M\) và chữ số nhỏ nhất \(m\).
    • Kiểm tra điều kiện \(m \neq 0\) và \(M \pmod m == 0\).

Cách làm đơn giản (Brute Force)

Thực tế, bài toán này không có cách tiếp cận nào "ngây thơ" hơn việc duyệt qua từng số và kiểm tra. Tuy nhiên, một cách làm đơn giản cho người mới bắt đầu là chuyển số thành chuỗi (string) để dễ dàng duyệt qua từng ký tự.

Ý tưởng

1. Duyệt qua từng số trong danh sách.
2. Chuyển số đó thành chuỗi ký tự.
3. Duyệt qua từng ký tự trong chuỗi để tìm ký tự lớn nhất và nhỏ nhất.
4. Chuyển các ký tự đó ngược lại thành số và kiểm tra điều kiện.

Độ phức tạp

• Thời gian: \(O(n \times \log_{10}(a_i))\), trong đó \(\log_{10}(a_i)\) là số chữ số của \(a_i\). Với \(n=10^5\) và số chữ số tối đa là 19, tổng số thao tác khoảng \(1.9 \times 10^6\), hoàn toàn nằm trong giới hạn thời gian (thường là \(10^8\) thao tác/giây).
• Đánh giá: Cách tiếp cận này đủ tốt để đạt điểm tối đa.

Code Brute Force

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

int main() {
    int n;
    cin >> n;
    int count = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int min_digit = 9, max_digit = 0;
        for (char c : s) {
            int digit = c - '0';
            if (digit < min_digit) min_digit = digit;
            if (digit > max_digit) max_digit = digit;
        }
        if (min_digit != 0 && max_digit % min_digit == 0) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

n = int(input())
a = input().split()
count = 0
for s in a:
    digits = [int(d) for d in s]
    m = min(digits)
    M = max(digits)
    if m != 0 and M % m == 0:
        count += 1
print(count)

Hướng giải quyết (Tối ưu)

Nhận xét

Thay vì chuyển sang chuỗi, ta có thể sử dụng các phép toán số học (% 10 để lấy chữ số cuối và / 10 để bỏ chữ số cuối) để tách các chữ số. Cách này thường nhanh hơn một chút về mặt hằng số so với xử lý chuỗi.

Thuật toán

1. Đọc số lượng phần tử \(n\).
2. Sử dụng một biến ans để đếm số mã đẹp hợp lệ.
3. Với mỗi số \(x\) trong đầu vào:
   • Khởi tạo \(min\_val = 10\) và \(max\_val = -1\).
   • Trong khi \(x > 0\):
     • Lấy chữ số cuối \(d = x \pmod{10}\).
     • Cập nhật \(min\_val = \min(min\_val, d)\) và \(max\_val = \max(max\_val, d)\).
     • Loại bỏ chữ số cuối: \(x = x / 10\).
   • Sau khi lấy hết các chữ số, kiểm tra nếu \(min\_val > 0\) và \(max\_val \pmod{min\_val} == 0\) thì tăng ans.
4. In ra ans.

Độ phức tạp

• Thời gian: \(O(n \times \text{số chữ số})\), xấp xỉ \(O(n \times 18)\).
• Bộ nhớ: \(O(1)\) nếu đọc và xử lý từng số, hoặc \(O(n)\) nếu lưu cả mảng.

Code tham khảo

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

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    int valid_count = 0;

    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;

        int m = 10; // Chữ số nhỏ nhất
        int M = -1; // Chữ số lớn nhất

        long long temp = a;
        while (temp > 0) {
            int digit = temp % 10;
            if (digit < m) m = digit;
            if (digit > M) M = digit;
            temp /= 10;
        }

        // Kiểm tra điều kiện mã đẹp hợp lệ
        if (m != 0 && M % m == 0) {
            valid_count++;
        }
    }

    cout << valid_count << endl;

    return 0;
}

import sys

def solve():
    # Đọc toàn bộ dữ liệu từ đầu vào để xử lý nhanh hơn
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    a = input_data[1:]

    valid_count = 0
    for i in range(n):
        s = a[i]
        # Chuyển từng ký tự thành số nguyên để tìm min, max
        digits = [int(d) for d in s]

        m = min(digits)
        M = max(digits)

        # Kiểm tra m khác 0 và M chia hết cho m
        if m != 0 and M % m == 0:
            valid_count += 1

    print(valid_count)

if __name__ == "__main__":
    solve()