Hướng dẫn giải của Dãy số (đề Hòa Bình 2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Mỗi lần quay chuyển phần tử đầu xuống cuối, nên sau k lần quay dãy trở thành a[k mod n], a[k mod n + 1], .... Phần tử đầu tiên khi đó là a[k mod n] (chỉ số bắt đầu từ 0). Vì k có thể lên tới 10^9 nên không thể mô phỏng trực tiếp với n lớn.
Sub 1: Vét cạn — ~O(k \cdot n)~
Thực hiện đúng k lần thao tác: mỗi lần dịch cả dãy sang trái một vị trí và đưa phần tử đầu xuống cuối. In a[0] sau cùng. Đúng theo đề nhưng khi k lớn thì rất chậm.
Kết quả chấm: đạt 16/30 test (14 test còn lại quá giờ, không sai).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DAYSO.INP", "r")) { freopen("DAYSO.INP", "r", stdin); freopen("DAYSO.OUT", "w", stdout); }
long long n, k;
cin >> n >> k;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vet can: thuc hien dung k lan thao tac, moi lan chuyen so dau xuong cuoi
for (long long step = 0; step < k; step++) {
long long first = a[0];
for (long long i = 0; i + 1 < n; i++) a[i] = a[i + 1];
a[n - 1] = first;
}
cout << a[0] << "\n";
return 0;
}
Sub 2: Dùng phép chia lấy dư — ~O(1)~
Quay n lần thì dãy trở về như cũ, nên chỉ cần k mod n lần. Khi đó đáp án là a[k mod n]. Dùng long long cho n và k để đọc dữ liệu an toàn.
Kết quả chấm: đạt 30/30 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("DAYSO.INP", "r")) { freopen("DAYSO.INP", "r", stdin); freopen("DAYSO.OUT", "w", stdout); }
long long n, k;
cin >> n >> k;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Sau k lan quay, phan tu dau tien la phan tu co chi so k mod n (chi so bat dau tu 0)
cout << a[k % n] << "\n";
return 0;
}
Bình luận