Hướng dẫn giải của Trò chơi Pinball (KS2)
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
Quả bóng đi trên dãy ký tự '<', '>' và mỗi ô bị lật sau khi bóng rời đi; cần tính tổng thời gian bóng ra khỏi lưới.
Sub 1: Mô phỏng — số bước lớn, dùng khi ~n \le 1000~
Mô phỏng đúng theo đề: từ ô hiện tại đi theo ký tự, lật ký tự, đếm giây cho đến khi ra ngoài. Nếu chỉ nộp sub này: đúng 15/20 test.
Sub 2: Quét qua lại — ~O(n)~
Giả sử bóng đang đi sang phải: nó đi qua các ô '>' (các ô này bị lật thành '<') cho đến ô '<' đầu tiên bên phải, đảo chiều. Lúc này mọi ô nó vừa đi qua đều là '<' nên nó chạy thẳng về bên trái qua các ô đó (lật lại thành '>') và tiếp tục qua các ô chưa động tới cho đến ô '>' đầu tiên (theo đề gốc) bên trái vị trí xuất phát, rồi đảo chiều. Như vậy bóng quét qua lại, mỗi lần mở rộng đến ô '<' kế tiếp bên phải hoặc ô '>' kế tiếp bên trái trong dãy gốc. Ta lưu hai danh sách vị trí đó, cộng độ dài từng đoạn quét; khi hết danh sách thì bóng ra ngoài (vị trí 0 hoặc ~n+1~). Đáp án có thể tới cỡ ~n^2~ nên dùng long long. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu (đọc/ghi file PINBALL.inp/PINBALL.out); nếu ~n \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Kết quả: 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int n, p;
string s;
// Sub 1: mô phỏng trực tiếp từng giây — dùng khi n <= 1000
void sub1() {
long long t = 0;
int pos = p;
while (pos >= 1 && pos <= n) {
int nx = (s[pos - 1] == '<') ? pos - 1 : pos + 1;
s[pos - 1] = (s[pos - 1] == '<') ? '>' : '<';
pos = nx;
t++;
}
cout << t << "\n";
}
// Sub 2: quả bóng quét qua lại, mỗi lần đảo chiều tại ô '<' kế tiếp bên phải
// hoặc ô '>' kế tiếp bên trái (ban đầu). Cộng độ dài các đoạn quét — O(n)
void sub2() {
vector<int> R, L; // R: các vị trí j>p có '<' tăng dần; L: các vị trí k<p có '>' giảm dần
for (int j = p + 1; j <= n; j++) if (s[j - 1] == '<') R.push_back(j);
for (int k = p - 1; k >= 1; k--) if (s[k - 1] == '>') L.push_back(k);
long long t = 0;
int pos = p;
bool right = (s[p - 1] == '>');
size_t ir = 0, il = 0;
while (true) {
if (right) {
if (ir == R.size()) { t += n + 1 - pos; break; }
t += R[ir] - pos; pos = R[ir++];
} else {
if (il == L.size()) { t += pos; break; }
t += pos - L[il]; pos = L[il++];
}
right = !right;
}
cout << t << "\n";
}
int main() {
freopen("PINBALL.inp", "r", stdin);
freopen("PINBALL.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> p >> s;
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận