Biến Đổi Số

Nguồn: Bài tập do bạn đọc gửi Độ khó: Trung bình Số học Chia hết Tham lam Đếm phân phối

Đề bài

Biến đổi số

Tuấn rất thích số là bội số của 45. Vì vậy cứ thấy bất kỳ một số nguyên dương $N$ nào Tuấn cũng cố gắng biến đổi số đó bằng cách thay đổi vị trí các chữ số đó để được một bội số của 45.

Cho trước số nguyên dương $N$, hãy cho biết có thể biến đổi số đó để hợp với sở thích của Tuấn được không?

Input:

• Dòng duy nhất chứa số nguyên dương $N$. Số chữ số của $N$ không quá $10^4$ ký tự.

Output:

• Nếu có thể biến đổi được thì hãy in ra số lớn nhất thỏa mãn bài toán, ngược lại thì in $-1$.

Giới hạn thời gian: 1 giây.

Ví dụ 1 – input

45

Ví dụ 1 – output

45

Ví dụ 2 – input

153

Ví dụ 2 – output

315

Ví dụ 3 – input

555554444

Ví dụ 3 – output

-1

Lời mở đầu

Nay mình đi comment dạo thấy bài này thú vị nè: một bạn hỏi ý tưởng vì đề chỉ cho 1 giây mà số $N$ có tới $10^4$ chữ số. Nhìn qua tưởng phải thử hết các hoán vị, nhưng thật ra chỉ cần nhớ lại 2 dấu hiệu chia hết học từ hồi cấp 2 là bài toán trở nên rất nhẹ nhàng 😇.

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

Giải thích ví dụ cho bạn nào chưa hiểu đề: ta được phép đổi chỗ các chữ số của $N$ (giữ nguyên bộ chữ số, chỉ xếp lại thứ tự), cần tìm cách xếp cho ra số lớn nhất chia hết cho 45.

• $N = 45$: bản thân $45$ đã chia hết cho 45, còn $54$ thì không ⇒ đáp án $45$.
• $N = 153$: các cách xếp là $135, 153, 315, 351, 513, 531$. Chia hết cho 45 có $135 = 45 \cdot 3$ và $315 = 45 \cdot 7$, lớn nhất là $315$.
• $N = 555554444$: không có cách xếp nào chia hết cho 45 ⇒ $-1$.

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

Cách 1Vét cạn hoán vị · chỉ được với N rất ngắnCách 2Dấu hiệu chia hết cho 5 và 9 · O(L)

Cách 1Vét cạn tất cả hoán vị – O(L! · L)

Làm theo đúng đề: thử mọi cách sắp xếp các chữ số. Để lấy được số lớn nhất thì mẹo là sắp xếp các chữ số giảm dần trước, rồi dùng prev_permutation để sinh các hoán vị theo thứ tự giảm dần. Hoán vị đầu tiên chia hết cho 45 gặp được chính là đáp án, dừng luôn. Gọi $L$ là số chữ số của $N$.

Để kiểm tra chia hết thì không thể đổi cả xâu sang số (có thể tới $10^4$ chữ số), ta tính phần dư dần dần: $r = (r \cdot 10 + \text{chữ số}) \bmod 45$. Ngoài ra bỏ qua hoán vị có số 0 đứng đầu (thật ra hoán vị như vậy không bao giờ là lớn nhất, nhưng cứ kiểm cho chắc).

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(){
    string s;
    cin >> s;
    sort(s.begin(), s.end(), greater<char>());
    do{
        int r = 0;
        for(int i = 0; i < (int)s.length(); ++i){
            r = (r * 10 + (s[i] - '0')) % 45;
        }
        if(r == 0 && s[0] != '0'){
            cout << s;
            return 0;
        }
    }while(prev_permutation(s.begin(), s.end()));
    cout << -1;
    return 0;
}

from itertools import permutations

s = sorted(input().strip(), reverse=True)
ans = "-1"
for p in permutations(s):
    if p[0] != '0' and int(''.join(p)) % 45 == 0:
        ans = ''.join(p)
        break
print(ans)

Không gian$O(L)$

Thời gian$O(L! \cdot L)$

Chỉ chạy được với N rất ngắn

Số hoán vị là $L!$: $10! \approx 3.6 \cdot 10^6$ còn chạy được, nhưng $12! \approx 4.8 \cdot 10^8$ đã mất cỡ 1.7 giây (mình đo với $N = 123456789112$, không có đáp án), còn $L = 10^4$ thì là chuyện không tưởng. Cách này chỉ để hiểu đề và làm code kiểm tra thôi nha.

Cách 2Dấu hiệu chia hết cho 5 và 9 – O(L)

Nhận xét: 45 = 5 · 9

Vì $45 = 5 \cdot 9$ và $5$, $9$ nguyên tố cùng nhau nên: một số chia hết cho 45 khi và chỉ khi nó chia hết cho cả 5 và 9. Mà hai dấu hiệu này thì quá quen thuộc:

• Chia hết cho 9 ⇔ tổng các chữ số chia hết cho 9. Đổi chỗ các chữ số thì tổng không đổi ⇒ điều kiện này hoặc đúng với mọi cách xếp, hoặc sai với mọi cách xếp. Chỉ cần kiểm tra một lần!
• Chia hết cho 5 ⇔ chữ số cuối cùng là 0 hoặc 5. Vậy $N$ phải có ít nhất một chữ số 0 hoặc 5 để đặt xuống cuối.

Một trong hai điều kiện không thoả ⇒ in $-1$. Ví dụ $555554444$: tổng chữ số là $5 \cdot 5 + 4 \cdot 4 = 41$, không chia hết cho 9 ⇒ $-1$.

Xếp sao cho lớn nhất

Khi đã chắc chắn có đáp án, ta tham lam:

1. Chọn chữ số cuối: nếu có chữ số 0 thì đặt 0 xuống cuối, không có 0 thì mới đặt 5. Lý do: phần phía trước gồm các chữ số còn lại; nếu đặt 0 ở cuối thì chữ số 5 được ở phía trước, còn đặt 5 ở cuối thì chữ số 0 lại nằm phía trước. Hai số dài bằng nhau, bộ chữ số phía trước chỉ khác nhau đúng một chữ số (5 so với 0) ⇒ đặt 0 ở cuối luôn cho số lớn hơn.
2. Các chữ số còn lại xếp giảm dần (chữ số lớn đứng trước) ⇒ được số lớn nhất.

N	0 ở cuối	5 ở cuối
1530	5310	3105
50040	54000	40005

Thuật toán

1. Đếm số lần xuất hiện của từng chữ số vào mảng cnt[0..9] (đếm phân phối) và tính tổng chữ số sum.
2. Nếu sum % 9 != 0 hoặc không có chữ số 0 lẫn 5 ⇒ in $-1$.
3. last = 0 nếu có chữ số 0, ngược lại = 5; bớt cnt[last] đi 1.
4. Ghép các chữ số từ 9 về 0 (mỗi chữ số $d$ lặp cnt[d] lần), cuối cùng ghép thêm last.

Có bị số 0 đứng đầu không?

$N$ là số nguyên dương nên có ít nhất một chữ số khác 0. Khi xếp giảm dần thì chữ số lớn nhất đứng đầu ⇒ không bao giờ có số 0 ở đầu. Ví dụ $N = 90$ ⇒ đáp án $90$.

Không đọc N vào long long

$N$ có tới $10^4$ chữ số nên phải đọc vào xâu. Tổng chữ số tối đa $9 \cdot 10^4$ nên dùng int thoải mái.

Minh hoạ

Em nhập $N$ rồi bấm Tiếp để xem từng bước: đếm chữ số, kiểm tra hai dấu hiệu, chọn chữ số cuối, rồi ghép chữ số từ 9 về 0:

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(){
    string s;
    cin >> s;
    int cnt[10] = {0};
    int sum = 0;
    for(int i = 0; i < (int)s.length(); ++i){
        cnt[s[i] - '0']++;
        sum += s[i] - '0';
    }
    if(sum % 9 != 0 || (cnt[0] == 0 && cnt[5] == 0)){
        cout << -1;
        return 0;
    }
    int last = (cnt[0] > 0) ? 0 : 5;
    cnt[last]--;
    string res = "";
    for(int d = 9; d >= 0; --d){
        res += string(cnt[d], char('0' + d));
    }
    res += char('0' + last);
    cout << res;
    return 0;
}

s = input().strip()
cnt = [0] * 10
total = 0
for c in s:
    cnt[int(c)] += 1
    total += int(c)
if total % 9 != 0 or (cnt[0] == 0 and cnt[5] == 0):
    print(-1)
else:
    last = 0 if cnt[0] > 0 else 5
    cnt[last] -= 1
    res = []
    for d in range(9, -1, -1):
        res.append(str(d) * cnt[d])
    res.append(str(last))
    print(''.join(res))

C++▶ Chạy tay từng dòng codeĐếm chữ số, kiểm tra tổng chia hết 9 và có 0/5, rồi ghép chữ số từ 9 về 0 và đặt 0 (hoặc 5) ở cuối.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 string s;

6 cin >> s;

7 int cnt[10] = {0};

8 int sum = 0;

9 for(int i = 0; i < (int)s.length(); ++i){

10 cnt[s[i] - '0']++;

11 sum += s[i] - '0';

12 }

13 if(sum % 9 != 0 || (cnt[0] == 0 && cnt[5] == 0)){

14 cout << -1;

15 return 0;

16 }

17 int last = (cnt[0] > 0) ? 0 : 5;

18 cnt[last]--;

19 string res = "";

20 for(int d = 9; d >= 0; --d){

21 res += string(cnt[d], char('0' + d));

22 }

23 res += char('0' + last);

24 cout << res;

25 return 0;

26}

ChậmVừaNhanhRất nhanh

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

• Không gian: xâu $N$ và xâu kết quả đều dài $L$, mảng đếm chỉ 10 phần tử ⇒ $O(L)$.
• Thời gian: duyệt xâu một lần để đếm, rồi ghép lại $L$ chữ số ⇒ $O(L)$. Với $L = 10^4$ thì chạy tức thì nha các bạn. Đây cũng chính là ý tưởng "sắp xếp giảm dần" nhưng làm bằng đếm phân phối nên không tốn $O(L \log L)$.

Không gian$O(L)$

Thời gian$O(L)$

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 600 bộ test ngẫu nhiên ($N$ tới 7 chữ số, nhiều bộ chỉ gồm các chữ số 0, 5, 9 để có đáp án), so với code vét cạn lấy max trên tập mọi hoán vị – khớp hết. Với $N$ có $10^4$ chữ số: cách 2 bản C++ chạy khoảng 0.005 giây, bản Python khoảng 0.02 giây.

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 😇