Bài 5

Có

n

người ngồi thành vòng tròn. Tổng cộng có

nk

đồng xu được phân phối, không nhất thiết đều. Một bước chuyển một đồng xu giữa hai người kề nhau. Hãy tìm thuật toán dùng ít bước nhất để cuối cùng mọi người có cùng số đồng xu.

Bước 1 trên 5: Mã hóa độ lệch

Bước trước Bước tiếp

d_i=c_i-k,\qquad\sum_{i=1}^nd_i=0

Phân tích chi tiết

Đánh số tuần hoàn, gọi $c_i$ là số xu ban đầu và đặt $d_i=c_i-k$ . Vì tổng là $nk$ nên $\sum_{i=1}^nd_i=0$ . Đổi nhãn để $d_1\ge0$ .