Số Siêu May Mắn

Nguồn: Bài học viên hỏi Độ khó: Trung bình Vét cạn Sinh hoán vị Tìm kiếm nhị phân

Đề bài

Số siêu may mắn (input file: stdin, output file: stdout, time limit: 1000 ms, memory limit: 1256000 kB)

Số may mắn theo quan niệm của người Mỹ là số mà các chữ số của nó chỉ gồm số 4 và 7. Ví dụ: 47, 744, 4 là số may mắn còn 5, 17, 467 thì không phải. Số siêu may mắn là số may mắn có số lượng chữ số 4 và 7 bằng nhau. Ví dụ: 47, 7744, 474477 là số siêu may mắn còn 4, 744, 467 thì không phải.

Task: Hãy lập trình tìm số siêu may mắn nhỏ nhất lớn hơn số nguyên dương $n$ cho trước.

Input:

• Dòng đầu tiên chứa số nguyên dương $T$ là số testcase thỏa $1 \le T \le 100$.
• $T$ dòng tiếp theo chứa số nguyên dương $n$ thỏa $1 \le n \le 10^9$, $n$ không chứa chữ số 0 đứng trước.

Output:

• Ứng với mỗi testcase in ra số siêu may mắn nhỏ nhất lớn hơn hoặc bằng $n$, mỗi testcase in trên một dòng.

Ví dụ – input

2
4500
47

Ví dụ – output

4747
47

Lời mở đầu

Nay mình đi comment dạo thấy bài này cũng được nên đăng để anh em thử sức, sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ:

• $n = 4500$: các số siêu may mắn có 4 chữ số theo thứ tự tăng dần là 4477, 4747, 4774, 7447, 7474, 7744. Số 4477 nhỏ hơn 4500 nên bị loại, số đầu tiên $\ge 4500$ là 4747.
• $n = 47$: bản thân 47 đã là số siêu may mắn (một chữ số 4, một chữ số 7) nên in luôn 47.

Lưu ý nhỏ về đề

Phần Task ghi "lớn hơn $n$" nhưng phần Output và ví dụ thứ 2 ($n = 47$ in ra 47) cho thấy đề muốn số nhỏ nhất lớn hơn hoặc bằng $n$. Mình làm theo phần Output và ví dụ nha.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Tăng n tới khi gặp số siêu may mắn · TLECách 2Sinh 350 số + tìm kiếm nhị phân

Cách 1Làm theo đề: tăng n từng đơn vị – chậm

Cách nghĩ đầu tiên ai cũng nghĩ ra: viết hàm kiểm tra một số $x$ có phải số siêu may mắn không (tách từng chữ số, gặp chữ số khác 4 và 7 là loại ngay, cuối cùng so số lượng chữ số 4 và chữ số 7). Sau đó cứ cho $n$ tăng dần lên từng đơn vị cho tới khi hàm kiểm tra trả về đúng thì in ra.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

bool sieuMayMan(long long x){
    int c4 = 0, c7 = 0;
    while(x > 0){
        int d = x % 10;
        if(d == 4) c4++;
        else if(d == 7) c7++;
        else return false;
        x /= 10;
    }
    return c4 == c7;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        long long n;
        cin >> n;
        while(!sieuMayMan(n)) n++;
        cout << n << "\n";
    }
    return 0;
}

def sieu_may_man(x):
    c4 = c7 = 0
    while x > 0:
        d = x % 10
        if d == 4:
            c4 += 1
        elif d == 7:
            c7 += 1
        else:
            return False
        x //= 10
    return c4 == c7


T = int(input())
for _ in range(T):
    n = int(input())
    while not sieu_may_man(n):
        n += 1
    print(n)

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: mỗi lần kiểm tra mất $O(\log_{10} n)$, nhưng số lần phải tăng $n$ có thể rất lớn. Ví dụ $n = 777777778$: số siêu may mắn có 8 chữ số lớn nhất là 77774444 < $n$, nên đáp án phải nhảy lên 10 chữ số là 4444477777, tức là phải tăng khoảng $3.67 \cdot 10^9$ lần!

Không gian$O(1)$

Thời gian$O(\text{đáp án} - n)$

Bị TLE

Mình chạy thử C++ với đúng một test $n = 777777778$ đã mất khoảng 7 giây, trong khi đề có tới $T = 100$ test và giới hạn 1 giây. Cách này chỉ dùng được khi $n$ nhỏ (vài trăm nghìn trở xuống) – mình giữ lại để làm code vét cạn đối chiếu kết quả.

Nhớ dùng long long

$n \le 10^9$ nhưng đáp án có thể là 4444477777 – vượt quá giới hạn kiểu int (khoảng $2.1 \cdot 10^9$). Cả 2 cách đều phải lưu bằng long long.

Cách 2Sinh hết số siêu may mắn rồi tìm kiếm nhị phân – O(350 + T log 350)

Có bạn bình luận dưới bài là "dùng IDE online liệt kê hết các số $\le 10^9$ thoả mãn rồi tạo một mảng chứa hết các số đó, việc còn lại là duyệt mảng". Thật ra đó chính là ý tưởng đúng 👍, chỉ có điều mình không cần chép tay ra mảng, mà để chương trình tự sinh ngay lúc chạy. Lý do là các số siêu may mắn rất ít:

• Số siêu may mắn có số chữ số 4 bằng số chữ số 7 nên độ dài luôn chẵn: $2, 4, 6, 8, 10, \ldots$
• Với độ dài $2k$, ta chỉ cần chọn $k$ vị trí để đặt chữ số 4 (còn lại là 7), nên có $C_{2k}^{k}$ số.
• Vì $n \le 10^9$ và 4444477777 (10 chữ số) đã lớn hơn $10^9$, nên đáp án luôn có không quá 10 chữ số.

Độ dài	2	4	6	8	10	Tổng
Số lượng $C_{2k}^{k}$	2	6	20	70	252	350

Chỉ có 350 số thôi các bạn! Vậy mình sinh hết 350 số này vào mảng a theo thứ tự tăng dần, rồi với mỗi $n$ chỉ cần tìm phần tử đầu tiên của a mà $\ge n$ – đó chính là lower_bound (tìm kiếm nhị phân).

Sinh số bằng next_permutation

Với độ dài $2k$, mình bắt đầu từ xâu nhỏ nhất 44..477..7 ($k$ chữ số 4 rồi $k$ chữ số 7), rồi gọi next_permutation liên tục để đi qua tất cả các hoán vị khác nhau của xâu theo thứ tự từ điển tăng dần. Các xâu cùng độ dài thì so sánh từ điển cũng chính là so sánh giá trị số, và số ngắn hơn luôn nhỏ hơn số dài hơn ⇒ duyệt độ dài $2, 4, \ldots, 10$ và đẩy lần lượt vào mảng thì mảng a tự động đã được sắp xếp, không cần sort.

Hàm next_permutation biến xâu hiện tại thành hoán vị kế tiếp qua 3 bước:

1. Từ phải sang trái, tìm vị trí $i$ đầu tiên mà $s_i \lt s_{i+1}$ (ở đây tức là một chữ số 4 đứng ngay trước một chữ số 7). Không có vị trí nào như vậy ⇒ xâu đã là hoán vị lớn nhất (dạng 77..744..4), hàm trả về false và vòng lặp dừng.
2. Tìm vị trí $j \gt i$ xa nhất bên phải mà $s_j \gt s_i$ (một chữ số 7), đổi chỗ $s_i$ và $s_j$.
3. Đảo ngược đoạn phía sau vị trí $i$ để đoạn đó nhỏ nhất có thể.

Minh hoạ sinh hoán vị kế tiếp

Các bạn chọn độ dài rồi bấm Tiếp để xem từng bước next_permutation sinh ra các số siêu may mắn theo thứ tự tăng dần nhé:

Độ dài (chẵn, 2..8) n (tuỳ chọn, để tìm đáp án)

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    vector<long long> a;
    for(int len = 2; len <= 10; len += 2){
        string s = string(len / 2, '4') + string(len / 2, '7');
        do{
            a.push_back(stoll(s));
        }while(next_permutation(s.begin(), s.end()));
    }
    int T;
    cin >> T;
    while(T--){
        long long n;
        cin >> n;
        int k = lower_bound(a.begin(), a.end(), n) - a.begin();
        cout << a[k] << "\n";
    }
    return 0;
}

import sys
from bisect import bisect_left
from itertools import combinations

a = []
for length in range(2, 11, 2):
    # chọn length/2 vị trí đặt chữ số 4, các vị trí còn lại là 7
    for pos in combinations(range(length), length // 2):
        s = ['7'] * length
        for p in pos:
            s[p] = '4'
        a.append(int(''.join(s)))
a.sort()

data = sys.stdin.read().split()
T = int(data[0])
out = []
for i in range(1, T + 1):
    n = int(data[i])
    k = bisect_left(a, n)
    out.append(str(a[k]))
print('\n'.join(out))

Bản Python

Python không có sẵn next_permutation, nên mình dùng itertools.combinations để chọn $k$ vị trí đặt chữ số 4 (đúng với công thức $C_{2k}^{k}$ ở trên), sau đó sort lại cho chắc rồi dùng bisect_left – chính là lower_bound của Python.

Khung chạy tay bên dưới chạy đúng từng dòng code C++ ở trên. Phần sinh mảng có khoảng 700 bước (350 số), các bạn có thể bấm ⏭ để nhảy tới cuối rồi bấm ◀ Lùi để xem phần trả lời từng testcase nhé:

C++▶ Chạy tay từng dòng codeCách 2: sinh 350 số siêu may mắn bằng next_permutation, mỗi n dùng lower_bound.

Dữ liệu vào (stdin) – sửa thoải mái2 4500 47

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 vector<long long> a;

6 for(int len = 2; len <= 10; len += 2){

7 string s = string(len / 2, '4') + string(len / 2, '7');

8 do{

9 a.push_back(stoll(s));

10 }while(next_permutation(s.begin(), s.end()));

11 }

12 int T;

13 cin >> T;

14 while(T--){

15 long long n;

16 cin >> n;

17 int k = lower_bound(a.begin(), a.end(), n) - a.begin();

18 cout << a[k] << "\n";

19 }

20 return 0;

21}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng a chỉ có 350 phần tử – coi như $O(1)$.
• Thời gian: sinh 350 số mất cỡ $350 \times 10$ phép tính; mỗi testcase tìm kiếm nhị phân mất $O(\log 350) \approx 9$ phép so sánh. Tổng cộng $O(350 \cdot 10 + T \log 350)$ – chạy tức thì.

Không gian$O(350)$

Thời gian$O(T \log 350)$

Không cần lo truy cập ngoài mảng

Số lớn nhất trong mảng là 7777744444 > $10^9 \ge n$, nên lower_bound luôn tìm thấy và a[k] không bao giờ vượt ra ngoài mảng.

Ghi chú của mình: code C++ và Python của cách 2 đã được kiểm tra với 300 bộ test ngẫu nhiên ($n \le 10^9$, $T \le 100$, có nhiều $n$ sát các số may mắn), so với code vét cạn sinh tất cả số gồm chữ số 4, 7 – khớp hết; cách 1 cũng khớp trên 200 bộ test nhỏ ($n \le 10^5$). Với 100 test $n = 10^9$ và $n = 777777778$, cách 2 chạy chưa tới 0.01 giây (C++) và khoảng 0.04 giây (Python), còn cách 1 (C++) mất khoảng 7 giây chỉ cho một test $n = 777777778$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇