USACO 2019 - I Would Walk 500 Miles
Xem PDFFarmer John muốn chia \(N\) con bò của mình (\(N \leq 7500\)), được đánh số thuận tiện từ \(1 \ldots N\), thành \(K\) nhóm không rỗng (\(2 \leq K \leq N\)), sao cho bất kỳ hai con bò thuộc hai nhóm khác nhau muốn gặp nhau đều phải đi bộ một số dặm. Bò \(x\) và bò \(y\) (với \(1 \leq x < y \leq N\)) sẵn lòng đi bộ \((2019201913x + 2019201949y)\text{ mod } 2019201997\) dặm để gặp nhau.
Với một cách chia \(N\) con bò thành \(K\) nhóm không rỗng, gọi \(M\) là giá trị nhỏ nhất trong số quãng đường mà bất kỳ hai con bò thuộc hai nhóm khác nhau sẵn lòng đi để gặp nhau. Để kiểm tra sự tận tâm của những con bò dành cho nhau, Farmer John muốn chia tối ưu \(N\) con bò thành \(K\) nhóm sao cho \(M\) lớn nhất có thể.
Giới hạn bộ nhớ cho bài này được đặt là 512 MB, cao hơn giới hạn thông thường 256 MB.
Dữ liệu vào
Dữ liệu vào chỉ gồm một dòng chứa \(N\) và \(K\), cách nhau bởi một dấu cách.
Dữ liệu ra
In ra \(M\) trong một phương án tối ưu.
Ví dụ
Ví dụ 1
Input
3 2Output
2019201769Giải thích
Trong ví dụ này, bò 1 và bò 2 sẵn lòng đi bộ 2019201817 dặm để gặp nhau. Bò 2 và bò 3 sẵn lòng đi bộ 2019201685 dặm. Còn bò 1 và bò 3 sẵn lòng đi bộ 2019201769 dặm. Vì vậy, bằng cách chia sao cho bò 1 ở một nhóm riêng, còn bò 2 và bò 3 ở cùng một nhóm, ta có \(M = \min(2019201817,2019201769) = 2019201769\) (đây là giá trị tốt nhất có thể đạt được trong trường hợp này).
Nguồn
USACO 2019 US Open Contest, Gold — I Would Walk 500 Miles
Tác giả: Brian Dean.
Kỳ thi:
- USACO 2019 - US Open - Hạng Vàng (1 Tháng tư, 2019)
Bình luận