A. K-Divisible Sum (Educational Codeforces Round 103).

Contest giải được đúng 1 bài nhưng rating vẫn +5.

A - K-Divisible Sum

Lược dịch: Cho hai số nguyên $n$ và $k$. Bạn phải tạo một mảng nguyên $\{a_i \mid 1 \leq i \leq n, a_i \in \mathbb{Z}+\}$ sao cho $\displaystyle \sum_{i = 1}^n a_i \equiv 0 \pmod k$ và $\max\{a_i \mid 1 \leq i \leq n\}$ đạt nhỏ nhất có thể. Khi đó, tìm $\max\{a_i \mid 1 \leq i \leq n\}$?

Hướng giải: Algoritham.

• Nếu $n \equiv 0 \pmod k$, khi đó ta có thể dựng $\{a_i \mid 1 \leq i \leq n \} = \{1, 1, .., 1\}$. Khi đó $\max\{a_i \mid 1 \leq i \leq n\} = 1$.
• Nếu $k \equiv 0 \pmod n$ khi đó ta có thể dựng $\displaystyle \{a_i \mid 1 \leq i \leq n \} = \left\{\frac{k}{n}, \frac{k}{n}, .., \frac{k}{n}\right\}$. Khi đó $\displaystyle \max\{a_i \mid 1 \leq i \leq n\} = \frac{k}{n}$.
• Nếu $k > n$, khi đó ta sẽ tham lam bằng cách cho $a_1$ (hay bất kì phần tử nào) đạt $\max$, các phần tử còn lại bằng $1$. Kết quả sẽ là $\displaystyle \left\lceil\frac{k}{n}\right\rceil$.
• Nếu n > k, ta tính kết quả n - (n mod k). Nếu n chia hết cho n - (n mod k), đáp án là n / (n - (n mod k)) và ngược lại là n / (n - (n mod k)) + 1.

Code mẫu (C++).

Happy coding!