Hướng dẫn giải của [Beginner Free Contest 08] VMACHINE
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
Cần chọn một tập mệnh giá đồng xu sao cho mọi số từ 1 đến C đều trả được bằng một tổng con. Bài toán cần ít đồng xu nhất.
Sub 1: Vét cạn, ~C \le 20~ ~O(\text{tap hop})~
Thử k = 1, 2, ... đồng xu, duyệt các tập mệnh giá để kiểm tra phủ được 1..C. Chạy riêng subtask này đạt 15/50 test (các test có C lớn nằm ngoài miền).
Sub 2: Tham lam lũy thừa 2, ~O(\log C)~ ~O(\log C)~
Chọn các lũy thừa của 2 nhỏ hơn hoặc bằng C. Chúng phủ được 0..2^(k+1)-1 >= C với k+1 đồng xu, là ít nhất có thể. Chạy riêng subtask này đạt 50/50 test.
Chương trình hoàn chỉnh
Nếu C <= 20 dùng sub 1, ngược lại dùng sub 2. Ví dụ đề in 1 1 3 cho C = 5; bộ lũy thừa 2 cũng đúng số lượng nên được chấp nhận. Lưu ý: đề cho in bộ mệnh giá bất kỳ (ví dụ trong đề in 1 1 3), máy chấm kiểm tra bộ đồng xu có đúng số lượng ít nhất và trả được mọi số tiền từ 1 đến C hay không.
#include <bits/stdc++.h>
using namespace std;
long long C;
vector<long long> coins; // cac menh gia dang chon
void printCoins() {
cout << coins.size() << "\n";
for (size_t i = 0; i < coins.size(); i++) cout << coins[i] << (i + 1 < coins.size() ? ' ' : '\n');
}
// Kiem tra tap dong xu co tra duoc moi so 1..c khong
bool covered(int c) {
bitset<128> b;
b[0] = 1;
for (long long v : coins) b |= b << v; // b[s] = 1 neu tra dung duoc so s
for (int s = 1; s <= c; s++) if (!b[s]) return false;
return true;
}
bool dfs(int k, long long minv, int c) {
if ((int)coins.size() == k) return covered(c);
for (long long v = minv; v <= c; v++) {
coins.push_back(v);
if (dfs(k, v, c)) return true;
coins.pop_back();
}
return false;
}
// Sub 1: vet can, dung khi C <= 20: thu k = 1,2,... dong xu, moi lan duyet cac tap menh gia de tim so dong xu it nhat.
// Sau do in cach chon: cac luy thua cua 2 nho hon hoac bang C (so luong dung bang k vua tim).
void sub1() {
int c = (int)C;
int kmin = 0;
for (int k = 1;; k++) {
coins.clear();
if (dfs(k, 1, c)) { kmin = k; break; }
}
coins.clear();
for (long long v = 1; v <= C; v *= 2) coins.push_back(v);
if ((int)coins.size() != kmin) { /* khong xay ra: luy thua 2 cho so dong xu toi uu */ }
printCoins();
}
// Sub 2: tham lam, dung cho C lon: cac luy thua cua 2 nho hon hoac bang C.
// Chung phu duoc 0..2^(k+1)-1 >= C, va so dong xu = ceil(log2(C+1)) la it nhat co the.
void sub2() {
coins.clear();
for (long long v = 1; v <= C; v *= 2) coins.push_back(v);
printCoins();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> C;
if (C <= 20) sub1();
else sub2();
}
return 0;
}
Bình luận