Hướng dẫn giải của [VTT Q4 Contest 10] Bài 1: Stickers [STICKERS]
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
Hai chữ số 2 và 5 dùng thay cho nhau, 6 và 9 cũng vậy, nên chỉ có 8 loại miếng dán độc lập. Mỗi dãy ~S~ cần một số miếng cố định của từng loại.
Sub 1: Mô phỏng
Gộp 2 với 5 và 6 với 9 thành cùng một loại, đếm số miếng mỗi loại của ~T~, rồi xếp từng dãy ~S~ một, trừ dần số miếng cho tới khi thiếu. Mỗi miếng chỉ bị trừ một lần nên tổng thời gian cỡ ~O(|T| + |S|)~. Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Công thức
Đếm số miếng có ở mỗi loại và số miếng cần ở mỗi loại, đáp án là giá trị nhỏ nhất của ~\lfloor có / cần \rfloor~ trên các loại mà ~S~ có dùng. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc hai xâu, dữ liệu nhỏ gọi sub1, lớn gọi sub2.
#include <bits/stdc++.h>
using namespace std;
string T, S;
// Gộp 2 với 5 và 6 với 9 thành cùng một loại miếng dán
int cls(int d) {
if (d == 5) return 2;
if (d == 9) return 6;
return d;
}
// Sub 1: mô phỏng — xếp từng dãy S một cho tới khi hết miếng
void sub1() {
int have[10] = {0};
for (char c : T) have[cls(c - '0')]++;
long long ans = 0;
while (true) {
for (char c : S) {
int d = cls(c - '0');
if (have[d] == 0) { cout << ans << "\n"; return; }
have[d]--;
}
ans++;
}
}
// Sub 2: đếm số lượng mỗi loại, đáp án là min của (có / cần)
void sub2() {
long long have[10] = {0}, need[10] = {0};
for (char c : T) have[cls(c - '0')]++;
for (char c : S) need[cls(c - '0')]++;
long long ans = LLONG_MAX;
for (int d = 0; d < 10; d++)
if (need[d] > 0) ans = min(ans, have[d] / need[d]);
cout << ans << "\n";
}
int main() {
freopen("STICKERS.INP", "r", stdin);
freopen("STICKERS.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> T >> S;
// Mô phỏng chạy tối đa |T| lần lặp ~ |S| bước, tổng ~ |T| bước nên với dữ liệu nhỏ dùng sub1
if ((long long)T.size() * S.size() <= 1000000) sub1();
else sub2();
}
Bình luận