Tô màu · CODER HUSC

Skip to content

CODER HUSC

This site works best with JavaScript enabled.

Time limit: 1.0 s
Memory limit: 256 MB
Points: 100partial
AC rate: 22.2%
Solvers: 142

Cho một bảng kích thước $n \times m$ ~n \times m~ và một số nguyên dương $k$ ~k~. Thực hiện tô màu các ô của bảng với quy tắc sau:

Nếu hai ô $(x_1,y_1)$ ~(x_1,y_1)~ và $(x_2,y_2)$ ~(x_2,y_2)~ là hai ô khác nhau được tô cùng màu thì $\max(|x_1-x_2|,|y_1-y_2|) \ge k$ ~\max(|x_1-x_2|,|y_1-y_2|) \ge k~.

Hãy đếm số lượng màu ít nhất dùng để tô toàn bộ các ô của bảng.

Input

Dòng duy nhất chứa ba số nguyên $n$ ~n~, $m$ ~m~, $k$ ~k~ $(1 \le n,m,k \le 10^6)$ ~(1 \le n,m,k \le 10^6)~.

Output

In ra số lượng màu ít nhất dùng để tô toàn bộ các ô của bảng.

Examples

Sample Input 1

3 3 2

Sample Output 1

Sample Input 2

7 1 1000000

Sample Output 2

Scoring

Subtask $1$ ~1~ $-$ ~-~ $50$ ~50~ điểm: $n,m,k \le 10^3$ ~n,m,k \le 10^3~
Subtask $2$ ~2~ $-$ ~-~ $50$ ~50~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ thứ nhất, chỉ sử dụng $4$ ~4~ màu, có thể tô màu cho các ô của bảng như sau:

drawing

Trong ví dụ thứ hai, toàn bộ các ô đều phải được tô màu khác nhau.

Comments

T-NAI-25-1194 23/02/2025 20:30

có ai cho mình xin cách giải bài toán này được không ạ,mình giải được subtask1 còn subtask2 bị rte

Vote score: 0
T-JUN-25-1393 23/02/2025 11:02

https://codeforces.com/problemset/problem/2002/A

Vote score: 1

You need to sign in to write comments, reply and vote.

Sign in to comment