Rote (Tin học trẻ toàn quốc 2024 – Vòng sơ khảo – Bảng B, C2)

Nguồn: Sơ khảo bảng B – Tin học trẻ toàn quốc 2024 (CLUE OJ – Chương 11: Mảng 2 chiều) Độ khó: Dễ Mảng 2 chiều Mô phỏng

Đề bài

Alice có bảng số $A$ kích thước $3 \times 4$. Các hàng được đánh số từ 1 đến 3 từ trên xuống dưới, các cột được đánh số từ 1 đến 4 từ trái sang phải. Ô nằm giao ở hàng $i$ $(1 \le i \le 3)$ và cột $j$ $(1 \le j \le 4)$ được gọi là ô $(i, j)$ và ban đầu chứa số $a_{ij}$.

Alice đã thực hiện liên tục $k$ phép biến đổi, mỗi phép thuộc một trong hai loại dưới đây để nhận được bảng số $B$.

Loại 1: chọn hình vuông kích thước $3 \times 3$ bên trái và quay theo chiều kim đồng hồ (xem Hình 1).

Loại 2: chọn hình vuông kích thước $3 \times 3$ bên phải và quay ngược chiều kim đồng hồ (xem Hình 2).

Yêu cầu: cho dãy $k$ phép biến đổi, hãy xác định bảng $B$.

Dữ liệu nhập:

• Ba dòng đầu, mỗi dòng chứa 4 số nguyên dương mô tả bảng $A$ (các số không vượt quá 100);
• Dòng tiếp theo chứa số nguyên $k$ $(k \le 100)$;
• Dòng tiếp theo chứa $k$ số nguyên, mỗi số bằng 1 (Loại 1) hoặc 2 (Loại 2) mô tả dãy biến đổi.

Dữ liệu xuất: gồm ba dòng, mỗi dòng chứa 4 số nguyên dương mô tả bảng $B$.

Chú ý: có 50% số test có $k = 1$.

Ghi chú trên CLUE OJ: đề gốc ở phần input và output ghi nhầm "bốn" thành "ba" (mỗi dòng chứa "ba" số) – đúng ra là bốn số, mình đã sửa lại ở trên.

Ví dụ – input

9 9 9 9
1 2 3 4
5 6 7 8
2
1 2

Ví dụ – output

1 9 9 4
5 9 9 8
6 2 7 3

Lời mở đầu

Bài đầu tiên của đề sơ khảo Tin học trẻ bảng B 2024, chỉ là mô phỏng trên một bảng $3 \times 4$. Nhưng chữ "quay" trong đề rất dễ làm các bạn hiểu nhầm thành "xoay cả hình vuông 90 độ" – nhìn kỹ Hình 1, Hình 2 sẽ thấy không phải vậy. Mình sẽ đi từ cách chép thẳng theo hình (ăn 50% điểm), lên cách lặp $k$ lần (100%), rồi một cách gọn hơn: xem 8 ô viền như một vòng tròn và dịch vòng 1 bước.

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:

Bộ test100 test, 2 subtaskÝ tưởngdịch vòng 8 ôCách 1k = 1 – 50%Cách 2lặp k lần – 100%Cách 3mảng vòng – 100%Lỗi sai0/100 test

Bộ testBộ test chính thức có gì?

Số test	Bảng	Giá trị trong bảng	$k$
100	luôn $3 \times 4$	1 … 99	1 … 100

Bộ test chia rất rõ thành 3 nhóm theo $k$ (đúng như đề nói "50% số test có $k = 1$"):

Subtask	Các test	$k$	Tổng số phép Loại 1 / Loại 2	Cách 1	Cách 2, 3
1: $k = 1$ (50%)	1 – 50	đúng 1	24 / 26	50/50	50/50
2: không giới hạn thêm (50%)	51 – 70	2 … 9	60 / 50	0/20	20/20
	71 – 100	đúng 100	1544 / 1456	0/30	30/30

Ở subtask 1 có 24 test chỉ dùng Loại 1 và 26 test chỉ dùng Loại 2, nên phải cài đúng cả hai loại mới lấy được trọn 50%. Ở subtask 2 hai loại phép xen kẽ nhau. Vì bảng chỉ có 12 ô và $k \le 100$ nên mọi cách mô phỏng đúng đều chạy tức thì – cái khó của bài là hiểu đúng phép quay chứ không phải tốc độ.

Ý tưởng"Quay" ở đây là dịch 8 ô viền đi 1 bước

Nhìn Hình 1: hình vuông bên trái có ô giữa $a_{22}$ đứng yên. Còn 8 ô viền thì mỗi số tiến 1 ô theo chiều kim đồng hồ: $a_{11}$ sang chỗ $a_{12}$, $a_{12}$ sang chỗ $a_{13}$, $a_{13}$ xuống chỗ $a_{23}$, ..., $a_{21}$ lên chỗ $a_{11}$. Nếu "xoay 90 độ" thì $a_{11}$ phải bay tới góc $a_{13}$, mà Hình 1 không như thế.

Hình 2 cũng vậy, nhưng với hình vuông bên phải (cột 2 đến 4) và các số tiến 1 ô ngược chiều kim đồng hồ: $a_{13}$ sang chỗ $a_{12}$, $a_{12}$ xuống chỗ $a_{22}$, ...

Mấu chốt

Liệt kê 8 ô viền theo chiều kim đồng hồ thành một vòng $v_0, v_1, \dots, v_7$ (bắt đầu từ góc trên trái). Loại 1 = dịch vòng của hình vuông trái sang phải 1 bước ($v_p$ chuyển tới vị trí $p + 1$, $v_7$ quay về vị trí 0). Loại 2 = dịch vòng của hình vuông phải sang trái 1 bước.

Một chi tiết quan trọng khi cài đặt: các phép gán phải dùng giá trị cũ của bảng. Nếu gán thẳng a[1][2] = a[1][1] sau khi đã gán a[1][1] = a[2][1] thì a[1][2] nhận nhầm giá trị mới. Vì thế mình luôn chép bảng ra một bản sao (hoặc chép 8 số viền ra mảng riêng) trước khi biến đổi.

Em nhập bảng $A$ và dãy phép biến đổi rồi bấm Tiếp để xem từng phép dịch vòng 8 ô (số nhỏ ở góc mỗi ô là vị trí trong vòng):

Bảng A (12 số) Dãy phép

Ví dụ nhanh:

Cách 1Subtask k = 1: chép đúng theo hình

Với $k = 1$, chỉ cần làm đúng một phép. Mình giữ bảng ban đầu ở mảng b, rồi nhìn Hình 1 (hoặc Hình 2) chép từng ô của bảng mới: ô $(1, 1)$ mới là $a_{21}$ cũ, nên a[1][1] = b[2][1]; ô $(1, 2)$ mới là $a_{11}$ cũ, nên a[1][2] = b[1][1]... Ô giữa không đổi nên không cần gán.

C++▶ Chạy tay từng dòng codeCách 1 (subtask k = 1): giữ bảng gốc ở b, chép từng ô theo hình.

Dữ liệu vào (stdin) – sửa thoải mái11 12 13 14 21 22 23 24 31 32 33 34 1 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Ở "Ví dụ đề" (k = 2) cách này chỉ làm phép đầu tiên nên in ra kết quả sai – đúng như lý do nó chỉ được 50% điểm.

Không gian$O(1)$

Thời gian$O(1)$ – đúng 8 phép gán

Kết quả chạy thật: đúng 50/100 test – đúng trọn 50 test đầu ($k = 1$), sai toàn bộ 50 test sau vì chỉ làm phép đầu tiên. Bản Python cũng 50/100.

Cách 2Lặp lại k lần (100%)

Từ Cách 1 lên full điểm chỉ cần bọc phần biến đổi trong vòng lặp while(k--). Mỗi vòng đọc loại phép t, chép bảng hiện tại sang b bằng memcpy rồi gán như Cách 1. Vì $k \le 100$ và mỗi phép chỉ 8 phép gán nên chạy tức thì.

C++▶ Chạy tay từng dòng codeCách 2: lặp k lần, mỗi lần chép bảng ra b rồi gán theo hình.

Dữ liệu vào (stdin) – sửa thoải mái9 9 9 9 1 2 3 4 5 6 7 8 2 1 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Thử "8 lần Loại 1": sau 8 lần dịch vòng 1 bước, bảng quay về đúng như ban đầu.

1. memcpy(b, a, sizeof(a)) chép toàn bộ mảng a sang b – phải làm trong vòng lặp, ở mỗi phép, vì bảng đã thay đổi sau phép trước.
2. Mình dùng chỉ số từ 1 cho giống đề (a[4][5]) để chép công thức từ hình sang code không bị lệch.

Không gian$O(1)$

Thời gian$O(k)$ – mỗi phép chép bảng 12 ô và 8 phép gán

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0.03 giây; bản Python đúng 100/100 test, chậm nhất 0.14 giây.

Cách 3Xem 8 ô viền là một vòng và dịch 1 bước

Cách 2 phải chép tay 16 phép gán, dễ gõ nhầm một chỉ số. Cách gọn hơn: lưu sẵn toạ độ 8 ô viền theo chiều kim đồng hồ vào hai mảng rr[], cc[] (cột tính tương đối so với cột bắt đầu c0 của hình vuông). Hàm quay(c0, cw) chép 8 số viền ra mảng v, rồi đặt số ở vị trí p vào vị trí (p + 1) % 8 (cùng chiều kim đồng hồ) hoặc (p + 7) % 8 (ngược chiều, tức là lùi 1).

C++▶ Chạy tay từng dòng codeCách 3: chép 8 ô viền ra mảng v rồi đặt mỗi số vào vị trí kế tiếp trên vòng.

Dữ liệu vào (stdin) – sửa thoải mái9 9 9 9 1 2 3 4 5 6 7 8 2 1 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Dòng 14 (chép 8 ô viền ra v) mình gộp 8 lần lặp thành 1 bước.

1. Loại 1 là quay(1, true): hình vuông bắt đầu ở cột 1; Loại 2 là quay(2, false): hình vuông bắt đầu ở cột 2.
2. Viết (p + 7) % 8 thay cho (p - 1) % 8 vì trong C++ (0 - 1) % 8 = -1, chỉ số âm sẽ sai.
3. Mảng v đóng vai trò "bản sao" giống b ở Cách 2, nên không bị lỗi ghi đè.

Không gian$O(1)$

Thời gian$O(8k)$

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0.03 giây; bản Python đúng 100/100 test, chậm nhất 0.15 giây.

Lỗi hay gặpHai cách hiểu/cài sai, chạy thử trên bộ test

Lỗi A – hiểu "quay" là xoay 90 độ: 0/100 test

Xoay cả hình vuông $3 \times 3$ như xoay ảnh (a[i][j] = b[4 - j][i]) thì góc $a_{11}$ nhảy tới góc $a_{13}$, trong khi đề chỉ dịch 1 ô. Mình chạy thử: sai cả 100 test, kể cả test ví dụ. Bài học: khi đề có hình minh hoạ, hãy đối chiếu từng ô thay vì đoán theo chữ.

Lỗi B – gán thẳng trên mảng, không dùng bản sao: 0/100 test

Bỏ memcpy và viết a[1][1] = a[2][1]; a[1][2] = a[1][1]; ...: giá trị cũ của a[1][1] đã bị ghi đè trước khi kịp chuyển sang a[1][2]. Kết quả: sai cả 100 test.

Ghi chú của mình: Cách 1 đạt đúng 50/100 test (subtask $k = 1$); Cách 2 và Cách 3 (cả C++ lẫn Python) đều đạt 100/100 test, mỗi test dưới 0.2 giây. Hai lỗi "xoay 90 độ" và "không dùng bản sao" đều trượt toàn bộ bộ test – bài dễ nhưng không đọc kỹ hình là mất trắng điểm.

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 😇