mofk_
user-avatar

Nguyễn Đinh Quang Minh

Đóng góp: 44

Ngày sinh: 15/01/1999

Đăng ký: 06/07/2015

Lần đăng nhập cuối: 21/10/2016

Kết nối tài khoản

VOJ: tru3goon3r (42.65 điểm)

Topcoder: Chưa kết nối

Discuss đề thi IOI 2015

Như tít ạ, em thấy các bác chém gió bảng rank ghê quá nên cũng xin mạn phép mở topic chém gió lời giải ở đây :3

Em xin mở hàng luôn bằng sol bài 1 (hi vọng là đúng) của em:

*Nhận xét: Ta không nên đi đủ một vòng tròn quá 1 lần.

- Chứng minh: giả sử ta đi nhiều hơn 1 vòng tròn. Xét 2 lần đi bất kì. Trong 2 lần đó, ta sẽ chuyển không nhiều hơn 2 * K món đồ. Ta có thể tối ưu cách đi này bằng cách: đi theo chiều bất kì, đến khi gặp và phát đủ K món thì quay về, sau đó đi theo chiều ngược lại, phát quà cho những thằng còn lại (<= K thằng). Tổng độ dài quãng đường sẽ không lớn hơn 2 * L, tốt hơn cách đi trước.

Như vậy ta chỉ cần xét 2 trường hợp: không đi hết vòng tròn nào và đi hết 1 vòng tròn. Trước hết chia những thằng trên vòng tròn thành 2 tập trái và phải, tùy theo đi từ 0 theo hướng nào đến nó gần hơn.

*TH1: Ta sẽ đến phát quà cho 2 thằng xa 0 nhất của mỗi tập. Trên đường đi ta sẽ phát hết quà cho nó và  K - 1 thằng trước nó. Do đó tiếp theo ta sẽ phát quà cho các thằng xa 0 thứ K, 2 * K, ... của mỗi tập cho đến khi hết hàng. Vì mảng được sort rồi nên trường hợp này chạy hết O (N / K).

*TH2: Để ý rằng ta có thể đi hết vòng tròn ngay từ đầu, và ta nên chọn một đoạn liên tiếp K thằng để phát quà (và hiển nhiên, mỗi tập nên có ít nhất 1 thằng được phát). Sau đó ta làm giống TH1. ĐPT là O(K*N/K) = O(N). Mong các bác vào góp cho xôm ạ :3

UPD: Đã sửa lại một số đoạn phát biểu liều :(