Chuyên đề 4: Mô phỏng và kỹ thuật trên lưới trong C++ và Python: mảng hướng dx dy, ma trận xoắn ốc, xoay ma trận, ngày tháng

Series: Chuyên đề nhập môn Độ khó: Dễ Chuyên đề 4 / Nhập môn lập trình Mô phỏng Lưới

// Chuyên đề nhập môn · Chuyên đề 4

Mô phỏng và kỹ thuật trên lưới: mảng hướng, xoắn ốc, xoay ma trận, ngày tháng

Robot đi trên bàn cờ, dò mìn, điền số xoắn ốc, xoay ảnh, tính thứ của một ngày: toàn những bài “làm đúng như đề nói” nhưng rất dễ sai một li đi một dặm. Bài này dạy em cách viết chúng gọn và không sót trường hợp.

Lời mở đầu

Trong đề thi HSG, câu 1 và câu 2 thường là bài mô phỏng: đề mô tả một quá trình (robot đi theo lệnh, con ốc bò quanh vườn, đồng hồ chạy thêm k giây…) và em chỉ việc làm đúng như đề mô tả. Không cần thuật toán cao siêu, nhưng rất nhiều bạn mất điểm vì quên kiểm tra ô ra ngoài lưới, quên năm nhuận, đánh nhầm hàng với cột, hay viết 8 câu lệnh if gần giống nhau rồi sai một câu.

Bài này dùng nhiều mảng hai chiều, nên nếu em chưa vững hãy xem lại bài 7: Mảng 2 chiều, và cách viết vòng lặp ở bài 4: Vòng lặp. Mình sẽ đi thật chậm: mỗi kỹ thuật đều có ví dụ chạy tay, mô phỏng bấm từng bước và code C++ lẫn Python.

Chuyên đề 1Chữ số và hệ cơ sốChuyên đề 2Số thực, làm trònChuyên đề 3Số nguyên lớnChuyên đề 4Mô phỏng trên lướiChuyên đề 5Xử lý xâu trong đề thiChuyên đề 6Số học trong đề thiChuyên đề 7File và nhập xuất nhanhChuyên đề 8Python khi đi thiChuyên đề 9Cộng dồn 2 chiềuChuyên đề 10Vét cạn thông minh

Trong bài này bạn sẽ học: dùng mảng hướng dx, dy để duyệt 4 hoặc 8 ô kề bằng một vòng for; hàm kiểm tra ô trong lưới; bài dò mìn đếm mìn xung quanh; robot đi theo lệnh và quay trái, quay phải bằng (d + 1) % 4; điền ma trận xoắn ốc bằng quy tắc “bị chặn thì rẽ phải” và cách duyệt theo từng lớp; xoay, lật, chuyển vị ma trận bằng công thức chỉ số; ngày tháng: năm nhuận, cộng thêm k ngày, thứ trong tuần, đổi giờ phút giây và mẹo tìm chu kỳ khi k rất lớn. Có khung chạy tay, 3 mô phỏng bấm từng bước và 8 bài tập kèm gợi ý.

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

Phần 1Mảng hướng dx dyPhần 2Robot đi theo lệnhPhần 3Ma trận xoắn ốcPhần 4Xoay, lật ma trậnPhần 5Ngày tháng, chu kỳBài tập8 bài + gợi ý

Phần 1Mảng hướng dx, dy và các ô kề

Trên lưới $n$ hàng, $m$ cột, ta gọi ô ở hàng $i$, cột $j$ là ô $(i, j)$, đánh số từ 0. Hàng tăng khi đi xuống, cột tăng khi đi sang phải (giống cách viết mảng a[i][j]). Vậy từ ô $(i, j)$:

• đi lên: $(i - 1, j)$, đi xuống: $(i + 1, j)$;
• sang trái: $(i, j - 1)$, sang phải: $(i, j + 1)$.

Nếu cần xét cả 4 ô kề, nhiều bạn viết 4 khối if gần giống nhau. Với 8 ô kề (thêm đường chéo) thì thành 8 khối, rất dễ gõ nhầm một dấu cộng trừ. Mẹo của dân thi đấu: ghi độ lệch của từng hướng vào hai mảng dx (lệch hàng) và dy (lệch cột), rồi duyệt hướng bằng một vòng lặp.

Hình 1. Ô kề thứ $k$ của $(i, j)$ là $(i + dx[k],\ j + dy[k])$. Bốn ô xanh dương chung cạnh, bốn ô tím chung đỉnh.

Khuôn mẫu duyệt ô kề

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool inside(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}

for(int k = 0; k < 4; k++){
    int x = i + dx[k], y = j + dy[k];   // ô kề thứ k
    if(!inside(x, y)) continue;          // LUÔN kiểm tra biên trước
    // ... xử lý ô (x, y) ...
}

Đổi 4 thành 8 và dùng hai mảng 8 phần tử là có ngay 8 hướng. Phần còn lại của code giữ nguyên.

Vì sao phải kiểm tra biên trước? Ô ở góc $(0, 0)$ có ô “phía trên” là $(-1, 0)$. Đọc a[-1][0] trong C++ không báo lỗi mà đọc nhầm một vùng nhớ khác, cho ra kết quả sai ngẫu nhiên; trong Python, a[-1] lại là hàng cuối cùng, nên chương trình chạy êm mà vẫn sai. Ở điều kiện if, phép && (and) dừng ngay khi gặp vế sai, nên viết inside(x, y) && g[x][y] == '*' là an toàn: ô ngoài lưới không bao giờ bị đọc.

Ví dụ: trò dò mìn. Cho lưới gồm ô trống . và ô có mìn *. Với mỗi ô trống, in ra số mìn trong 8 ô xung quanh nó. Chạy tay ô $(0, 1)$ của lưới bên dưới: các ô kề nằm trong lưới là $(0, 0)$ có mìn, $(0, 2)$, $(1, 0)$, $(1, 1)$, $(1, 2)$ có mìn; ba ô phía trên nằm ngoài lưới nên bỏ qua. Vậy ô $(0, 1)$ ghi số 2.

Lưới vào	Kết quả	Giải thích vài ô
*... ..*. ....	*211 12*1 0111	Ô (1, 0): kề với (0, 0) có mìn → 1. Ô (2, 0): không ô kề nào có mìn → 0. Ô (0, 3): chỉ kề (1, 2) có mìn → 1.

Bảng 1. Dò mìn trên lưới 3 × 4: mỗi ô trống đếm số mìn trong 8 ô xung quanh.

Xem code C++ / Python: dò mìn với mảng 8 hướng (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int n, m;
string g[105];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

bool inside(int x, int y){              // ô (x, y) có nằm trong lưới không?
    return x >= 0 && x < n && y >= 0 && y < m;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> g[i];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(g[i][j] == '*'){ cout << '*'; continue; }
            int cnt = 0;
            for(int k = 0; k < 8; k++){
                int x = i + dx[k], y = j + dy[k];
                if(inside(x, y) && g[x][y] == '*') cnt++;   // kiểm tra biên TRƯỚC
            }
            cout << cnt;
        }
        cout << '\n';
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

out = []
for i in range(n):
    row = []
    for j in range(m):
        if g[i][j] == '*':
            row.append('*')
            continue
        cnt = 0
        for k in range(8):
            x, y = i + dx[k], j + dy[k]
            if 0 <= x < n and 0 <= y < m and g[x][y] == '*':   # kiểm tra biên TRƯỚC
                cnt += 1
        row.append(str(cnt))
    out.append(''.join(row))
print('\n'.join(out))

Em bấm Tiếp để xem máy tính đi qua từng ô, thử từng hướng $k = 0..7$, bỏ qua những ô ngoài lưới:

C++▶ Chạy tay từng dòng codeDuyệt từng ô; với ô trống, thử 8 hướng dx[k], dy[k] (ô đỏ: ô kề đang xét, viền tím: vùng 3 × 3 xung quanh).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4string g[105];

5int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

6int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

7

8int main(){

9 int n, m;

10 cin >> n >> m;

11 for(int i = 0; i < n; i++) cin >> g[i];

12 for(int i = 0; i < n; i++){

13 for(int j = 0; j < m; j++){

14 if(g[i][j] == '*'){ cout << '*'; continue; }

15 int cnt = 0;

16 for(int k = 0; k < 8; k++){

17 int x = i + dx[k], y = j + dy[k];

18 if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '*') cnt++;

19 }

20 cout << cnt;

21 }

22 cout << '\n';

23 }

24 return 0;

25}

ChậmVừaNhanhRất nhanh

Mẹo “thêm viền rào”

Một cách khác để khỏi kiểm tra biên: khai báo lưới rộng hơn 2 ô và đánh số từ 1, tức là dùng hàng $1..n$, cột $1..m$, còn hàng 0, hàng $n + 1$, cột 0, cột $m + 1$ là viền rào chứa giá trị “vô hại” (không có mìn, hoặc là tường). Khi đó ô kề của mọi ô thật đều nằm trong mảng. Cách này rất tiện với bài robot có tường: em chỉ việc đặt viền toàn là #.

Phần 2Robot đi theo xâu lệnh

Bài mô phỏng kinh điển: robot đứng ở ô S, nhận xâu lệnh gồm các chữ U (lên), D (xuống), L (trái), R (phải). Mỗi lệnh robot đi 1 ô; nếu ô đó ra ngoài lưới hoặc là tường # thì robot đứng yên và làm lệnh tiếp theo. Hỏi robot dừng ở đâu và đã đi qua bao nhiêu ô khác nhau.

Cách làm đẹp nhất là đổi chữ cái thành chỉ số hướng: đặt xâu "URDL" cùng thứ tự với mảng dx, dy, khi đó chữ c ứng với hướng d = "URDL".find(c). Mọi lệnh được xử lý bởi cùng một đoạn code: tính ô mới, kiểm tra, rồi bước.

MÔ PHỎNGRobot đi theo xâu lệnh trên lưới có tườngSửa lưới (. ô trống, # tường, S ô xuất phát), chọn kiểu lệnh rồi bấm Tiếp / Tự chạy.

LướiS...# .#... ...#. #....Kiểu lệnh4 hướng U D L RQuay: F L RXâu lệnh

ChậmVừaNhanh

robot (mũi tên là hướng)đã đi quatườngchưa tới

Lệnh	Ô định tới	Kết quả	Robot ở
R, R, R	(1, 2), (1, 3), (1, 4)	trống, bước	(1, 4)
R	(1, 5)	tường, đứng yên	(1, 4)
D, R, D, D	(2, 4), (2, 5), (3, 5), (4, 5)	trống, bước	(4, 5)
L, L, L, U, L	… (3, 2), (3, 1)	trống, bước	(3, 1)
L	(3, 0)	ngoài lưới, đứng yên	(3, 1)

Bảng 2. Chạy tay ví dụ mặc định của mô phỏng (đánh số hàng, cột từ 1 cho dễ đọc). Robot dừng ở (3, 1) và đã đi qua 13 ô khác nhau.

Xem code C++ / Python: robot đi theo xâu lệnh U D L R trên lưới có tường (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int n, m;
string g[1005];
bool vis[1005][1005];
int dx[4] = {-1, 0, 1, 0};      // U, R, D, L
int dy[4] = {0, 1, 0, -1};

int main(){
    cin >> n >> m;
    int x = 0, y = 0;
    for(int i = 0; i < n; i++){
        cin >> g[i];
        for(int j = 0; j < m; j++)
            if(g[i][j] == 'S'){ x = i; y = j; }
    }
    string s;
    cin >> s;
    string dirs = "URDL";
    vis[x][y] = true;
    int cnt = 1;                                  // số ô khác nhau đã đi qua
    for(char c : s){
        int d = dirs.find(c);                     // chữ cái -> chỉ số hướng
        int nx = x + dx[d], ny = y + dy[d];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;   // ra ngoài: đứng yên
        if(g[nx][ny] == '#') continue;                         // tường: đứng yên
        x = nx; y = ny;
        if(!vis[x][y]){ vis[x][y] = true; cnt++; }
    }
    cout << x + 1 << " " << y + 1 << "\n" << cnt;
    return 0;
}

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
s = data[2 + n]
x = y = 0
for i in range(n):
    if 'S' in g[i]:
        x, y = i, g[i].index('S')
dx = [-1, 0, 1, 0]          # U, R, D, L
dy = [0, 1, 0, -1]
vis = {(x, y)}
for c in s:
    d = 'URDL'.index(c)                     # chữ cái -> chỉ số hướng
    nx, ny = x + dx[d], y + dy[d]
    if not (0 <= nx < n and 0 <= ny < m):   # ra ngoài: đứng yên
        continue
    if g[nx][ny] == '#':                    # tường: đứng yên
        continue
    x, y = nx, ny
    vis.add((x, y))
print(x + 1, y + 1)
print(len(vis))

Quay trái, quay phải. Nhiều đề không cho hướng tuyệt đối mà cho lệnh F (đi thẳng), L (quay trái 90°), R (quay phải 90°). Khi đó robot phải nhớ hướng đang nhìn bằng một biến d. Nếu xếp 4 hướng trong mảng dx, dy theo chiều kim đồng hồ (lên, phải, xuống, trái) thì:

• quay phải: d = (d + 1) % 4 (từ “trái” = 3 quay phải thành 0 = “lên”);
• quay trái: d = (d + 3) % 4, tức là quay phải 3 lần (viết (d - 1) % 4 trong C++ sẽ ra số âm khi d = 0!);
• quay đầu: d = (d + 2) % 4;
• đi thẳng: x += dx[d]; y += dy[d];

Em chọn “Quay: F L R” ở mô phỏng trên, nhập chẳng hạn FRFFRFLF để thấy mũi tên đổi hướng. Bài tập 3 sẽ luyện đúng kiểu lệnh này.

Thứ tự trong mảng hướng rất quan trọng

Công thức (d + 1) % 4 chỉ đúng khi 4 hướng được xếp liền nhau theo một chiều quay. Nếu em xếp lên, xuống, trái, phải (thứ tự hay gặp khi chỉ cần duyệt ô kề) thì quay phải không còn là cộng 1. Thói quen tốt: luôn xếp theo chiều kim đồng hồ và ghi chú thích ngay cạnh mảng.

Phần 3Ma trận xoắn ốc

Đề: điền các số $1, 2, \ldots, n \cdot m$ vào lưới $n \times m$ theo hình xoắn ốc, bắt đầu từ góc trên trái, đi sang phải, xuống, sang trái, lên… và cuộn dần vào trong. Với $n = 4, m = 5$:

	cột 0	cột 1	cột 2	cột 3	cột 4
hàng 0	1	2	3	4	5
hàng 1	14	15	16	17	6
hàng 2	13	20	19	18	7
hàng 3	12	11	10	9	8

Bảng 3. Ma trận xoắn ốc 4 × 5.

Cách 1: “đi thẳng, bị chặn thì rẽ phải”. Hãy tưởng tượng em cầm bút đi trên lưới. Lúc đầu đi sang phải. Mỗi bước, nhìn ô phía trước: nếu nó nằm ngoài lưới hoặc đã có số thì rẽ phải 90°. Chỉ một quy tắc đó thôi là bút tự cuộn vào trong, không cần biết đang ở vòng thứ mấy! Đây chính là robot quay phải ở phần 2: mảng hướng theo chiều kim đồng hồ, bắt đầu bằng “phải”, rẽ phải là d = (d + 1) % 4.

MÔ PHỎNGĐiền ma trận xoắn ốc: đi thẳng, bị chặn thì rẽ phảiNhập số hàng n, số cột m rồi bấm Tiếp. Ô đỏ là ô chặn đường (ngoài lưới thì không tô).

n (hàng)m (cột)

ChậmVừaNhanh

ô vừa điền / đang đứngđã điềnô chặn đườngchưa điền

C++▶ Chạy tay từng dòng codeĐiền xoắn ốc: điền số, nhìn ô phía trước; ngoài lưới hoặc đã điền thì rẽ phải.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int a[105][105];

5int dx[4] = {0, 1, 0, -1}; // phải, xuống, trái, lên

6int dy[4] = {1, 0, -1, 0};

7

8int main(){

9 int n, m;

10 cin >> n >> m;

11 int x = 0, y = 0, d = 0;

12 for(int v = 1; v <= n * m; v++){

13 a[x][y] = v;

14 int nx = x + dx[d], ny = y + dy[d];

15 if(nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] != 0){

16 d = (d + 1) % 4;

17 nx = x + dx[d]; ny = y + dy[d];

18 }

19 x = nx; y = ny;

20 }

21 for(int i = 0; i < n; i++){

22 for(int j = 0; j < m; j++) cout << a[i][j] << " ";

23 cout << "\n";

24 }

25 return 0;

26}

ChậmVừaNhanhRất nhanh

Xem code C++ / Python: điền ma trận xoắn ốc bằng quy tắc rẽ phải (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int a[1005][1005];
int dx[4] = {0, 1, 0, -1};     // phải, xuống, trái, lên (theo chiều kim đồng hồ)
int dy[4] = {1, 0, -1, 0};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int x = 0, y = 0, d = 0;
    for(int v = 1; v <= n * m; v++){
        a[x][y] = v;
        int nx = x + dx[d], ny = y + dy[d];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] != 0){
            d = (d + 1) % 4;                   // bị chặn -> rẽ phải
            nx = x + dx[d]; ny = y + dy[d];
        }
        x = nx; y = ny;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cout << a[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

n, m = map(int, input().split())
a = [[0] * m for _ in range(n)]
dx = [0, 1, 0, -1]      # phải, xuống, trái, lên (theo chiều kim đồng hồ)
dy = [1, 0, -1, 0]
x = y = d = 0
for v in range(1, n * m + 1):
    a[x][y] = v
    nx, ny = x + dx[d], y + dy[d]
    if not (0 <= nx < n and 0 <= ny < m) or a[nx][ny] != 0:
        d = (d + 1) % 4                 # bị chặn -> rẽ phải
        nx, ny = x + dx[d], y + dy[d]
    x, y = nx, ny
print('\n'.join(' '.join(map(str, row)) for row in a))

Cách 2: duyệt theo từng lớp. Nhìn Bảng 3, ma trận gồm những “viền” lồng nhau như củ hành. Giữ 4 biến biên: hàng trên u, hàng dưới d, cột trái l, cột phải r. Mỗi lớp đi đủ 4 cạnh rồi co biên vào: đi hàng u từ trái sang phải xong thì u++, đi cột r từ trên xuống xong thì r--, tương tự với d và l. Dừng khi u > d hoặc l > r.

Hình 2. Ma trận 5 × 6 có 3 lớp. Số lớp bằng $\lceil \min(n, m) / 2 \rceil$; lớp trong cùng có thể chỉ là một hàng hoặc một cột.

Cách 2 rất hợp khi đề cho sẵn ma trận và hỏi thứ tự đi xoắn ốc, hoặc bắt xử lý riêng từng lớp (chẳng hạn xoay vòng mỗi lớp như bài LeetCode 1914 ở cuối bài). Code dưới đây in các phần tử theo thứ tự xoắn ốc. Với ma trận 3 × 4 chứa $1..12$ theo hàng, kết quả là 1 2 3 4 8 12 11 10 9 5 6 7.

Xem code C++ / Python: in ma trận theo thứ tự xoắn ốc bằng 4 biên u, d, l, r (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

int a[1005][1005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) cin >> a[i][j];
    int u = 0, d = n - 1, l = 0, r = m - 1;       // 4 biên của lớp hiện tại
    while(u <= d && l <= r){
        for(int j = l; j <= r; j++) cout << a[u][j] << " ";      // hàng trên: trái -> phải
        u++;
        for(int i = u; i <= d; i++) cout << a[i][r] << " ";      // cột phải: trên -> dưới
        r--;
        if(u <= d){                                              // còn hàng dưới
            for(int j = r; j >= l; j--) cout << a[d][j] << " ";  // hàng dưới: phải -> trái
            d--;
        }
        if(l <= r){                                              // còn cột trái
            for(int i = d; i >= u; i--) cout << a[i][l] << " ";  // cột trái: dưới -> trên
            l++;
        }
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [list(map(int, data[2 + i * m: 2 + (i + 1) * m])) for i in range(n)]
u, d, l, r = 0, n - 1, 0, m - 1        # 4 biên của lớp hiện tại
res = []
while u <= d and l <= r:
    for j in range(l, r + 1):          # hàng trên: trái -> phải
        res.append(a[u][j])
    u += 1
    for i in range(u, d + 1):          # cột phải: trên -> dưới
        res.append(a[i][r])
    r -= 1
    if u <= d:                         # còn hàng dưới
        for j in range(r, l - 1, -1):
            res.append(a[d][j])
        d -= 1
    if l <= r:                         # còn cột trái
        for i in range(d, u - 1, -1):
            res.append(a[i][l])
        l += 1
print(*res)

Lớp trong cùng chỉ còn một hàng hoặc một cột

Đây là chỗ sai kinh điển của cách 2. Với ma trận 1 × 4: đi hàng trên xong thì u = 1 > d = 0; nếu không có điều kiện if(u <= d) trước khi đi hàng dưới, code sẽ in lại các số theo chiều ngược và mỗi số xuất hiện hai lần. Khi tự viết, em luôn thử với 1 hàng, 1 cột và ma trận vuông cạnh lẻ.

Phần 4Xoay, lật và chuyển vị ma trận

Xoay một tấm ảnh 90° chính là xoay ma trận điểm ảnh. Đừng cố tưởng tượng cả tấm ảnh quay, hãy hỏi một câu đơn giản: ô $a[i][j]$ sẽ bay về ô nào? Xét xoay 90° theo chiều kim đồng hồ ma trận $n$ hàng, $m$ cột. Ma trận mới $b$ có $m$ hàng, $n$ cột, và:

• hàng trên cùng của $a$ (hàng 0) trở thành cột phải nhất của $b$ (cột $n - 1$), hàng 1 thành cột $n - 2$… tức là hàng $i$ thành cột $n - 1 - i$;
• trong một hàng, đọc từ trái sang phải (cột $j$ tăng) thì trong cột mới đọc từ trên xuống (hàng $j$ tăng).

Ghép lại: $b[j][n - 1 - i] = a[i][j]$. Em bấm từng bước để xem mỗi ô bay đi đâu, và đổi sang các phép biến đổi khác:

MÔ PHỎNGXoay ma trận: mỗi ô a[i][j] bay về đâu?Nhập ma trận (mỗi hàng một dòng, tối đa 5 × 5), chọn phép biến đổi rồi bấm Tiếp.

Ma trận a1 2 3 4 5 6Phép biến đổiXoay 90° thuậnXoay 90° ngượcChuyển vị

ChậmVừaNhanh

ô đang chuyểnđã chuyển xongô của b chưa có số

Phép biến đổi	Kích thước mới	Công thức	Ghi nhớ
Xoay 90° thuận chiều kim đồng hồ	$m \times n$	$b[j][n-1-i] = a[i][j]$	hàng trên → cột phải
Xoay 90° ngược chiều	$m \times n$	$b[m-1-j][i] = a[i][j]$	cột phải → hàng trên
Xoay 180°	$n \times m$	$b[n-1-i][m-1-j] = a[i][j]$	đảo cả hàng lẫn cột
Chuyển vị (lật qua đường chéo chính)	$m \times n$	$b[j][i] = a[i][j]$	đổi vai hàng và cột
Lật ngang (gương trái phải)	$n \times m$	$b[i][m-1-j] = a[i][j]$	đảo từng hàng
Lật dọc (trên xuống dưới)	$n \times m$	$b[n-1-i][j] = a[i][j]$	đảo thứ tự các hàng

Bảng 4. Công thức chỉ số của các phép biến đổi. Luôn khai báo ma trận mới $b$, không ghi đè trực tiếp lên $a$.

Mẹo xoay $k$ lần. Xoay 4 lần 90° thì ma trận về như cũ, nên xoay $k$ lần giống hệt xoay $k \bmod 4$ lần. Dù $k = 10^{18}$ em cũng chỉ xoay tối đa 3 lần. Xoay ngược chiều $k$ lần bằng xoay thuận $(4 - k \bmod 4) \bmod 4$ lần. Code dưới đây đọc ma trận, xoay thuận $k$ lần và in kích thước mới kèm ma trận:

Xem code C++ / Python: xoay ma trận 90° theo chiều kim đồng hồ k lần (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> rotate90(const vector<vector<int>> &a){   // xoay 90° theo chiều kim đồng hồ
    int n = a.size(), m = a[0].size();
    vector<vector<int>> b(m, vector<int>(n));                 // b có m hàng, n cột
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            b[j][n - 1 - i] = a[i][j];
    return b;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    long long k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int>(m));
    for(auto &row : a) for(auto &x : row) cin >> x;
    k %= 4;                                  // xoay 4 lần là về như cũ
    for(int t = 0; t < k; t++) a = rotate90(a);
    cout << a.size() << " " << a[0].size() << "\n";
    for(auto &row : a){
        for(int x : row) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

import sys

def rotate90(a):                       # xoay 90° theo chiều kim đồng hồ
    n, m = len(a), len(a[0])
    b = [[0] * n for _ in range(m)]    # b có m hàng, n cột
    for i in range(n):
        for j in range(m):
            b[j][n - 1 - i] = a[i][j]
    return b

data = sys.stdin.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
a = [list(map(int, data[3 + i * m: 3 + (i + 1) * m])) for i in range(n)]
for _ in range(k % 4):                 # xoay 4 lần là về như cũ
    a = rotate90(a)
out = [f"{len(a)} {len(a[0])}"]
out += [' '.join(map(str, row)) for row in a]
print('\n'.join(out))

Ghép các phép đơn giản

Xoay 90° thuận = chuyển vị rồi lật ngang (em thử với ma trận 2 × 2 sẽ thấy). Xoay 180° = lật ngang rồi lật dọc. Với ma trận vuông, chuyển vị và lật đều làm được tại chỗ bằng swap, nên xoay tại chỗ không cần mảng phụ. Trong Python còn có mẹo một dòng: b = [list(r) for r in zip(*a[::-1])] là xoay 90° thuận.

Ma trận không vuông

Khi $n \ne m$, xoay 90° làm đổi kích thước thành $m \times n$. Lỗi hay gặp: khai báo b cùng cỡ $n \times m$ với a, hoặc in theo $n$ hàng cũ. Sau mỗi lần xoay, nhớ đổi chỗ $n$ và $m$.

Phần 5Mô phỏng ngày tháng, giờ phút giây và mẹo tìm chu kỳ

Bài ngày tháng cũng là mô phỏng: lịch chạy từng ngày, hết tháng thì sang tháng, hết năm thì sang năm. Hai “viên gạch” cần thuộc lòng:

• Năm nhuận (lịch Gregory ta đang dùng): năm chia hết cho 400, hoặc chia hết cho 4 nhưng không chia hết cho 100. Ví dụ 2024 và 2000 nhuận; 1900 và 2100 không nhuận.
• Số ngày trong tháng: lưu sẵn mảng {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} (phần tử 0 bỏ trống để tháng $m$ ứng với chỉ số $m$), riêng tháng 2 năm nhuận có 29 ngày.

Ngày tiếp theo: tăng ngày lên 1; nếu vượt số ngày của tháng thì về ngày 1 và tăng tháng; nếu tháng vượt 12 thì về tháng 1 và tăng năm. Cộng thêm $k$ ngày: lặp lại việc đó $k$ lần.

Ngày	+1 ngày	Lý do
28/02/2024	29/02/2024	2024 chia hết cho 4, không chia hết cho 100 → nhuận
28/02/1900	01/03/1900	1900 chia hết cho 100 nhưng không chia hết cho 400 → không nhuận
30/04/2026	01/05/2026	tháng 4 có 30 ngày
31/12/2025	01/01/2026	tháng vượt 12 → sang năm mới

Bảng 5. Những trường hợp cần thử khi viết hàm “ngày tiếp theo”.

Khi nào mô phỏng quá chậm? Nếu $k \le 10^7$, lặp từng ngày là đủ nhanh. Nhưng nếu $k = 10^{18}$ thì lặp từng ngày mất hàng chục nghìn năm! Lúc đó em hãy tìm chu kỳ: quy luật năm nhuận lặp lại sau đúng 400 năm, và 400 năm có $400 \cdot 365 + 97 = 146097$ ngày (97 năm nhuận). Vậy cộng $146097$ ngày thì ngày, tháng giữ nguyên còn năm tăng đúng 400. Ta “nhảy” nhanh $k / 146097$ chu kỳ, phần còn lại $k \bmod 146097$ mới mô phỏng từng ngày.

Xem code C++ / Python: cộng thêm k ngày (k tới 10^18) bằng chu kỳ 400 năm (bấm để mở)

#include <bits/stdc++.h>
using namespace std;

bool isLeap(long long y){                         // năm nhuận
    return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
}

int daysIn(int m, long long y){                   // số ngày của tháng m năm y
    int md[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if(m == 2 && isLeap(y)) return 29;
    return md[m];
}

int main(){
    long long d, m, y, k;
    cin >> d >> m >> y >> k;
    y += 400 * (k / 146097);                      // 400 năm có đúng 146097 ngày
    k %= 146097;
    while(k > 0){                                 // mô phỏng từng ngày (< 146097 lần)
        d++;
        if(d > daysIn(m, y)){ d = 1; m++; }       // sang tháng mới
        if(m > 12){ m = 1; y++; }                 // sang năm mới
        k--;
    }
    cout << d << " " << m << " " << y;
    return 0;
}

def is_leap(y):                              # năm nhuận
    return (y % 4 == 0 and y % 100 != 0) or y % 400 == 0

def days_in(m, y):                           # số ngày của tháng m năm y
    md = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    if m == 2 and is_leap(y):
        return 29
    return md[m]

d, m, y, k = map(int, input().split())
y += 400 * (k // 146097)                     # 400 năm có đúng 146097 ngày
k %= 146097
while k > 0:                                 # mô phỏng từng ngày (< 146097 lần)
    d += 1
    if d > days_in(m, y):                    # sang tháng mới
        d, m = 1, m + 1
    if m > 12:                               # sang năm mới
        m, y = 1, y + 1
    k -= 1
print(d, m, y)

Thứ trong tuần. Chọn một mốc đã biết thứ, rồi đếm số ngày từ mốc tới ngày cần hỏi; lấy số đó chia 7 lấy dư. Mốc tiện nhất là ngày 01/01/0001 (lịch Gregory kéo dài về trước), đó là Thứ Hai. Số ngày đã trôi qua trước ngày $d/m/y$ là:

$$S = 365(y - 1) + \left\lfloor \frac{y-1}{4} \right\rfloor - \left\lfloor \frac{y-1}{100} \right\rfloor + \left\lfloor \frac{y-1}{400} \right\rfloor + (\text{số ngày các tháng } 1..m-1 \text{ của năm } y) + d - 1$$

Ba số hạng chia lấy phần nguyên đếm số năm nhuận trước năm $y$. Khi đó $S \bmod 7 = 0$ là Thứ Hai, $1$ là Thứ Ba, …, $6$ là Chủ Nhật. Ví dụ ngày 24/10/2026 có $S \bmod 7 = 5$ nên là Thứ Bảy. Công thức không có vòng lặp nên chạy được cả với năm $10^9$ (bài tập 7). Cùng ý tưởng “đổi ra một con số rồi tính”, hai ngày cách nhau bao nhiêu ngày chính là hiệu hai giá trị $S$.

Đổi giờ:phút:giây

Cách gọn nhất là đổi hết ra giây, tính toán trên số nguyên rồi đổi ngược lại:

long long t = h * 3600 + m * 60 + s;      // đổi ra giây
t = ((t + k) % 86400 + 86400) % 86400;    // cộng k giây, quay vòng 24 giờ (k có thể âm)
h = t / 3600; m = t % 3600 / 60; s = t % 60;
printf("%02lld:%02lld:%02lld", h, m, s);   // in đủ 2 chữ số

Một ngày có $24 \cdot 3600 = 86400$ giây. Phép + 86400 rồi % 86400 lần nữa giúp kết quả không âm khi lùi giờ (trong C++, số âm chia lấy dư cho kết quả âm).

Tìm chu kỳ trong mô phỏng nói chung

Nếu trạng thái của quá trình chỉ có hữu hạn khả năng (vị trí trên lưới, hướng nhìn, giờ trong ngày…), thì sau một lúc trạng thái chắc chắn lặp lại. Lưu thời điểm đầu tiên gặp mỗi trạng thái; khi gặp lại trạng thái đã thấy ở thời điểm $f$ vào thời điểm $t$, chu kỳ dài $t - f$, và em chỉ cần mô phỏng thêm $(k - t) \bmod (t - f)$ bước. Bài tập 8 dùng đúng kỹ thuật này.

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

• Đếm số phần tử cực đại trong ma trận (Dễ)
• Số ngày trong tháng (Dễ)
• Khóa Số (HSG12 Hà Nội 2025 – Bài 1) (Dễ)
• Con Ốc Sên (SNAIL) (Dễ)
• Cyclically Rotating a Grid (LeetCode 1914) (Trung bình)
• Ma trận xoắn ốc 2 (Trung bình)
• Trò Chơi (HSG9 Hà Nội 2025 – Bài 4) (Khá)

Xem toàn bộ bài cùng chủ đề: nhãn Mô phỏng.

Bài tậpLuyện mô phỏng trên lưới

Bài 1Dò mìnDễ

Cho lưới $n \times m$ ($1 \le n, m \le 100$) gồm ký tự . (ô trống) và * (mìn). In ra lưới mới: ô mìn giữ nguyên *, mỗi ô trống thay bằng số mìn trong 8 ô xung quanh nó.

Input

3 4
*...
..*.
....

Output

*211
12*1
0111

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đúng ví dụ ở phần 1: dùng mảng 8 hướng và kiểm tra ô kề nằm trong lưới trước khi đọc. Ô $(0, 1)$ kề với hai mìn ở $(0, 0)$ và $(1, 2)$ nên ghi 2.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int n, m;
string g[105];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

bool inside(int x, int y){              // ô (x, y) có nằm trong lưới không?
    return x >= 0 && x < n && y >= 0 && y < m;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> g[i];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(g[i][j] == '*'){ cout << '*'; continue; }
            int cnt = 0;
            for(int k = 0; k < 8; k++){
                int x = i + dx[k], y = j + dy[k];
                if(inside(x, y) && g[x][y] == '*') cnt++;   // kiểm tra biên TRƯỚC
            }
            cout << cnt;
        }
        cout << '\n';
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

out = []
for i in range(n):
    row = []
    for j in range(m):
        if g[i][j] == '*':
            row.append('*')
            continue
        cnt = 0
        for k in range(8):
            x, y = i + dx[k], j + dy[k]
            if 0 <= x < n and 0 <= y < m and g[x][y] == '*':   # kiểm tra biên TRƯỚC
                cnt += 1
        row.append(str(cnt))
    out.append(''.join(row))
print('\n'.join(out))

Bài 2Ô đỉnh núiDễ

Bản đồ độ cao là lưới $n \times m$ số nguyên ($1 \le n, m \le 1000$, $0 \le a_{ij} \le 10^9$). Ô $(i, j)$ là đỉnh núi nếu nó lớn hơn hẳn mọi ô chung cạnh với nó (ô ở biên chỉ so với các ô kề nằm trong lưới). Đếm số đỉnh núi.

Input

3 3
1 5 2
4 3 6
7 1 8

Output

3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Với mỗi ô, duyệt 4 hướng bằng dx, dy; gặp một ô kề trong lưới mà lớn hơn hoặc bằng thì ô này không phải đỉnh. Ba đỉnh là 5 (kề 1, 2, 3), 7 (kề 4, 1) và 8 (kề 6, 1). Ô 6 không phải đỉnh vì kề với 8. Lưới 1 × 1 có đúng một đỉnh vì không có ô kề nào.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int a[1005][1005];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) cin >> a[i][j];
    int cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            bool peak = true;
            for(int k = 0; k < 4; k++){
                int x = i + dx[k], y = j + dy[k];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(a[x][y] >= a[i][j]){ peak = false; break; }
            }
            if(peak) cnt++;
        }
    cout << cnt;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [list(map(int, data[2 + i * m: 2 + (i + 1) * m])) for i in range(n)]
cnt = 0
for i in range(n):
    for j in range(m):
        v = a[i][j]
        if i > 0 and a[i - 1][j] >= v: continue
        if i < n - 1 and a[i + 1][j] >= v: continue
        if j > 0 and a[i][j - 1] >= v: continue
        if j < m - 1 and a[i][j + 1] >= v: continue
        cnt += 1
print(cnt)

Bài 3Robot quay đầuDễ

Robot đứng ở gốc toạ độ $(0, 0)$ trên mặt phẳng rộng vô hạn, mặt hướng về phía Bắc (trục $y$ tăng). Trục $x$ tăng về phía Đông. Robot nhận xâu lệnh độ dài không quá $10^5$ gồm: F đi thẳng 1 đơn vị, L quay trái 90°, R quay phải 90°. In ra toạ độ cuối cùng $x$, $y$ và hướng cuối cùng (N, E, S, W).

Input

FFRFFFLLF

Output

2 2 W

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Xếp 4 hướng theo chiều kim đồng hồ: Bắc, Đông, Nam, Tây với dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0}. Quay phải d = (d + 1) % 4, quay trái d = (d + 3) % 4. Chạy tay: đi lên tới $(0, 2)$, quay sang Đông, đi tới $(3, 2)$, quay trái hai lần thành hướng Tây, đi 1 bước về $(2, 2)$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    int dx[4] = {0, 1, 0, -1};      // N, E, S, W (chiều kim đồng hồ)
    int dy[4] = {1, 0, -1, 0};
    string name = "NESW";
    int x = 0, y = 0, d = 0;
    for(char c : s){
        if(c == 'R') d = (d + 1) % 4;
        else if(c == 'L') d = (d + 3) % 4;
        else { x += dx[d]; y += dy[d]; }
    }
    cout << x << " " << y << " " << name[d];
    return 0;
}

s = input().strip()
dx = [0, 1, 0, -1]          # N, E, S, W (chiều kim đồng hồ)
dy = [1, 0, -1, 0]
x = y = d = 0
for c in s:
    if c == 'R':
        d = (d + 1) % 4
    elif c == 'L':
        d = (d + 3) % 4
    else:
        x += dx[d]
        y += dy[d]
print(x, y, 'NESW'[d])

Bài 4Ngày hôm sauDễ

Cho một ngày hợp lệ $d$, $m$, $y$ ($1 \le y \le 9998$). In ra ngày hôm sau theo dạng dd/mm/yyyy: ngày và tháng luôn đủ 2 chữ số, năm in bình thường.

Input

28 2 2024

Output

29/02/2024

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dùng hàm năm nhuận và mảng số ngày trong tháng ở phần 5. Tăng ngày; nếu vượt số ngày của tháng thì ngày = 1, tăng tháng; nếu tháng vượt 12 thì tháng = 1, tăng năm. In đủ 2 chữ số bằng printf("%02d/%02d/%d") trong C++ hoặc f"{d:02d}" trong Python. 2024 là năm nhuận nên sau 28/02 là 29/02.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

bool isLeap(int y){ return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; }

int main(){
    int d, m, y;
    cin >> d >> m >> y;
    int md[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if(isLeap(y)) md[2] = 29;
    d++;
    if(d > md[m]){ d = 1; m++; }
    if(m > 12){ m = 1; y++; }
    printf("%02d/%02d/%d", d, m, y);
    return 0;
}

def is_leap(y):
    return (y % 4 == 0 and y % 100 != 0) or y % 400 == 0

d, m, y = map(int, input().split())
md = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
if is_leap(y):
    md[2] = 29
d += 1
if d > md[m]:
    d, m = 1, m + 1
if m > 12:
    m, y = 1, y + 1
print(f"{d:02d}/{m:02d}/{y}")

Bài 5Xoắn ốc ngược chiềuTrung bình

Điền các số $1..n \cdot m$ vào lưới $n \times m$ ($1 \le n, m \le 100$) theo hình xoắn ốc ngược chiều kim đồng hồ: bắt đầu từ góc trên trái, đi xuống trước, rồi sang phải, lên, sang trái và cuộn dần vào trong. In lưới.

Input

3 4

Output

1 10 9 8
2 11 12 7
3 4 5 6

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Vẫn là quy tắc “đi thẳng, bị chặn thì rẽ”, chỉ đổi mảng hướng thành: xuống, phải, lên, trái. Đi xuống mà rẽ sang phải màn hình thật ra là rẽ trái theo góc nhìn của bút, nên ta được xoắn ốc ngược chiều, nhưng trong code vẫn chỉ là d = (d + 1) % 4. Mẫu: cột 0 điền 1, 2, 3; hàng dưới điền 4, 5, 6; cột phải đi lên 7, 8; hàng trên sang trái 9, 10; rồi 11, 12 ở lõi.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int a[105][105];
int dx[4] = {1, 0, -1, 0};      // xuống, phải, lên, trái
int dy[4] = {0, 1, 0, -1};

int main(){
    int n, m;
    cin >> n >> m;
    int x = 0, y = 0, d = 0;
    for(int v = 1; v <= n * m; v++){
        a[x][y] = v;
        int nx = x + dx[d], ny = y + dy[d];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] != 0){
            d = (d + 1) % 4;
            nx = x + dx[d]; ny = y + dy[d];
        }
        x = nx; y = ny;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cout << a[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

n, m = map(int, input().split())
a = [[0] * m for _ in range(n)]
dx = [1, 0, -1, 0]      # xuống, phải, lên, trái
dy = [0, 1, 0, -1]
x = y = d = 0
for v in range(1, n * m + 1):
    a[x][y] = v
    nx, ny = x + dx[d], y + dy[d]
    if not (0 <= nx < n and 0 <= ny < m) or a[nx][ny] != 0:
        d = (d + 1) % 4
        nx, ny = x + dx[d], y + dy[d]
    x, y = nx, ny
print('\n'.join(' '.join(map(str, row)) for row in a))

Bài 6Xoay ảnh nhiều lầnTrung bình

Cho ma trận $n \times m$ ($1 \le n, m \le 300$, $|a_{ij}| \le 10^9$) và số $k$ ($0 \le k \le 10^{18}$). Xoay ma trận 90° theo chiều kim đồng hồ $k$ lần. In ra kích thước mới (số hàng, số cột) trên một dòng, sau đó là ma trận.

Input

2 3 1
1 2 3
4 5 6

Output

3 2
4 1
5 2
6 3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Xoay 4 lần là về như cũ nên chỉ cần xoay $k \bmod 4$ lần, mỗi lần dùng công thức $b[j][n - 1 - i] = a[i][j]$ và nhớ đổi kích thước thành $m \times n$. $k$ tới $10^{18}$ nên phải đọc bằng long long. Mẫu: hàng trên 1 2 3 trở thành cột phải, đọc từ trên xuống.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> rotate90(const vector<vector<int>> &a){   // xoay 90° theo chiều kim đồng hồ
    int n = a.size(), m = a[0].size();
    vector<vector<int>> b(m, vector<int>(n));                 // b có m hàng, n cột
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            b[j][n - 1 - i] = a[i][j];
    return b;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    long long k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int>(m));
    for(auto &row : a) for(auto &x : row) cin >> x;
    k %= 4;                                  // xoay 4 lần là về như cũ
    for(int t = 0; t < k; t++) a = rotate90(a);
    cout << a.size() << " " << a[0].size() << "\n";
    for(auto &row : a){
        for(int x : row) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

import sys

def rotate90(a):                       # xoay 90° theo chiều kim đồng hồ
    n, m = len(a), len(a[0])
    b = [[0] * n for _ in range(m)]    # b có m hàng, n cột
    for i in range(n):
        for j in range(m):
            b[j][n - 1 - i] = a[i][j]
    return b

data = sys.stdin.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
a = [list(map(int, data[3 + i * m: 3 + (i + 1) * m])) for i in range(n)]
for _ in range(k % 4):                 # xoay 4 lần là về như cũ
    a = rotate90(a)
out = [f"{len(a)} {len(a[0])}"]
out += [' '.join(map(str, row)) for row in a]
print('\n'.join(out))

Bài 7Hôm ấy là thứ mấy?Trung bình

Có $Q$ câu hỏi ($Q \le 10^5$), mỗi câu cho một ngày hợp lệ $d$, $m$, $y$ theo lịch Gregory ($1 \le y \le 10^9$). Với mỗi câu, in ra thứ của ngày đó: Thứ Hai, Thứ Ba, Thứ Tư, Thứ Năm, Thứ Sáu, Thứ Bảy hoặc Chủ Nhật. Biết ngày 01/01/0001 là Thứ Hai.

Input

3
24 10 2026
2 9 1945
1 1 1

Output

Thứ Bảy
Chủ Nhật
Thứ Hai

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Năm tới $10^9$ nên không thể đếm từng ngày. Dùng công thức $S$ ở phần 5: số ngày từ 01/01/0001 tới ngày cần hỏi, gồm $365(y-1)$, cộng số năm nhuận trước năm $y$, cộng số ngày các tháng trước tháng $m$, cộng $d - 1$. $S$ có thể tới khoảng $3{,}7 \cdot 10^{11}$ nên dùng long long. Thứ là $S \bmod 7$ (0 là Thứ Hai). Ngày Quốc khánh 2/9/1945 rơi vào Chủ Nhật.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

bool isLeap(long long y){ return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0; }

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int md[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    string name[7] = {"Thứ Hai", "Thứ Ba", "Thứ Tư", "Thứ Năm", "Thứ Sáu", "Thứ Bảy", "Chủ Nhật"};
    int q;
    cin >> q;
    while(q--){
        long long d, m, y;
        cin >> d >> m >> y;
        long long p = y - 1;
        long long S = 365 * p + p / 4 - p / 100 + p / 400;    // các năm trọn vẹn trước năm y
        for(int t = 1; t < m; t++){
            S += md[t];
            if(t == 2 && isLeap(y)) S++;                       // tháng 2 năm nhuận
        }
        S += d - 1;
        cout << name[S % 7] << "\n";
    }
    return 0;
}

import sys

def is_leap(y):
    return (y % 4 == 0 and y % 100 != 0) or y % 400 == 0

md = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
name = ["Thứ Hai", "Thứ Ba", "Thứ Tư", "Thứ Năm", "Thứ Sáu", "Thứ Bảy", "Chủ Nhật"]
data = sys.stdin.read().split()
q = int(data[0])
out = []
for k in range(q):
    d, m, y = int(data[1 + 3 * k]), int(data[2 + 3 * k]), int(data[3 + 3 * k])
    p = y - 1
    S = 365 * p + p // 4 - p // 100 + p // 400      # các năm trọn vẹn trước năm y
    S += sum(md[1:m])
    if m > 2 and is_leap(y):                        # đã qua tháng 2 năm nhuận
        S += 1
    S += d - 1
    out.append(name[S % 7])
print('\n'.join(out))

Bài 8Con kiến theo mũi tênKhá

Lưới $n \times m$ ($1 \le n, m \le 1000$), mỗi ô ghi một mũi tên U, D, L hoặc R. Con kiến đứng ở ô $(r, c)$ (đánh số từ 1). Mỗi giây, kiến bò 1 ô theo mũi tên của ô nó đang đứng. Cho $k$ ($0 \le k \le 10^{18}$). Nếu kiến bò ra khỏi lưới ở giây thứ $t \le k$ thì in THOAT t; ngược lại in vị trí của kiến sau $k$ giây.

Dòng đầu: $n$, $m$, $k$. Dòng hai: $r$, $c$. Tiếp theo là $n$ dòng của lưới.

Input

3 4 10
1 1
RRDL
URDD
ULLL

Output

1 3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Kiến chỉ có $n \cdot m$ vị trí, nên nếu không ra ngoài thì sau tối đa $n \cdot m$ giây nó chắc chắn quay lại một ô đã đi qua, và từ đó lặp lại mãi. Lưu first[x][y] = giây đầu tiên kiến đứng ở ô đó (−1 nếu chưa). Khi tới ô đã có first $= f$ ở giây $t$, chu kỳ dài $L = t - f$; chỉ cần mô phỏng thêm $(k - t) \bmod L$ bước. Mẫu: kiến đi vòng 8 ô (1,1) → (1,2) → (1,3) → (2,3) → (3,3) → (3,2) → (3,1) → (2,1) → (1,1); sau 8 giây về chỗ cũ, còn 2 giây nữa tới (1, 3).

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int n, m;
string g[1005];
long long first_[1005][1005];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    long long k;
    int x, y;
    cin >> n >> m >> k >> x >> y;
    x--; y--;
    for(int i = 0; i < n; i++) cin >> g[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) first_[i][j] = -1;
    string dirs = "URDL";
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    long long t = 0;
    while(t < k){
        if(first_[x][y] != -1){                       // gặp lại ô cũ: có chu kỳ
            long long L = t - first_[x][y];
            long long rest = (k - t) % L;
            for(long long s = 0; s < rest; s++){       // đi nốt phần dư (luôn ở trong chu kỳ)
                int d = dirs.find(g[x][y]);
                x += dx[d]; y += dy[d];
            }
            break;
        }
        first_[x][y] = t;
        int d = dirs.find(g[x][y]);
        x += dx[d]; y += dy[d];
        t++;
        if(x < 0 || x >= n || y < 0 || y >= m){
            cout << "THOAT " << t;
            return 0;
        }
    }
    cout << x + 1 << " " << y + 1;
    return 0;
}

import sys

data = sys.stdin.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
x, y = int(data[3]) - 1, int(data[4]) - 1
g = data[5:5 + n]
first = [[-1] * m for _ in range(n)]
move = {'U': (-1, 0), 'R': (0, 1), 'D': (1, 0), 'L': (0, -1)}
t = 0
out = None
while t < k:
    if first[x][y] != -1:                      # gặp lại ô cũ: có chu kỳ
        rest = (k - t) % (t - first[x][y])
        for _ in range(rest):                  # đi nốt phần dư (luôn ở trong chu kỳ)
            a, b = move[g[x][y]]
            x, y = x + a, y + b
        break
    first[x][y] = t
    a, b = move[g[x][y]]
    x, y = x + a, y + b
    t += 1
    if not (0 <= x < n and 0 <= y < m):
        out = 'THOAT %d' % t
        break
print(out if out else '%d %d' % (x + 1, y + 1))

Chuyên đề tiếp theo · Chuyên đề 5

Xử lý xâu trong đề thi

Chuẩn hoá xâu, tách từ, tách số ra khỏi xâu, đếm tần suất, nén xâu và những bẫy đọc dữ liệu hay làm mất điểm trong đề HSG.

Học chuyên đề 5 →

← Chuyên đề 3: Số nguyên lớnXem cả 10 chuyên đề nhập môn

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 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!