Khóa Số (HSG12 Hà Nội 2025 – Bài 1)

Nguồn: Đề thi HSG lớp 12 Hà Nội 2025 – Bài 1 Độ khó: Dễ Mô phỏng Toán học Chia lấy dư

Đề bài

Bài I. Khoá số (5,0 điểm)

Hải dùng ổ khóa số (Hình ảnh) để khóa tủ cá nhân tại đội tuyển. Khóa gồm có bốn vòng số, mỗi vòng gồm $10$ chữ số từ $0$ đến $9$. Các vòng số của khóa này có thể xoay tròn theo chiều kim đồng hồ hoặc ngược lại.

Hải đặt mật khẩu khóa của mình theo thứ tự từ trên xuống dưới của vị trí chốt là $\{2, 0, 2, 5\}$. Mỗi lần khóa, Hải xoay các số đi, khi nào muốn mở thì lại đưa các số về đúng dãy $\{2, 0, 2, 5\}$. Mỗi lần xoay thì một chữ số sẽ chuyển thành số kề bên trái hoặc kề bên phải của nó.

Chú ý: kề bên trái của $0$ là $9$, kề bên phải của $9$ là $0$.

Hình ảnh: ổ khóa 4 vòng số (vẽ lại minh hoạ), đang ở đúng mật khẩu $\{2, 0, 2, 5\}$ tại vị trí chốt.

Yêu cầu: Cho biết $4$ chữ số $A, B, C, D$ lần lượt là các chữ số đang xuất hiện từ trên xuống dưới của vị trí chốt. Em hãy lập trình tính giúp Hải xem phải xoay ít nhất bao nhiêu lần để có thể mở khóa.

Dữ liệu vào từ file văn bản KHOASO.INP: Gồm bốn chữ số $A, B, C, D$ trên cùng một dòng, cách nhau bởi một dấu cách $(0 \le A, B, C, D \le 9)$.

Kết quả ghi ra file văn bản KHOASO.OUT: Một số nguyên duy nhất là kết quả của bài toán.

Lưu ý: trên hệ thống chấm online CLUE OJ thì đọc dữ liệu từ bàn phím và in kết quả ra màn hình (giới hạn trên CLUE OJ: 1 giây, 1 GB).

KHOASO.INP

2 3 8 1

KHOASO.OUT

11

Giải thích ví dụ (trong đề): Cách xoay ít lần nhất để mở khóa là:

• Chữ số thứ nhất giữ nguyên;
• Chữ số thứ hai xoay từ $3$ thành $0$ mất $3$ lần xoay;
• Chữ số thứ ba xoay từ $8$ thành $2$ mất $4$ lần xoay như sau: $8 \to 9 \to 0 \to 1 \to 2$;
• Chữ số thứ tư xoay từ $1$ thành $5$ mất $4$ lần xoay;

Tổng số lần xoay là: $0 + 3 + 4 + 4 = 11$.

Lời mở đầu

Đây là bài 1 – bài "khởi động" của đề thi học sinh giỏi Tin học lớp 12 thành phố Hà Nội năm 2025. Bài dễ nhưng rất hay bị mất điểm oan vì quên trường hợp "vòng qua" $9 \to 0$ hoặc $0 \to 9$. Mình viết lời giải chi tiết để nhiều bạn được tham khảo luôn, nhất là các bạn đang ôn thi HSG. 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 tóm tắt lại đề cho dễ hình dung: có $4$ vòng số, mỗi vòng đang hiện một chữ số. Mỗi lần xoay, ta chọn một vòng và đẩy chữ số của nó lên $1$ (sang phải: $3 \to 4$, …, $9 \to 0$) hoặc xuống $1$ (sang trái: $3 \to 2$, …, $0 \to 9$). Cần đưa $4$ vòng về đúng $2, 0, 2, 5$ với ít lần xoay nhất.

Vì mỗi lần xoay chỉ tác động lên đúng một vòng, nên các vòng hoàn toàn độc lập với nhau: số lần xoay ít nhất của cả ổ khóa = tổng số lần xoay ít nhất của từng vòng. Với ví dụ 2 3 8 1:

Vòng	Đang là	Cần về	Xoay phải (tăng)	Xoay trái (giảm)	Ít nhất
1	2	2	0	0	0
2	3	0	3→4→…→9→0: 7	3→2→1→0: 3	3
3	8	2	8→9→0→1→2: 4	8→7→…→2: 6	4
4	1	5	1→2→3→4→5: 4	1→0→9→8→7→6→5: 6	4

Tổng: $0 + 3 + 4 + 4 = 11$ – đúng với đáp án của đề.

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

Cách 1Xoay thử 2 chiều (lời giải thi) · O(1)Cách 2Công thức min(d, 10 − d) · O(1)

Cách 1Xoay thử theo từng chiều rồi lấy min – O(1)

Ta sẽ xử lý riêng đối với từng chốt (từng vòng số). Ở đây ta gọi:

• $right(x, y)$: số lần xoay để đưa chữ số $x$ thành $y$ mà chỉ sử dụng thao tác xoay phải (tăng lên $1$, sau $9$ là $0$).
• $left(x, y)$: số lần xoay để đưa chữ số $x$ thành $y$ mà chỉ sử dụng thao tác xoay trái (giảm đi $1$, trước $0$ là $9$).

Dễ thấy có thể tính những hàm này bằng cách duyệt trâu: cứ xoay từng nấc một và đếm, đến khi $x = y$ thì dừng. Mỗi vòng chỉ có $10$ chữ số nên đi một chiều tối đa $9$ nấc là tới – vòng lặp chạy rất ít.

Vì sao chỉ cần xét 2 chiều "đi thẳng"?

Xoay qua xoay lại (lúc phải lúc trái) trên cùng một vòng chỉ làm các nấc triệt tiêu nhau, tốn thêm lần xoay mà không có lợi gì. Vậy cách tốt nhất cho một vòng là đi thẳng một chiều: hoặc toàn xoay phải, hoặc toàn xoay trái. Do đó để xoay một chốt $x$ về lại $y$ thì tốn tối thiểu $\min(right(x, y),\ left(x, y))$ thao tác.

Kết quả bài toán sẽ là:

Công thức kết quả

$\min(right(A, 2), left(A, 2)) + \min(right(B, 0), left(B, 0)) + \min(right(C, 2), left(C, 2)) + \min(right(D, 5), left(D, 5))$

Cái "vòng qua" $9 \to 0$ và $0 \to 9$ được xử lý gọn bằng phép chia lấy dư cho $10$:

• Xoay phải: x++; x %= 10; – khi $x = 9$ thì $x + 1 = 10$, $10 \bmod 10 = 0$. Đúng "kề bên phải của 9 là 0".
• Xoay trái: x--; x += 10; x %= 10; – khi $x = 0$ thì $x - 1 = -1$, cộng $10$ được $9$, $9 \bmod 10 = 9$. Đúng "kề bên trái của 0 là 9". Còn với $x \ge 1$ thì cộng $10$ rồi chia dư $10$ không làm thay đổi gì.

Vì sao phải cộng 10 trước khi chia dư?

Trong C++, phép % với số âm cho kết quả âm: -1 % 10 bằng -1 chứ không phải 9. Nếu chỉ viết x--; x %= 10; thì từ $0$ xoay trái sẽ ra $-1$, vòng while(x != y) chạy mãi không dừng! (Python thì -1 % 10 = 9, nhưng mình vẫn giữ + 10 cho giống code C++.)

Minh hoạ xoay từng vòng số

Em nhập $4$ chữ số đang hiện trên khóa rồi bấm Tiếp: với mỗi vòng, khung dưới tô đường đi khi xoay phải (xanh lá) và khi xoay trái (cam), rồi chọn chiều ngắn hơn.

A B C D

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 A, B, C, D;
int right(int x, int y){
    int ans = 0;
    while (x != y){
        x ++;
        x %= 10;
        ans ++;
    }
    return ans;
}
int left(int x, int y){
    int ans = 0;
    while (x != y){
        x --;
        x += 10;
        x %= 10;
        ans ++;
    }
    return ans;
}
int main(){
    if(fopen("KHOASO.INP", "r")){
        freopen("KHOASO.INP", "r", stdin);
        freopen("KHOASO.OUT", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> A >> B >> C >> D;
    cout << min(right(A, 2), left(A, 2))
          + min(right(B, 0), left(B, 0))
          + min(right(C, 2), left(C, 2))
          + min(right(D, 5), left(D, 5)) << endl;
}

import sys, os

def right(x, y):
    ans = 0
    while x != y:
        x += 1
        x %= 10
        ans += 1
    return ans

def left(x, y):
    ans = 0
    while x != y:
        x -= 1
        x += 10
        x %= 10
        ans += 1
    return ans

if os.path.exists("KHOASO.INP"):
    sys.stdin = open("KHOASO.INP", "r")
    sys.stdout = open("KHOASO.OUT", "w")
A, B, C, D = map(int, sys.stdin.read().split()[:4])
print(min(right(A, 2), left(A, 2))
      + min(right(B, 0), left(B, 0))
      + min(right(C, 2), left(C, 2))
      + min(right(D, 5), left(D, 5)))

Các bạn bấm Tiếp để chạy tay từng dòng. Phần "Dữ liệu" vẽ vòng số $0..9$: ô vàng là chữ số $x$ hiện tại, con trỏ y là chữ số cần về. Thử nút Vòng qua 9 → 0 để thấy phép % 10 làm việc thế nào nha.

C++▶ Chạy tay từng dòng codeCách 1: với từng vòng, đếm số nấc nếu chỉ xoay phải và nếu chỉ xoay trái, lấy min rồi cộng lại.

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

Dữ liệu mẫu:

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

2using namespace std;

3int A, B, C, D;

4int right(int x, int y){

5 int ans = 0;

6 while (x != y){

7 x ++;

8 x %= 10;

9 ans ++;

10 }

11 return ans;

12}

13int left(int x, int y){

14 int ans = 0;

15 while (x != y){

16 x --;

17 x += 10;

18 x %= 10;

19 ans ++;

20 }

21 return ans;

22}

23int main(){

24 if(fopen("KHOASO.INP", "r")){

25 freopen("KHOASO.INP", "r", stdin);

26 freopen("KHOASO.OUT", "w", stdout);

27 }

28 ios::sync_with_stdio(0);

29 cin.tie(0);

30 cin >> A >> B >> C >> D;

31 cout << min(right(A, 2), left(A, 2))

32 + min(right(B, 0), left(B, 0))

33 + min(right(C, 2), left(C, 2))

34 + min(right(D, 5), left(D, 5)) << endl;

35}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code ở trên:

1. if(fopen("KHOASO.INP", "r")) { freopen(...); }: nếu trong thư mục có file KHOASO.INP (lúc thi trên máy chấm) thì chuyển việc đọc/ghi sang file; còn khi nộp lên hệ thống chấm online không có file này thì điều kiện sai và chương trình đọc bàn phím, in màn hình như bình thường. Viết kiểu này thì một code dùng được cho cả hai.
2. Hai hàm đặt tên right, left trùng tên với hai "manipulator" std::right, std::left của thư viện. Code vẫn biên dịch chạy đúng (mình đã thử với g++), vì khi gọi right(A, 2) với 2 tham số kiểu int thì trình biên dịch chọn đúng hàm của mình. Nhưng nếu bạn nào lo thì cứ đổi tên thành xoayPhai, xoayTrai cho chắc ăn nhé.
3. Thứ tự gọi các hàm trong một biểu thức (gọi right hay left trước) do trình biên dịch quyết định; ở khung chạy tay mình cho chạy từ trái sang phải cho dễ theo dõi, kết quả không đổi.

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

• Không gian: $O(1)$ – chỉ vài biến.
• Thời gian: mỗi lần gọi right/left lặp tối đa $9$ lần, có $8$ lần gọi, nên tối đa khoảng $72$ bước – là hằng số, $O(1)$.

Không gian$O(1)$

Thời gian$O(1)$

Cách 2Công thức min(d, 10 − d) – O(1)

Ở cách 1 các bạn để ý: nếu gọi $d = |x - y|$ là khoảng cách "đi thẳng" giữa hai chữ số (không đi vòng qua $9 \to 0$), thì một chiều xoay tốn đúng $d$ lần, còn chiều ngược lại phải đi vòng qua phần còn lại của vòng tròn $10$ chữ số, tốn $10 - d$ lần. Ví dụ $8 \to 2$: $d = 6$ (đi trái $8 \to 7 \to \dots \to 2$), chiều kia $10 - 6 = 4$ (đi phải $8 \to 9 \to 0 \to 1 \to 2$). Vậy:

Công thức cho một vòng

$cost(x, y) = \min(d,\ 10 - d)$ với $d = |x - y|$. Kết quả $= cost(A, 2) + cost(B, 0) + cost(C, 2) + cost(D, 5)$.

Khi $x = y$ thì $d = 0$, $\min(0, 10) = 0$ – đúng là không phải xoay. Cách này chỉ là "rút gọn" của cách 1 cho gọn code; trong phòng thi thì cách 1 vẫn là an toàn và đủ điểm, vì vòng lặp tối đa chỉ $9$ nấ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 cost(int x, int y){
    int d = abs(x - y);
    return min(d, 10 - d);
}
int main(){
    if(fopen("KHOASO.INP", "r")){
        freopen("KHOASO.INP", "r", stdin);
        freopen("KHOASO.OUT", "w", stdout);
    }
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << cost(A, 2) + cost(B, 0) + cost(C, 2) + cost(D, 5) << endl;
}

import sys, os

def cost(x, y):
    d = abs(x - y)
    return min(d, 10 - d)

if os.path.exists("KHOASO.INP"):
    sys.stdin = open("KHOASO.INP", "r")
    sys.stdout = open("KHOASO.OUT", "w")
A, B, C, D = map(int, sys.stdin.read().split()[:4])
print(cost(A, 2) + cost(B, 0) + cost(C, 2) + cost(D, 5))

C++▶ Chạy tay từng dòng codeCách 2: mỗi vòng tốn min(d, 10 - d) lần xoay, với d = |x - y|.

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

Dữ liệu mẫu:

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

2using namespace std;

3int cost(int x, int y){

4 int d = abs(x - y);

5 return min(d, 10 - d);

6}

7int main(){

8 if(fopen("KHOASO.INP", "r")){

9 freopen("KHOASO.INP", "r", stdin);

10 freopen("KHOASO.OUT", "w", stdout);

11 }

12 int A, B, C, D;

13 cin >> A >> B >> C >> D;

14 cout << cost(A, 2) + cost(B, 0) + cost(C, 2) + cost(D, 5) << endl;

15}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này: chỉ $4$ lần tính công thức.

Không gian$O(1)$

Thời gian$O(1)$

Mẹo kiểm tra khi đi thi

Bài có không gian đầu vào rất nhỏ (chỉ $10^4$ bộ $A, B, C, D$) thì các bạn hoàn toàn có thể viết thêm một chương trình vét cạn (ví dụ BFS trên $10^4$ trạng thái của ổ khóa) rồi so kết quả với code của mình trên tất cả các bộ dữ liệu. Mình cũng làm đúng như vậy để kiểm tra bài này (xem ghi chú bên dưới).

Ghi chú của mình: code C++ của cả 2 cách đã được chạy với tất cả $10^4$ bộ $A, B, C, D$ và so với kết quả của một chương trình BFS trên $10^4$ trạng thái ổ khóa (mỗi bước xoay một vòng lên/xuống 1 nấc) – khớp hết; bản Python của 2 cách được so trên 500 bộ chọn ngẫu nhiên trong số đó – cũng khớp hết. Test của đề cho đúng $11$.

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 😇