Rotate Numbers (NTHU OJ 12934)

Nguồn: NTHU Online Judge (12934) Độ khó: Dễ Xử lý xâu Số lớn Mô phỏng

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

12934 – Rotate Numbers (Xoay số)

Cho một số nguyên lớn, hãy xoay toàn bộ số đó đi $180^\circ$ và in ra kết quả. Ví dụ:

Tuy nhiên, đôi khi sau khi xoay, số đó trở nên vô nghĩa, ví dụ:

Ngoài ra, sau khi xoay số, nếu có các chữ số 0 ở đầu thì không in chúng ra, ví dụ:

Dữ liệu vào: Gồm một số nguyên $N$, $N$ có không quá 100 chữ số.

Kết quả: In ra số sau khi xoay $180^\circ$; nếu số sau khi xoay là vô nghĩa thì in ra No. Nhớ in thêm một dấu xuống dòng ở cuối đáp án.

12934 – Rotate Numbers

Description

Given a large integer, please rotate the whole number by $180^\circ$ and print out the result. For example:

However, sometimes after you rotate the number, it becomes meaningless, for example:

Besides, after you rotate the number, if there are some zeros in the front, do not print them out, for example:

Input

The input contains an integer $N$, which $N$ is no more than 100 digits.

Output

Output the 180 degree rotated number, if the rotated number is meaningless, output "No". Please add a newline at the end of your answer.

Sample Input

16809

Sample Output

60891

Lời mở đầu

Anh em nào đã học xử lý chuỗi ký tự thì thử sức với bài tập Rotate Numbers này xem, có hướng dẫn giải chi tiết của mình để anh em tham khảo 😇. Bài này là một bạn học viên nhắn tin hỏi mình (bài tập trên lớp của bạn ấy, nộp trễ là bị trừ còn 80% điểm 😅). Lúc đó mình vừa đi theo con coi chừng nó vừa tranh thủ code trên… note điện thoại cho bạn ấy luôn 🤣. Đề gốc tiếng Anh, mình đã dịch sang tiếng Việt ở tab đầu, bạn nào muốn đọc bản gốc thì bấm tab English nhé.

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

Làm rõ đề bài hơn cho các bạn: hãy tưởng tượng mình viết số lên tờ giấy rồi xoay ngược tờ giấy 180° (lộn đầu xuống). Khi đó thứ tự các chữ số bị đảo ngược, và mỗi chữ số cũng bị lộn ngược. Chỉ có 5 chữ số lộn ngược lại mà vẫn còn là chữ số (vẫn tính số 0 nhé):

000 → 0

111 → 1

666 → 9

888 → 8

999 → 6

22vô nghĩa

33vô nghĩa

44vô nghĩa

55vô nghĩa

77vô nghĩa

(Hàng dưới mỗi ô là chữ số được xoay thật 180° bằng CSS để các bạn nhìn cho rõ.) Còn các số 2, 3, 4, 5, 7 là những số đảo lại không được ⇒ chỉ cần số có một trong các chữ số này là in No. Và khi đảo lại xong, nếu số 0 đứng ở đầu thì ta không in ra thôi.

Ví dụ đề: $16809$ đọc ngược là $9, 0, 8, 6, 1$, lộn từng chữ số: $9 \to 6$, $0 \to 0$, $8 \to 8$, $6 \to 9$, $1 \to 1$ ⇒ 60891. Với $16980$: đọc ngược là $0, 8, 9, 6, 1$ ⇒ $08691$, bỏ số 0 ở đầu ⇒ 8691. Còn $14681$ có chữ số 4 ⇒ No.

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

Cách 1Kiểm tra trước, in sau · 2 lần duyệtCách 2Một vòng lặp duy nhất · O(n)

Cách 1Kiểm tra trước, in sau – 2 lần duyệt chuỗi

Bạn học viên đọc đề đã nhận ra được mấy ý rất đúng: số nhập vào tới 100 chữ số ⇒ không có kiểu số nguyên nào chứa nổi ⇒ dùng kiểu chuỗi (string); rồi tách từng ký tự ra xét các trường hợp: số 0, các số 1/6/8/9, và còn lại. Bài này chỉ là kỹ thuật duyệt chuỗi thôi, khá cơ bản. Hướng làm đầu tiên mình gợi ý cho bạn ấy như sau:

1. Xét chuỗi gốc ban đầu, duyệt qua từng ký tự số trong chuỗi. Nếu thấy có sự xuất hiện của các ký tự 2, 3, 4, 5, 7 – chỉ cần có 1 trong số mấy thằng này – thì lập tức xuất No và không xử lý tiếp nữa.
2. Nếu duyệt hết rồi mà không thấy mấy thằng này thì lúc này tiến hành xử lý chuỗi, in ra chuỗi đảo ngược thôi: xét từ cuối chuỗi đi lên. Nếu cuối chuỗi có số 0 thì cứ bỏ qua, xét lên thằng tiếp theo – chỉ bắt đầu từ thằng khác 0 đầu tiên tính từ cuối chuỗi lên, để loại đi các số 0 sẽ đứng đầu sau khi xoay.
3. Rồi cứ thế: nếu là 0 thì in ra 0, là 1 in ra 1, là 6 in ra 9, là 8 in ra 8, là 9 in ra 6. Sau cùng ta sẽ có chuỗi đảo ngượ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;
    int n = s.size();
    int flag = 1;
    int i = 0;
    while(i < n){
        if(s[i] == '2' || s[i] == '3' || s[i] == '4' || s[i] == '5' || s[i] == '7'){
            flag = 0;
            break;
        }
        i++;
    }
    if(flag == 0)
        cout << "No";
    else{
        for(i = n - 1; i >= 0; i--){
            if(s[i] != '0')
                break;
        }
        if(i < 0)
            cout << "0"; // N = 0
        while(i >= 0){
            if(s[i] == '0' || s[i] == '1' || s[i] == '8')
                cout << s[i];
            else if(s[i] == '6')
                cout << "9";
            else if(s[i] == '9')
                cout << "6";
            i--;
        }
    }
    cout << "\n";
    return 0;
}

s = input().strip()
n = len(s)
flag = 1
i = 0
while i < n:
    if s[i] in "23457":
        flag = 0
        break
    i += 1
if flag == 0:
    print("No")
else:
    i = n - 1
    while i >= 0 and s[i] == '0':  # bỏ các số 0 ở cuối chuỗi gốc
        i -= 1
    res = []
    if i < 0:
        res.append('0')  # N = 0
    while i >= 0:
        if s[i] in "018":
            res.append(s[i])
        elif s[i] == '6':
            res.append('9')
        elif s[i] == '9':
            res.append('6')
        i -= 1
    print("".join(res))

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

• Không gian: chỉ lưu chuỗi $s$ ⇒ $O(n)$ với $n$ là số chữ số.
• Thời gian: một vòng duyệt từ đầu đến cuối để kiểm tra, cộng một vòng duyệt từ cuối về đầu để in ⇒ $O(n)$, nhưng trường hợp số hợp lệ thì phải đi 2 lượt qua chuỗi.

Không gian$O(n)$

Thời gian$O(2n)$

Cẩn thận ký tự xuống dòng nếu đọc bằng fgets (C)

Code gốc mình gửi bạn ấy viết bằng C, đọc chuỗi bằng fgets. Hàm này giữ lại ký tự '\n' ở cuối chuỗi, nên vòng "bỏ các số 0 ở cuối" sẽ dừng ngay tại '\n' mà không bỏ được số 0 nào – mình chạy thử với 16980 (có xuống dòng) thì ra 08691 thay vì 8691. Trong bài mình chuyển sang C++ đọc bằng cin >> s (không dính '\n') nên không còn lỗi này. Bạn nào thích dùng C thì nhớ xoá '\n' ở cuối chuỗi trước khi xử lý nha. Ngoài ra mình thêm một dòng in 0 cho trường hợp $N = 0$ (code gốc in ra dòng trống).

Code này chưa gọn đâu

Làm theo cách này là chưa gọn đâu, có thể gọn hơn nữa chỉ dùng 1 vòng lặp duy nhất. Các bạn cố gắng suy nghĩ tối ưu xem trước khi đọc cách 2 nhé 😉.

Cách 2Một vòng lặp duy nhất – O(n)

Cách 1 chưa được tối ưu về mặt trình bày lẫn hiệu suất là bởi vì nó tách biệt 2 quy trình: kiểm tra xem chuỗi có hợp lệ hay không là 1 vòng lặp, rồi sau đó nếu hợp lệ lại tiếp tục duyệt 1 vòng lặp nữa để đi tìm ra chuỗi kết quả. Tức là trong trường hợp chuỗi nhập vào hoàn toàn hợp lệ thì code đó sẽ chạy 2 lần chuỗi: một lần từ đầu đến cuối để kiểm tra, và một lần từ cuối về đầu để in kết quả.

Mình có thể tối ưu lại chỉ cần 1 vòng lặp duy nhất vừa để kiểm tra xem chuỗi có hợp lệ hay không, vừa để nếu hợp lệ thì có luôn chuỗi kết quả – mỗi ký tự chỉ xét qua 1 lần duy nhất:

Tư tưởng

Tạo ra một chuỗi đáp án gọi là res, rồi đi xét từ cuối chuỗi gốc về đầu, với từng ký tự:

• Gặp ký tự không hợp lệ (2, 3, 4, 5, 7) ⇒ ngay lập tức dừng quá trình xét và kết luận No luôn.
• Ký tự hợp lệ ⇒ đưa ký tự đã xoay (1→1, 8→8, 6→9, 9→6) vào cuối res.
• Gặp ký tự '0' thì phải biết có lấy hay không: kiểm tra res lúc này đã có dữ liệu hay chưa. Chưa có dữ liệu ⇒ đây là số 0 sẽ đứng đầu ⇒ không đưa vào; đã có dữ liệu rồi ⇒ nhận nó vào.

Đi đến cuối cùng mà vẫn hợp lệ thì chuỗi đáp án in ra chính là res. Đơn giản vậy thôi!

Ở code này mình còn tận dụng luôn biến j (số ký tự đang có trong res) làm biến cờ hiệu (flag): gặp ký tự không hợp lệ thì gán j = -1, thay vì mất công tạo riêng biến flag như cách trước. Và điều kiện "res đã có dữ liệu chưa" chính là j != 0.

Minh hoạ

Em nhập số $N$ rồi bấm Tiếp để xem vòng lặp đi từ cuối chuỗi về đầu. Ô nhỏ bên dưới mỗi bước cho thấy chữ số đang xét khi bị lộn ngược 180° trông như thế nào:

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;
    char res[105];
    cin >> s;
    int j = 0; // j: số ký tự đã có trong res, j = -1 nghĩa là "No"
    for(int i = s.size() - 1; i >= 0; i--){
        if(s[i] == '2' || s[i] == '3' || s[i] == '4' || s[i] == '5' || s[i] == '7'){
            j = -1;
            break;
        }
        else if(s[i] == '0'){
            if(j != 0)
                res[j++] = s[i];
        }
        else{
            if(s[i] == '1' || s[i] == '8')
                res[j++] = s[i];
            else if(s[i] == '6')
                res[j++] = '9';
            else if(s[i] == '9')
                res[j++] = '6';
        }
    }
    if(j == -1)
        cout << "No";
    else if(j == 0)
        cout << "0"; // N = 0
    else{
        res[j] = '\0';
        cout << res;
    }
    cout << "\n";
    return 0;
}

s = input().strip()
res = []  # chuỗi đáp án
ok = True
for i in range(len(s) - 1, -1, -1):
    c = s[i]
    if c in "23457":
        ok = False
        break
    elif c == '0':
        if len(res) != 0:  # res đã có dữ liệu thì mới nhận số 0
            res.append(c)
    elif c == '1' or c == '8':
        res.append(c)
    elif c == '6':
        res.append('9')
    elif c == '9':
        res.append('6')
if not ok:
    print("No")
elif len(res) == 0:
    print("0")  # N = 0
else:
    print("".join(res))

C++▶ Chạy tay từng dòng codeCách 2: một vòng lặp từ cuối chuỗi, j vừa là độ dài res vừa là cờ hiệu (j = -1 ⇒ No).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 string s;

6 char res[105];

7 cin >> s;

8 int j = 0; // j: số ký tự đã có trong res, j = -1 nghĩa là "No"

9 for(int i = s.size() - 1; i >= 0; i--){

10 if(s[i] == '2' || s[i] == '3' || s[i] == '4' || s[i] == '5' || s[i] == '7'){

11 j = -1;

12 break;

13 }

14 else if(s[i] == '0'){

15 if(j != 0)

16 res[j++] = s[i];

17 }

18 else{

19 if(s[i] == '1' || s[i] == '8')

20 res[j++] = s[i];

21 else if(s[i] == '6')

22 res[j++] = '9';

23 else if(s[i] == '9')

24 res[j++] = '6';

25 }

26 }

27 if(j == -1)

28 cout << "No";

29 else if(j == 0)

30 cout << "0"; // N = 0

31 else{

32 res[j] = '\0';

33 cout << res;

34 }

35 cout << "\n";

36 return 0;

37}

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à mảng res ⇒ $O(n)$.
• Thời gian: mỗi ký tự chỉ xét qua 1 lần duy nhất, gặp ký tự xấu là dừng luôn ⇒ $O(n)$, tối ưu hơn code ban đầu nhiều cả về hiệu suất lẫn cách trình bày.

Không gian$O(n)$

Thời gian$O(n)$

Một chú ý nhỏ: N = 0

Đề không nói rõ, nhưng nếu $N = 0$ thì xoay lại vẫn là $0$. Vòng lặp sẽ bỏ qua số 0 này (vì lúc đó res chưa có dữ liệu) nên $j$ vẫn bằng 0 – code gốc của mình khi đó in ra dòng trống. Trong bài mình thêm nhánh else if(j == 0) in 0 cho chắc ăn.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên (độ dài từ 1 đến 100 chữ số, có số chỉ gồm 0/1/6/8/9, số có chữ số xấu, số có nhiều số 0 ở cuối, và $N = 0$), so với code vét cạn "lộn từng chữ số rồi bỏ số 0 ở đầu" – khớp hết. Hai code C gốc (dùng fgets) mình cũng chạy lại: code một vòng lặp cho kết quả đúng với mọi test trừ $N = 0$; code hai vòng lặp bị dính ký tự '\n' như mình nói ở cách 1 – bản trong bài đã sửa cả hai chỗ.

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 😇