{"code":"lqdojcontest15bai3","name":"LQDOJ Contest #15 - Bài 3 - Gian hàng bánh chưng","description":"Ở một ngôi làng **LQDOJ** nổi tiếng với truyền thống gói bánh chưng ngày Tết, [user:shiba] – một người bán bánh chưng có tiếng đang chuẩn bị mở hai gian hàng tại chợ Tết. Anh sẽ thu mua $N$ gói bánh chưng từ $N$ gia đình trong làng để đi bán.\r\n\r\nGia đình thứ $i$ $(1 \\le i \\le N)$ sẽ bán đúng $a_i$ chiếc bánh chưng trong gói của mình với giá tổng cộng là $c_i$. [user:shiba] sẽ mua toàn bộ các gói bánh chưng này của các gia đình và phân chia chúng vào hai gian hàng.\r\n\r\n[user:shiba] ký hiệu giá bánh chưng trung bình ở gian hàng thứ nhất là $X_1$ và giá bánh chưng trung bình ở gian hàng thứ hai là $X_2$. Giá bánh chưng trung bình ở một gian hàng được tính bằng tỷ lệ giữa tổng giá và tổng số lượng bánh chưng ở gian hàng đó (hay nói cách khác, $X = \\frac{Tổng \\ \\ giá}{Tổng \\ \\ số \\ \\ lượng \\ \\ bánh \\ \\ chưng}$). \r\n\r\nĐể thuận lợi trong việc buôn bán ngày Tết và giữ giá cả hợp lý cho người dân, [user:shiba] muốn tích của $X_1$ và $X_2$ là nhỏ nhất có thể. Hay nói cách khác, anh muốn tích của giá bánh chưng trung bình ở hai gian hàng là nhỏ nhất, và [user:shiba] muốn chia làm sao mà ít nhất một gian hàng phải có đúng $M$ gói bánh chưng, không hơn không kém.\r\n\r\n**Yêu cầu:** Bạn hãy giúp [user:shiba] phân chia $N$ gói bánh chưng vào hai gian hàng sao cho tích của $X_1$ và $X_2$ là nhỏ nhất có thể và có ít nhất một gian hàng phải có đúng $M$ gói bánh chưng.\r\n\r\n#### Input\r\n\r\n - Dòng đầu tiên chứa hai số nguyên dương lần lượt là $N$ và $M$ $(2 \\le N \\le 100,1 \\le M < N)$ là số gói bánh chưng và số gói bánh chưng tối thiểu phải có ở ít nhất một gian hàng.\r\n - Dòng tiếp theo chứa $N$ số nguyên dương $a_i$ $(1 \\le a_i \\le 100)$ là số bánh chưng có trong gói thứ $i$, mỗi số cách nhau một khoảng trắng.\r\n - Dòng cuối cùng chứa $N$ số nguyên dương $c_i$ $(1 \\le c_i \\le 10^6)$ là giá của gói bánh chưng thứ $i$, mỗi số cách nhau một khoảng trắng.\r\n - Dữ liệu vào luôn đảm bảo rằng $a_1+a_2+...+a_N \\le 500$.\r\n\r\n#### Output \r\n\r\n - In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài sau khi làm tròn đến chữ số thập phân thứ ba.\r\n\r\n#### Scoring\r\n - Subtask $1$ ($30\\%$ số điểm): Có $N \\le 20$. \r\n - Subtask $2$ ($70\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 1\r\n        1 2 3\r\n        2 3 5\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2.625\r\n        ```\r\n    ??? warning \"Note\"\r\n        Đây là cách phân chia sao cho tích giá bánh chưng trung bình ở hai gian hàng là nhỏ nhất và thỏa mãn điều kiện có ít nhất một gian hàng có đúng $1$ gói bánh chưng:\r\n         - Gian hàng $1$: Gói $2$ $(a_2 = 2, c_2 = 3)$.\r\n         - Gian hàng $2$: Gói $1$ và gói $3$ $(a_1 = 1,c_1 = 2;a_3 = 3,c3 = 5)$.\r\n             - $X_1 = \\frac{3}{2} = 1.5$.\r\n             - $X_2 = \\frac{2+5}{1+3} = \\frac{7}{4} = 1.75$.\r\n             - Tích giá bánh chưng ở hai gian hàng là: $X_1 \\times X_2 = 1.5 \\times 1.75 = 2.625$ và gian hàng thứ $1$ có đúng $1$ gói bánh chưng.","points":1800.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}