Bài toán: I Count Two Three

Cho trước số nguyên n, nhiệm vụ là tìm số nguyên nhỏ nhất k sao cho k >= n và k có dạng 2^a * 3^b * 5^c * 7^d. Với n <= 10^9, ta có thể sinh sẵn tất cả các giá trị thỏa mãn điều kiện, lưu vào tập hợp std::set và sử dụng hàm lower_bound để tìm kiếm nhanh.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

typedef long long ll;
std::set<ll> candidate_set;

void precompute() {
    for (ll a = 1; a <= 1e9; a *= 2)
        for (ll b = a; b <= 1e9; b *= 3)
            for (ll c = b; c <= 1e9; c *= 5)
                for (ll d = c; d <= 1e9; d *= 7)
                    candidate_set.insert(d);
}

void process() {
    ll n;
    std::cin >> n;
    std::cout << *candidate_set.lower_bound(n) << "\n";
}

Bài toán: Cure

Tính tổng S = sum(1/k^2) từ k=1 đến n, làm tròn đến 5 chữ số thập phân. Khi n đạt đến một ngưỡng nhất định (khoảng 1 triệu), giá trị tổng sẽ hội tụ về gần một hằng số. Ta có thể tiền xử lý mảng tích lũy để trả lời truy vấn trong O(1).

#include <iostream>
#include <vector>
#include <iomanip>

double prefix_sums[1000001];

void build() {
    double current = 0;
    for (int i = 1; i <= 1000000; ++i) {
        current += 1.0 / (1.0 * i * i);
        prefix_sums[i] = current;
    }
}

void solve() {
    int n;
    while (std::cin >> n) {
        if (n > 1000000) n = 1000000;
        std::cout << std::fixed << std::setprecision(5) << prefix_sums[n] << "\n";
    }
}

Bài toán: Tea

Bài toán yêu cầu tính số lần đổ nước tối thiểu để chia đều lượng nước [L, R] vào hai cốc với sai số không quá 1. Quy luật được xác định dựa trên khoảng cách của L và R. Nếu R nhỏ hơn 2, không cần thực hiện hành động. Với các trường hợp khác, công thức cơ bản dựa trên phép chia lấy dư và các bước đổ xen kẽ.

Bài toán: Balanced Game

Trò chơi có n hình thái. Trò chơi cân bằng nếu mỗi hình thái có khả năng thắng bằng với khả năng thua (50%). Điều này xảy ra khi mỗi lựa chọn có thể thắng đúng (n-1)/2 lựa chọn khác và bị (n-1)/2 lựa chọn khác đánh bại. Suy ra n phải là số lẻ.

Bài toán: The Best Path

Xác định tính tồn tại của đường đi Euler trên đồ thị và tìm giá trị XOR cực đại của các đỉnh trên đường đi đó. Nếu đồ thị có nhiều hơn 2 đỉnh bậc lẻ, đường đi Euler không tồn tại. Nếu là chu trình Euler (0 đỉnh bậc lẻ), ta có thể chọn đỉnh bắt đầu bất kỳ để tối ưu giá trị XOR.

Bài toán: Sort

Tìm giá trị k nhỏ nhất để hợp nhất n dãy số với tổng chi phí không vượt quá T. Đây là dạng bài toán cây Huffman bậc k. Ta sử dụng tìm kiếm nhị phân trên k kết hợp với hai hàng đợi để duy trì thứ tự các phần tử, giúp tối ưu hóa thời gian thực thi xuống O(n log n) thay vì dùng hàng đợi ưu tiên truyền thống.