Hướng dẫn giải của Những chiếc đồng hồ (Đề HSG KonTum 2021)
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có 9 chiếc đồng hồ, mỗi chiếc ở một trong 4 trạng thái 0..3 (mỗi trạng thái ứng với một góc quay 90°). Có 9 phép biến đổi, mỗi phép quay 90° một nhóm đồng hồ cố định, tức là cộng 1 vào trạng thái của chúng (theo mod 4). Cần đưa tất cả về trạng thái 0 với số phép biến đổi ít nhất.
Nhận xét: làm một phép 4 lần thì các đồng hồ trở lại như cũ, nên mỗi phép chỉ cần dùng 0, 1, 2 hoặc 3 lần. Vì vậy chỉ có 4^9 = 262144 cách chọn số lần cho 9 phép, đủ nhỏ để thử hết.
Sub 1: Vét cạn — ~O(4^9 \cdot 9 \cdot 9)~
Duyệt mọi bộ số lần (x1, ..., x9) với xj thuộc {0, 1, 2, 3}, mỗi bộ được biểu diễn như một số trong hệ cơ số 4. Với mỗi bộ, cộng xj vào các đồng hồ thuộc phép j, kiểm tra mọi đồng hồ có về 0 (mod 4) hay không. Trong các bộ hợp lệ, lấy tổng x_j nhỏ nhất. Bỏ qua bộ nào đã có tổng không nhỏ hơn đáp án tốt nhất để chạy nhanh hơn.
Bài này không có subtask và chỉ có một trường hợp kích thước cố định, không có chỗ để cải tiến hợp lý nên chỉ viết một sub.
Chấm riêng: đúng 25/25 test.
Chương trình hoàn chỉnh
main đọc 9 trạng thái ban đầu và gọi sub1 để in số phép biến đổi ít nhất.
#include <bits/stdc++.h>
using namespace std;
int s[9]; // trạng thái ban đầu của các đồng hồ A..I (0..3)
// Mỗi phép biến đổi j (j = 0..8) quay 90° các đồng hồ trong danh sách: tương đương cộng 1 (mod 4) vào trạng thái của chúng.
// op[j][i] = 1 nếu phép j tác động lên đồng hồ i (A=0, ..., I=8).
int op[9][9] = {
{1, 1, 0, 1, 1, 0, 0, 0, 0}, // 1: A B D E
{1, 1, 1, 0, 0, 0, 0, 0, 0}, // 2: A B C
{0, 1, 1, 0, 1, 1, 0, 0, 0}, // 3: B C E F
{1, 0, 0, 1, 0, 0, 1, 0, 0}, // 4: A D G
{0, 1, 0, 1, 1, 1, 0, 1, 0}, // 5: B D E F H
{0, 0, 1, 0, 0, 1, 0, 0, 1}, // 6: C F I
{0, 0, 0, 1, 1, 0, 1, 1, 0}, // 7: D E G H
{0, 0, 0, 0, 0, 0, 1, 1, 1}, // 8: G H I
{0, 0, 0, 0, 1, 1, 0, 1, 1}, // 9: E F H I
};
// Sub 1: vét cạn. Mỗi phép chỉ cần làm 0..3 lần (làm đủ 4 lần thì đồng hồ trở lại như cũ),
// nên có 4^9 = 262144 cách chọn số lần cho các phép. Thử hết, giữ cách đủ điều kiện có tổng số lần ít nhất.
// Bài chỉ có 9 phép và 4^9 phương án nên không cần sub nào nhanh hơn.
void sub1() {
int best = INT_MAX;
const int TOTAL = 1 << 18; // 4^9
for (int code = 0; code < TOTAL; code++) {
int x[9], c = code, sum = 0;
for (int j = 0; j < 9; j++) {
x[j] = c % 4;
c /= 4;
sum += x[j];
}
if (sum >= best) continue;
bool ok = true;
for (int i = 0; i < 9 && ok; i++) {
int t = s[i];
for (int j = 0; j < 9; j++)
if (op[j][i]) t += x[j];
if (t % 4 != 0) ok = false; // đồng hồ i chưa về trạng thái 0
}
if (ok) best = sum;
}
cout << best << "\n";
}
int main() {
freopen("dongho.inp", "r", stdin);
freopen("dongho.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 0; i < 9; i++) cin >> s[i];
sub1();
return 0;
}
Bình luận