Đổi 1 Chữ Số Để Chia Hết Cho 3

Nguồn: Bài tập sưu tầm Độ khó: Dễ Số học Chia lấy dư Xử lý xâu

Đề bài

Đổi 1 chữ số để chia hết cho 3

Cho số nguyên dương $n$ có không quá 10 chữ số. Hãy xác định số nguyên lớn nhất $m$ chia hết cho 3 và khác $n$ ở đúng một chữ số.

Ví dụ, $n = 123$ thì $m$ sẽ là $723$.

INPUT: Vào từ thiết bị nhập chuẩn gồm một dòng chứa số nguyên $n$ có không quá 10 chữ số và không chứa các số 0 không có nghĩa.

OUTPUT: Đưa ra thiết bị xuất chuẩn số nguyên $m$ tìm được.

Input

123

Output

723

Lời mở đầu

Trong quá trình đi comment dạo mình thấy bài tập này cũng hay nên chia sẻ đề lên đây để anh em cùng xem và thử sức nhé, rồi bên dưới mình đưa ra hướng giải quyết theo cách làm của mình để anh em cùng tham khảo và thảo luận hen. Hy vọng mang đến giá trị cho anh em 😇.

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ụ: với $n = 123$, ta chỉ được đổi đúng một chữ số (đổi thành chữ số khác nó). Đổi chữ số hàng trăm $1 \to 7$ được $723$, tổng chữ số $7 + 2 + 3 = 12$ chia hết cho 3. Không có cách đổi nào cho số lớn hơn: đổi $1 \to 8$ hay $1 \to 9$ thì tổng chữ số là $13$, $14$, không chia hết cho 3 ⇒ đáp án $723$.

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

Cách 1Xử lý bằng chuỗi · O(N²), N ≤ 10Cách 2Tách chữ số bằng % 10 · O(N)

Cách 1Đọc vào dạng chuỗi rồi thử thay từng chữ số – O(N²), N ≤ 10

Bài này có thể giải quyết theo cách tối ưu, gọn lẹ và dễ dàng nếu chúng ta đọc dữ liệu đầu vào ở dạng chuỗi rồi xử lý. Lúc này số đầu vào muốn dài bao nhiêu chữ số cũng đều không vấn đề gì.

Tư tưởng giải quyết bài này khá đơn giản: để một số chia hết cho 3 thì tổng các chữ số của nó phải chia hết cho 3.

• Đầu tiên ta tính tổng sum tất cả các chữ số ban đầu.
• Khi xét riêng từng chữ số c, ta lấy sum - c (tổng các chữ số còn lại), rồi thay chữ số đó bằng chữ số lớn nhất khác nó (thử $j$ từ 9 về 0, gặp thằng đầu tiên thoả thì dừng) sao cho sum - c + j chia hết cho 3. Thế là được một chuỗi số mới.
• Lặp lại quy trình trên đúng $N$ lần, với $N$ là độ dài chuỗi số, mỗi lần được một chuỗi số mới. Trong các chuỗi số mới đó, chuỗi nào lớn nhất thì đó là đáp án.

Vì sao dùng chuỗi lại tiện?

Chuỗi truy xuất được vào một vị trí bất kỳ, nên ta nhanh chóng xét từng chữ số và thay nó bằng chữ số khác. Còn để tìm chuỗi lớn nhất, phép so sánh chuỗi cũng đúng theo nguyên tắc so sánh số: xét từ trái qua phải từng ký tự, ở ký tự nào lớn hơn ký tự kia thì kết luận ngay. Các chuỗi mới đều cùng độ dài với $n$ nên so sánh chuỗi cũng chính là so sánh số.

Không lo chữ số 0 ở đầu

Các chữ số $j$ thoả điều kiện là những chữ số có cùng số dư khi chia 3 (nhóm $\{0, 3, 6, 9\}$, $\{1, 4, 7\}$ hoặc $\{2, 5, 8\}$). Bỏ đi chính chữ số $c$ thì mỗi nhóm vẫn còn ít nhất 2 chữ số, nên chữ số lớn nhất được chọn luôn $\ge 4$, không bao giờ là 0. Nhờ vậy cũng chắc chắn luôn có đáp án.

Minh hoạ

Em nhập $n$ rồi bấm Tiếp để xem từng vị trí được thay bằng chữ số nào và Max được cập nhật ra sao:

n

Ví dụ nhanh:

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

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    string Max = "0";
    int sum = 0;
    for(int i = 0; i < (int)s.length(); i++) {
        sum += s[i] - 48;
    }
    for(int i = 0; i < (int)s.length(); i++) {
        int c = s[i] - 48;
        for(int j = 9; j >= 0; j--) {
            if(j != c && (sum - c + j) % 3 == 0) {
                string temp = s;
                temp[i] = j + 48;
                if(temp > Max)
                    Max = temp;
                break;
            }
        }
    }
    cout << Max;
    return 0;
}

s = input().strip()
Max = "0"
total = sum(int(ch) for ch in s)
for i in range(len(s)):
    c = int(s[i])
    for j in range(9, -1, -1):
        if j != c and (total - c + j) % 3 == 0:
            temp = s[:i] + str(j) + s[i + 1:]
            if temp > Max:
                Max = temp
            break
print(Max)

C++▶ Chạy tay từng dòng codeĐọc n dạng chuỗi, thay từng chữ số bằng chữ số lớn nhất khác nó để tổng chia hết cho 3.

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

Dữ liệu mẫu:

1#include <iostream>

2#include <string>

3using namespace std;

4

5int main() {

6 string s;

7 cin >> s;

8 string Max = "0";

9 int sum = 0;

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

11 sum += s[i] - 48;

12 }

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

14 int c = s[i] - 48;

15 for(int j = 9; j >= 0; j--) {

16 if(j != c && (sum - c + j) % 3 == 0) {

17 string temp = s;

18 temp[i] = j + 48;

19 if(temp > Max)

20 Max = temp;

21 break;

22 }

23 }

24 }

25 cout << Max;

26 return 0;

27}

ChậmVừaNhanhRất nhanh

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

• Không gian: chuỗi $s$ và vài chuỗi tạm cùng độ dài ⇒ $O(N)$ với $N$ là số chữ số.
• Thời gian: với mỗi vị trí, vòng $j$ chạy tối đa vài lần (chưa tới 10), rồi sao chép, so sánh chuỗi $O(N)$ ⇒ $O(N^2)$ trên lý thuyết, nhưng $N \le 10$ nên chạy tức thì. Nếu chỉ tính số lần thử chữ số thì là $O(10 \cdot N)$.

Không gian$O(N)$

Thời gian$O(N^2)$, $N \le 10$

Cách 2Không dùng chuỗi: tách chữ số bằng % 10 – O(N)

Còn nếu giả sử bạn nào chưa học xử lý chuỗi thì bài này vẫn xử lý được theo cách bình thường, bởi vì số ban đầu không quá 10 chữ số, vẫn nằm trong phạm vi lưu trữ của kiểu long long. Lúc này chỉ cần kiến thức ở mức vòng lặp là giải quyết được, nhưng tất nhiên sẽ phải xử lý nhiều hơn so với dùng chuỗi.

Tư tưởng vẫn y như trên, nhưng phức tạp ở chỗ khi muốn đi vào một chữ số để thay thế thì không gọi thẳng tới được như chuỗi, mà phải tách từng chữ số ra, rồi khi tìm được chữ số thay thế thì phải tính toán để cập nhật lại kết quả.

Ví dụ xét số $123$: đầu tiên lặp qua từng chữ số bằng cách liên tục % 10, / 10 đến khi về 0 thì dừng (nhớ tạo biến khác lưu lại giá trị ban đầu nhé, vì chia kiểu này làm giá trị bị thay đổi, sau cùng là 0), ta được tổng là $6$. Rồi xét vào từng chữ số:

• Chữ số $3$ (hàng đơn vị): $6 - 3 = 3$ là tổng các chữ số còn lại. Xét các chữ số từ 9 về 0 khác 3, gặp thằng đầu tiên thoả là $9$ ⇒ số mới $129$. Làm sao để nó hiểu là $129$? Đơn giản: $9$ lớn hơn $3$ là $6$ đơn vị, đằng sau nó không có chữ số nào nên $6 \cdot 10^0 = 6$ ⇒ $123 + 6 = 129$.
• Chữ số $2$ thay bằng $8$: lớn hơn $6$ đơn vị, đằng sau có 1 chữ số nên $6 \cdot 10^1 = 60$ ⇒ $123 + 60 = 183$.
• Chữ số $1$ thay bằng $7$: lớn hơn $6$ đơn vị, đằng sau có 2 chữ số nên $6 \cdot 10^2 = 600$ ⇒ $123 + 600 = 723$.

Mỗi lần tìm được số mới ta so sánh với Max, sau cùng đáp án là $723$.

Không phải lúc nào cũng cộng thêm

Giả sử số hiện tại là $999$: chữ số 9 cuối cùng chỉ có thể thay bằng chữ số nhỏ hơn, lớn nhất là $6$, nhỏ hơn $3$ đơn vị ⇒ $999 - 3 \cdot 10^0 = 996$. Tương tự $999 - 3 \cdot 10^1 = 969$ và $999 - 3 \cdot 10^2 = 699$. Max trong các số đó là 996. Vậy phải xét cả 2 trường hợp: chữ số mới lớn hơn thì cộng, nhỏ hơn thì trừ.

Không cần hàm pow

Có thể dùng hàm pow để tính lượng cần cộng/trừ, nhưng sẽ tốt hơn nếu ban đầu có một biến x = 1, xét xong mỗi chữ số thì nhân x lên 10 để lần lượt là $1, 10, 100, 1000\ldots$ Lấy phần chênh lệch giữa 2 chữ số nhân với x là được. Vừa nhanh, vừa tránh sai số của pow (vốn trả về số thực).

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

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long Max = -1;
    int sz = 0;
    long long temp = n;
    if(temp == 0) {
        sz++;
    }
    int sum = 0;
    while(temp) {
        sum += temp % 10;
        temp /= 10;
        sz++;
    }
    long long x = 1;
    for(int i = 1; i <= sz; i++) {
        int num = (n / x) % 10;
        for(int j = 9; j >= 0; j--) {
            if(j != num && (sum - num + j) % 3 == 0) {
                long long res;
                if(j > num) {
                    res = n + (j - num) * x;
                }
                else {
                    res = n - (num - j) * x;
                }
                if(res > Max) {
                    Max = res;
                }
                break;
            }
        }
        x *= 10;
    }
    cout << Max;
    return 0;
}

n = int(input())
Max = -1
total = 0
sz = 0
temp = n
if temp == 0:
    sz += 1
while temp:
    total += temp % 10
    temp //= 10
    sz += 1
x = 1
for i in range(1, sz + 1):
    num = (n // x) % 10
    for j in range(9, -1, -1):
        if j != num and (total - num + j) % 3 == 0:
            if j > num:
                res = n + (j - num) * x
            else:
                res = n - (num - j) * x
            if res > Max:
                Max = res
            break
    x *= 10
print(Max)

C++▶ Chạy tay từng dòng codeTách chữ số bằng % 10, x = 1, 10, 100..., cộng hoặc trừ phần chênh lệch nhân x.

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

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main() {

5 long long n;

6 cin >> n;

7 long long Max = -1;

8 int sz = 0;

9 long long temp = n;

10 if(temp == 0) {

11 sz++;

12 }

13 int sum = 0;

14 while(temp) {

15 sum += temp % 10;

16 temp /= 10;

17 sz++;

18 }

19 long long x = 1;

20 for(int i = 1; i <= sz; i++) {

21 int num = (n / x) % 10;

22 for(int j = 9; j >= 0; j--) {

23 if(j != num && (sum - num + j) % 3 == 0) {

24 long long res;

25 if(j > num) {

26 res = n + (j - num) * x;

27 }

28 else {

29 res = n - (num - j) * x;

30 }

31 if(res > Max) {

32 Max = res;

33 }

34 break;

35 }

36 }

37 x *= 10;

38 }

39 cout << Max;

40 return 0;

41}

ChậmVừaNhanhRất nhanh

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

• Không gian: vài biến ⇒ $O(1)$.
• Thời gian: tách chữ số $O(N)$, mỗi chữ số thử tối đa vài giá trị $j$ ⇒ $O(N)$, với $N \le 10$ thì tức thì.

Không gian$O(1)$

Thời gian$O(N)$

Nhớ dùng long long

$n$ có thể có 10 chữ số, tới $9\,999\,999\,999$, vượt giới hạn của int (khoảng $2.1 \cdot 10^9$), nên $n$, temp, x, res, Max đều phải là long long.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với mọi $n$ từ 1 đến 1000 cùng 400 số ngẫu nhiên tới 10 chữ số (và các biên $9\,999\,999\,999$, $1\,000\,000\,000$), so với code vét cạn thử đổi mọi chữ số thành mọi giá trị – khớp hết.

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 😇