Rote (Tin học trẻ toàn quốc 2024 – Vòng sơ khảo – Bảng B, C2)
Đề 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.
9 9 9 9
1 2 3 4
5 6 7 8
2
1 21 9 9 4
5 9 9 8
6 2 7 3Lờ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ày chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
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ộ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):
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.
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ì.
memcpy(b, a, sizeof(a))chép toàn bộ mảngasangb– phải làm trong vòng lặp, ở mỗi phép, vì bảng đã thay đổi sau phép trước.- 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.
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).
- 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. - Viết
(p + 7) % 8thay cho(p - 1) % 8vì trong C++(0 - 1) % 8 = -1, chỉ số âm sẽ sai. - Mảng
vđóng vai trò "bản sao" giốngbở Cách 2, nên không bị lỗi ghi đè.
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
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ữ.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.
Nhận xét
Đăng nhận xét