A. Mua Vé Số (Buy Lottery Tickets)
Bài toán yêu cầu liệt kê tất cả các tổ hợp 6 số từ một danh sách các số nguyên đầu vào, với điều kiện là các số được chọn phải thỏa mãn tính chất tăng dần. Vì giới hạn của dữ liệu không quá lớn, chúng ta có thể sử dụng thuật toán tìm kiếm theo chiều sâu (DFS) kết hợp với kỹ thuật quay lui (backtracking) để giải quyết.
Logic chính là duyệt qua từng phần tử, đánh dấu nó đã được sử dụng, và đệ quy để chọn số tiếp theo. Nếu tại một bước nào đó việc chọn số làm cho thứ tự không tăng dương hoặc vượt quá số lượng cần chọn, ta sẽ quay lại trạng thái trước đó. Một điểm chú ý là điều kiện dừng của đệ quy phải có câu lệnh trả về (return) để kết thúc nhánh hiện tại, tránh in thừa dữ liệu.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX_N = 20;
int pool[MAX_N];
int selection[7];
bool visited[MAX_N];
int total_numbers;
void backtrack(int current_idx, int start_pos) {
if (current_idx == 6) {
for (int i = 0; i < 6; ++i) {
cout << selection[i] << (i < 5 ? " " : "\n");
}
return;
}
for (int i = start_pos; i < total_numbers; ++i) {
if (!visited[i]) {
// Đảm bảo tính chất tăng dần
if (current_idx > 0 && pool[i] < selection[current_idx - 1]) continue;
visited[i] = true;
selection[current_idx] = pool[i];
backtrack(current_idx + 1, i + 1);
visited[i] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> total_numbers) {
if (total_numbers == 0) break;
memset(visited, false, sizeof(visited));
memset(selection, 0, sizeof(selection));
if (total_numbers < 6 || total_numbers > 13) {
cout << "ERROR\n\n";
continue;
}
for (int i = 0; i < total_numbers; ++i) {
cin >> pool[i];
}
// Sắp xếp để dễ dàng duy trì tính chất tăng dần
sort(pool, pool + total_numbers);
backtrack(0, 0);
cout << endl;
}
return 0;
}
B. Nhiệm Vụ Của Giáo Sư (Professor's Task)
Đây là một bài toán xử lý chuỗi cơ bản. Nhiệm vụ là đọc từng dòng dữ liệu từ đầu vào chuẩn và thống kê tần suất xuất hiện của các ký tự chữ cái thường (từ 'a' đến 'z'). Sau đó, kết quả được in ra theo thứ tự bảng chữ cái kèm theo số lần xuất hiện tương ứng.
Chúng ta sử dụng một mảng đếm có kích thước 26 để lưu trữ số lượng. Mỗi khi đọc một ký tự, ta kiểm tra xem nó có phải là chữ cái thường hay không. Nếu có, ta tăng giá trị tại vị trí tương ứng trong mảng.
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main() {
string line;
while (getline(cin, line)) {
int freq[26] = {0};
for (char c : line) {
if (c >= 'a' && c <= 'z') {
freq[c - 'a']++;
}
}
for (int i = 0; i < 26; ++i) {
cout << (char)('a' + i) << ':' << freq[i] << '\n';
}
cout << endl;
}
return 0;
}
C. Đồng Xu Vàng (Golden Coins)
Bài toán này yêu cầu tìm số cách để biểu diễn một số nguyên $N$ ($N < 300$) thành tổng các bình phương của các số nguyên từ 1 đến 17. Các bình phương này có thể được sử dụng nhiều lần.
Về mặt toán học, đây là bài toán quy hoạch động dạng "Cái túi không giới hạn" (Unbounded Knapsack) biến thiên, nơi chúng ta đếm số cách cấu thành tổng giá trị thay vì tối đa hóa giá trị. Gọi $dp[i]$ là số cách để tạo ra tổng $i$. Công thức truy hồi là: $dp[i] = \sum dp[i - val]$ với mọi $val$ là các số bình phương nhỏ hơn hoặc bằng $i$.
Để tối ưu bộ nhớ, chúng ta sử dụng mảng một chiều. Cần chú ý thứ tự duyệt: duyệt qua các loại "tiền" (số bình phương) ở vòng lặp ngoài, và duyệt tổng tiền tệ ở vòng lặp trong.
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_TARGET = 300;
long long dp[MAX_TARGET + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int target;
while (cin >> target && target != 0) {
memset(dp, 0, sizeof(dp));
dp[0] = 1; // Có 1 cách để tạo ra tổng 0 (không chọn gì cả)
for (int i = 1; i <= 17; ++i) {
int coin_value = i * i;
for (int j = coin_value; j <= target; ++j) {
dp[j] += dp[j - coin_value];
}
}
cout << dp[target] << endl;
}
return 0;
}
D. Happy 2004
Yêu cầu của bài toán là tính tổng tất cả các ước số của $A^B$ với $A=2004$, và lấy kết quả modulo 29. Đây là một bài toán về lý thuyết số sử dụng công thức tổng các ước số và phân tích thừa số nguyên tố.
Cho $A = \prod p_i^{k_i}$, khi đó $A^B = \prod p_i^{k_i \cdot B}$. Tổng các ước số $\sigma(n)$ được tính bằng công thức: $\sigma(n) = \prod (p_i^0 + p_i^1 + ... + p_i^{k_i \cdot B})$.
Vấn đề trở thành tính tổng của một cấp số nhân $S(p, k) = 1 + p + p^2 + ... + p^{k-1}$ modulo một số nguyên tố. Ta có thể sử dụng phương pháp chia để trị để tính tổng này một cách hiệu quả mà không cần tính lũy thừa lớn trực tiếp:
- Nếu $k$ chẵn: $S(p, k) = (1 + p^{k/2}) \cdot S(p, k/2)$.
- Nếu $k$ lẻ: $S(p, k) = S(p, k-1) + p^{k-1}$.
#include <iostream>
using namespace std;
const int MOD = 29;
// Hàm tính lũy thừa a^b % mod
int power_mod(int base, int exponent) {
int result = 1;
base %= MOD;
while (exponent > 0) {
if (exponent & 1) result = (result * base) % MOD;
base = (base * base) % MOD;
exponent >>= 1;
}
return result;
}
// Hàm tính tổng cấp số nhân 1 + p + ... + p^(k-1) % mod
int geometric_series_sum(int p, int k) {
if (k == 1) return 1;
if (k % 2 == 0) {
// S(2k) = (1 + p^k) * S(k)
int half_pow = power_mod(p, k / 2);
return ((1 + half_pow) * geometric_series_sum(p, k / 2)) % MOD;
} else {
// S(2k+1) = S(2k) + p^(2k)
return (geometric_series_sum(p, k - 1) + power_mod(p, k - 1)) % MOD;
}
}
int main() {
int b;
while (cin >> b && b != 0) {
int a = 2004;
int final_result = 1;
// Phân tích thừa số nguyên tố của 2004
for (int i = 2; i * i <= a; ++i) {
if (a % i == 0) {
int exp = 0;
while (a % i == 0) {
a /= i;
exp++;
}
// Tính tổng cho thừa số này: p_i^0 + ... + p_i^(exp*b)
// Số hạng trong công thức là exp*b + 1
final_result = (final_result * geometric_series_sum(i, exp * b + 1)) % MOD;
}
}
// Xử lý trường hợp a còn lại là một số nguyên tố lớn hơn 1
if (a > 1) {
final_result = (final_result * geometric_series_sum(a, b + 1)) % MOD;
}
cout << final_result << endl;
}
return 0;
}