Chia Đội Cân Bằng

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $12$ vận động viên với các chỉ số kỹ năng khác nhau cần được chia thành $4$ đội, mỗi đội đúng $3$ người. Sức mạnh của mỗi đội là tổng chỉ số kỹ năng của các thành viên.

Hãy chia các vận động viên sao cho hiệu giữa sức mạnh đội mạnh nhất và đội yếu nhất là nhỏ nhất có thể.

Dữ liệu vào

$12$ dòng, mỗi dòng chứa một số nguyên là chỉ số kỹ năng của một vận động viên

Dữ liệu ra

Dòng 1: Hiệu nhỏ nhất giữa sức mạnh đội lớn nhất và nhỏ nhất

Ràng buộc

Chỉ số kỹ năng: số nguyên trong khoảng $[1, 10^{6}]$

Ví dụ

Input	Output	Giải thích
1 2 3 4 5 6 7 8 9 10 11 12	1	Chia thành: (12,1,7)=20, (9,8,3)=20, (10,5,4)=19, (11,2,6)=19. Hiệu = 1.
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1	999999	11 người có kỹ năng $10^{6}$ và 1 người có kỹ năng $1$ . Đội yếu nhất buộc phải có người kỹ năng $1$ , tổng = $2 \times 10^{6} + 1$ . Đội mạnh nhất = $3 \times 10^{6}$ . Hiệu = $10^{6} - 1 = 999999$ .

Ghi chú

Số cách chia hợp lệ là $\frac{12!}{(3!)^{4} \cdot 4!} = 15400$ , đủ nhỏ để duyệt toàn bộ.

Bình luận

Không có bình luận tại thời điểm này.