Siêu đối xứng (2022TPB02) (Tin học trẻ TP Đà Nẵng 2021-2022 – Bảng B)

Nguồn: Tin học trẻ TP Đà Nẵng 2021-2022 (Bảng B) · LQDOJ Độ khó: Dễ Xử lý xâu Vét cạn Tìm quy luật

Đề bài

Bài 2. Siêu đối xứng (2.0 điểm) – Hội thi Tin học trẻ cấp thành phố Đà Nẵng, năm học 2021-2022, đề thi Bảng B – cấp THCS.

Một số nguyên dương được gọi là siêu đối xứng nếu tất cả các chữ số của nó giống nhau. Chẳng hạn số $777$ hoặc $4444$ là các số nguyên dương siêu đối xứng.

Nhập từ bàn phím một số nguyên dương $x$. Hãy tìm và in ra màn hình số nguyên dương $y$ nhỏ nhất sao cho tổng $x + y$ là một số nguyên dương siêu đối xứng.

Giới hạn:

• Có $50\%$ test ứng với $x \le 10^6$;
• $30\%$ test ứng với $10^6 \lt x \le 10^9$;
• $20\%$ test ứng với $10^9 \le x \le 10^{16}$.

Ví dụ – input

45

Ví dụ – output

10

Giải thích: $45 + 10 = 55$.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên 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 😇.

Trước khi vào bài, các bạn nhớ giúp mình chuyện giới hạn thời gian: với các hệ thống chấm bài giới hạn 1 giây, toàn bài chỉ nên lặp cỡ $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất $10^8$ lần (lúc này hên xui). Ngưỡng này là cho C/C++; Python, Java, C# chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân ngưỡng lên 2, 100 ms thì chia 10, cứ thế mà tính.

Đề bài thì quá rõ ràng rồi nên mình cũng không có gì giải thích thêm nha các bạn: với $x = 45$, số siêu đối xứng nhỏ nhất lớn hơn $45$ là $55$, nên $y = 55 - 45 = 10$.

Tư tưởng chung: tìm z rồi lấy z − x

Khá dễ để nhìn ra tư tưởng xử lý: hãy tìm ra số $z$ đầu tiên (cũng đồng nghĩa là nhỏ nhất) là số siêu đối xứng sao cho $z \gt x$, rồi từ đó $y = z - x$ – giá trị $y$ này bảo đảm là nhỏ nhất.

z > x chứ không phải z ≥ x

Không xét trường hợp $z = x$ nha các bạn. Nếu $z = x$ thì $y = 0$, không đúng với yêu cầu $y$ là số nguyên dương: theo định nghĩa số nguyên dương là số $\gt 0$, số $0$ không phải số nguyên dương (cũng không phải số nguyên âm). Vậy nếu $x = 22$ thì không được chọn $z = 22$ mà phải chọn $z = 33$, từ đó $y = 33 - 22 = 11$.

Ta thử đưa ra nhiều test để nhìn thấy rõ cách làm:

x	z nhỏ nhất (siêu đối xứng, z > x)	y = z − x
78	88	10
99	111	12
123	222	99
9031	9999	968
9998	9999	1
9999	11111	1112

Mấu chốt quyết định là tìm ra $z$ nhỏ nhất là số siêu đối xứng thoả $z \gt x$, đáp án chính là $z - x$. Tuy nhìn ra cách giải nhưng mình đã thấy nhiều bạn chọn cách cài không khéo nên rất phức tạp, nhiều lỗi khó kiểm soát, chưa kể còn bị quá thời gian nếu chọn hướng không tối ưu.

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ộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Tăng z dần từng đơn vị · O(Z − X)Cách 2Dựng z bằng xâu · O(độ dài x)

Cách 1Vét cạn: tăng z lên từng đơn vị – O(Z − X)

Hướng nhẹ đầu nhất mà nhiều bạn chắc chắn nhìn ra: cứ lần lượt tăng $z$ lên 1 đơn vị, mỗi lần kiểm tra $z$ có phải số siêu đối xứng không; tới khi thoả thì in $z - x$. Đây là cách vét cạn dễ cài đặt. Bạn nào chưa nghĩ ra cách tối ưu thì mình luôn khuyên cứ cài cách vét cạn này trước, để dùng nó làm công cụ kiểm tra tính chính xác cho cách tối ưu về sau (cuối bài mình có làm mẫu luôn).

Source code để các bạn tham khảo nếu làm theo cách vét cạn:

#include <iostream>
using namespace std;

bool isSupersymmetryNumber(long long x){
    int num = x % 10;
    x /= 10;
    while(x){
        if(x % 10 != num){
            return false;
        }
        x /= 10;
    }
    return true;
}

int main(){
    long long x;
    cin >> x;
    long long z = x;
    while(!isSupersymmetryNumber(++z));
    cout << z - x;
    return 0;
}

def isSupersymmetryNumber(x):
    num = x % 10
    x //= 10
    while x:
        if x % 10 != num:
            return False
        x //= 10
    return True

x = int(input())
z = x + 1
while not isSupersymmetryNumber(z):
    z += 1
print(z - x)

Giải thích một số chỗ trong code:

1. Đề cho $x$ tối đa tới $10^{16}$ nên phải chọn kiểu số nguyên 8 byte long long để tránh tràn số.
2. while(x) ⇔ while(x != 0): trong lập trình khi gọi một biến ra so sánh mà không nói rõ so sánh gì thì nghĩa là kiểm tra nó có khác 0 không. Tương tự while(!x) ⇔ while(x == 0). Số 0 đại diện cho false, nên với biến kiểu bool thì while(x) ⇔ while(x == true), còn while(!x) ⇔ while(x == false).
3. Hàm isSupersymmetryNumber kiểm tra $x$ có phải số siêu đối xứng không: lấy num = x % 10 (chữ số cuối) làm mốc, x /= 10 bỏ chữ số đó, rồi liên tục % 10 và / 10 lấy từng chữ số ra so với num; chỉ cần gặp 1 chữ số khác num là return false ngay. Vòng lặp kết thúc mà hàm vẫn chạy xuống dưới nghĩa là mọi chữ số đều giống nhau ⇒ return true.
4. while(!isSupersymmetryNumber(++z));: $z$ ban đầu chép từ $x$; mỗi vòng tăng $z$ lên 1 trước rồi mới kiểm tra (nhờ vậy không bao giờ xét $z = x$). Chưa thoả thì lặp tiếp, thoả thì dừng và in $z - x$.

Em bấm Tiếp để chạy tay code C++ của cách vét cạn (chọn $x$ sao cho đáp án nhỏ để dễ theo dõi):

C++▶ Chạy tay từng dòng codeCách 1: tăng z từng đơn vị, mỗi lần tách chữ số kiểm tra có giống hết nhau không.

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

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4bool isSupersymmetryNumber(long long x){

5 int num = x % 10;

6 x /= 10;

7 while(x){

8 if(x % 10 != num){

9 return false;

10 }

11 x /= 10;

12 }

13 return true;

14}

15

16int main(){

17 long long x;

18 cin >> x;

19 long long z = x;

20 while(!isSupersymmetryNumber(++z));

21 cout << z - x;

22 return 0;

23}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(1)$, chỉ dùng các biến đơn lẻ.
• Thời gian: vòng while trong main lặp $Z - X$ lần ($Z$ là số siêu đối xứng nhỏ nhất $\gt X$), mỗi lần gọi hàm kiểm tra tách tối đa 16 chữ số ⇒ $O(16 \cdot (Z - X))$.

Không gian$O(1)$

Thời gian$O(Z - X)$

Trường hợp xấu nhất: hơn 5 năm 😱

$Z - X$ lớn nhất khi chính $X$ là số siêu đối xứng: $X = 1111111111111111$ (16 chữ số 1) thì $Z = 2222222222222222$, số lần lặp $Z - X$ hơn 1 triệu tỷ, nhân thêm 16 thành cỡ $16 \cdot 10^{15}$ phép toán. Một giây chạy được $10^8$ thì cần $16 \cdot 10^7$ giây, tức hơn 5 năm mới ra kết quả ⇒ chắc chắn TLE ở subtask cuối. Nhưng vẫn nên viết ra để làm công cụ kiểm tra cách tối ưu.

Thực tế chạy thử

Mình chạy thử bản C++: với $x \le 10^6$ thì ra kết quả tức thì; với $x = 111111111$ (9 chữ số) mất khoảng 0.26 giây (vì phần lớn các số bị loại ngay ở 1–2 chữ số đầu tiên được so, nên thực tế nhanh hơn ước lượng $16 \cdot (Z - X)$); còn với $x = 1111111111111111$ thì chạy hơn 10 giây vẫn chưa xong. Bản Python chậm hơn C++ nhiều nên chỉ nên kỳ vọng subtask $x \le 10^6$.

Cách 2Dựng thẳng z bằng xâu – O(độ dài x)

Ta không cần cực như thế, cứ liên tục tăng $z$ lên từng đơn vị. Ví dụ $x = 11111$ là số siêu đối xứng thì $z = 22222$ là số siêu đối xứng tiếp theo, quá rõ để nhìn ra, cần gì phải lặp tăng dần?

Dễ nhất cho bài này là dùng chuỗi (string): đọc luôn $x$ ở dạng string, ví dụ x = "102". Số $z$ siêu đối xứng nhỏ nhất $\gt x$ trước tiên sẽ có độ dài (số chữ số) bằng độ dài $x$ – vì nếu $z$ ít chữ số hơn thì chắc chắn $z \lt x$ rồi.

1. Khởi đầu cho cả chuỗi $z$ là ký tự đầu tiên x[0]: x = "102" thì z = "111". So sánh z > x: thoả ⇒ đổi cả hai sang số rồi trừ: $111 - 102 = 9$.
2. Với x = "135": z = "111" không lớn hơn $x$. Lúc này biến $z$ thành số siêu đối xứng tiếp theo bằng cách cho cả chuỗi là ký tự x[0] + 1: z = "222", chắc chắn $z \gt x$ ⇒ $222 - 135 = 87$.
3. Với x = "999": z = "999" không lớn hơn $x$, mà x[0] đã là '9' rồi, không tăng được nữa. Lúc này $z$ phải dài hơn $x$ 1 chữ số và toàn chữ số '1': z = "1111" ⇒ $1111 - 999 = 112$.

Vì sao so sánh chuỗi lại đúng như so sánh số?

Class string của C++ có sẵn các toán tử so sánh, chỉ cần gọi if(z > x). Nó so từ trái qua phải từng cặp ký tự cùng vị trí theo mã ASCII, cặp đầu tiên khác nhau quyết định chuỗi nào lớn hơn. Với 2 số có cùng số chữ số, đó cũng chính là cách so sánh số: so hàng cao nhất trước (hàng trăm, rồi hàng chục, rồi hàng đơn vị), khác nhau ở đâu thì kết luận ngay ở đó. Vì $z$ và $x$ cùng độ dài nên so chuỗi = so số.

Chuẩn hoá lại quy trình: tạo z cùng độ dài với x, toàn ký tự x[0]. Nếu z > x ⇒ in $z - x$. Ngược lại, nếu z[0] < '9' thì đổi toàn bộ z sang ký tự z[0] + 1 rồi in $z - x$. Còn nếu z[0] == '9' thì $z$ là chuỗi dài hơn 1 ký tự, toàn chữ số '1', rồi in $z - x$.

Minh hoạ dựng z

Em nhập $x$ rồi bấm Tiếp để xem $z$ được dựng và so sánh với $x$ từng ký tự như thế nào:

x

Ví dụ nhanh:

Source code để các bạn tham khảo với hướng làm tối ưu này:

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

int main(){
    string x;
    cin >> x;
    string z(x.length(), x[0]);
    if(z > x){
        cout << stoll(z) - stoll(x);
    }
    else{
        if(z[0] < '9'){
            fill(z.begin(), z.end(), z[0] + 1);
            cout << stoll(z) - stoll(x);
        }
        else{
            cout << setfill('1') << setw(z.length()) << 2;
        }
    }
    return 0;
}

x = input().strip()
z = x[0] * len(x)
if z > x:
    print(int(z) - int(x))
else:
    if z[0] < '9':
        z = chr(ord(z[0]) + 1) * len(x)
        print(int(z) - int(x))
    else:
        print('1' * (len(x) - 1) + '2')

Bấm Tiếp để chạy tay từng dòng code C++:

C++▶ Chạy tay từng dòng codeCách 2: z = toàn ký tự x[0]; chưa lớn hơn x thì tăng chữ số, gặp 9 thì in 11...12.

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

Dữ liệu mẫu:

1#include <iostream>

2#include <iomanip>

3#include <string>

4#include <algorithm>

5using namespace std;

6

7int main(){

8 string x;

9 cin >> x;

10 string z(x.length(), x[0]);

11 if(z > x){

12 cout << stoll(z) - stoll(x);

13 }

14 else{

15 if(z[0] < '9'){

16 fill(z.begin(), z.end(), z[0] + 1);

17 cout << stoll(z) - stoll(x);

18 }

19 else{

20 cout << setfill('1') << setw(z.length()) << 2;

21 }

22 }

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Giải thích một số chỗ trong code:

1. string z(x.length(), x[0]); dùng hàm khởi tạo có tham số của class string để tạo sẵn chuỗi có độ dài x.length(), toàn bộ là ký tự x[0]. Bạn nào không biết cú pháp này sẽ phải code dài hơn, biết nó rất tiện.
2. stoll(z) chuyển chuỗi z sang số nguyên kiểu long long, tương tự stoll(x); kết quả là số nên trừ nhau được. Tương tự có hàm stoi trả về kiểu int.
3. fill(z.begin(), z.end(), z[0] + 1); thay toàn bộ ký tự từ đầu tới cuối chuỗi z bằng ký tự z[0] + 1. (Mình thêm #include <algorithm> cho hàm fill để code biên dịch được trên mọi trình biên dịch.)
4. Trường hợp cuối: z không lớn hơn x mà z[0] == '9' nghĩa là x toàn chữ số 9. Để ý quy luật: $x = 9$ ⇒ $11 - 9 = 2$; $x = 99$ ⇒ $12$; $x = 999$ ⇒ $112$; $x = 9999$ ⇒ $1112$. Đáp án luôn là (độ dài x − 1) chữ số 1 rồi một chữ số 2. Nên khỏi phải tạo lại z rồi đổi sang số trừ nhau, in luôn: cout << setfill('1') << setw(z.length()) << 2; nghĩa là in số 2 và đệm ký tự '1' đằng trước sao cho tổng độ dài (tính cả số 2) đúng bằng z.length().

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

• Không gian: chỉ có 2 chuỗi tối đa 17 ký tự ⇒ $O(\text{length}_x)$, trong bài này coi như $O(1)$.
• Thời gian: tạo z, so sánh chuỗi, đổi sang số, fill, in các ký tự '1'... đều là $O(\text{length}_x)$; theo quy tắc cộng Big-O ⇒ $O(\text{length}_x)$. Với $x \le 10^{16}$ (tối đa 17 chữ số) thì có thể coi là hằng số, nhưng cứ để $O(\text{length}_x)$ để nếu đề nâng $x$ lên tới $10^{1000}$ hay $10^{100000}$ thì lại khác.

Không gian$O(1)$

Thời gian$O(\text{length}_x)$

Từ 5 năm xuống tức thì

Thử ngay trường hợp xấu nhất của cách 1, $X = 1111111111111111$ (16 chữ số 1): cách này trả ra $1111111111111111$ ngay lập tức, còn cách trước ước chừng hơn 5 năm. Chịu khó suy luận tối ưu lại một chút mà chạy nhanh hơn rất nhiều nè 😄

Dùng vét cạn để kiểm tra cách tối ưu

Sẵn mình cho các bạn xem luôn cách dùng code vét cạn (cách 1) làm công cụ kiểm tra tính chính xác cho cách tối ưu (cách 2): sinh ngẫu nhiên $x$, chạy cả 2 hàm và so kết quả.

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

bool isSupersymmetryNumber(long long x){
    int num = x % 10;
    x /= 10;
    while(x){
        if(x % 10 != num){
            return false;
        }
        x /= 10;
    }
    return true;
}

long long solve1(long long x){
    long long z = x;
    while(!isSupersymmetryNumber(++z));
    return z - x;
}

long long solve2(long long a){
    string x = to_string(a);
    string z(x.length(), x[0]);
    if(z > x){
        return stoll(z) - stoll(x);
    }
    if(z[0] < '9'){
        fill(z.begin(), z.end(), z[0] + 1);
        return stoll(z) - stoll(x);
    }
    fill(z.begin(), z.end(), '1');
    z.back() = '2';
    return stoll(z);
}

int main(){
    srand(time(0));
    while(1){
        long long x = 1 + rand() % 1000000;
        long long res1 = solve1(x);
        long long res2 = solve2(x);
        if(res1 == res2){
            cout << "OK\n";
        }
        else{
            cout << "FAIL\n";
            cout << "x = " << x << endl;
            cout << "res1 = " << res1 << endl;
            cout << "res2 = " << res2;
            break;
        }
    }
    return 0;
}

Chạy chương trình lên, treo 10 phút mà nhìn lại toàn thấy chữ OK là yên tâm code ổn. Còn thấy chữ FAIL to đùng xuất hiện thì chương trình dừng ngay, in ra $x$, res1, res2 – ta biết bị sai ở trường hợp $x$ đó và kiểm tra lại bài làm với nó.

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng ví dụ của đề. Mình so chúng với một chương trình độc lập (liệt kê sẵn mọi số siêu đối xứng tới 18 chữ số rồi lấy số đầu tiên $\gt x$) trên 570 giá trị $x$: $x$ từ 1 tới 59, các trường hợp biên như $99$, $9999$, $10^6$, $10^9$, $9999999999999999$, $10^{16}$, cùng 500 giá trị ngẫu nhiên tới $10^{16}$ (cách 1 chỉ thử với $x \le 10^6$) – khớp hết. Chương trình kiểm tra ở trên chạy 5 giây được hơn 36 nghìn lượt, toàn OK.

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 😇