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 :(