Tiệc buffet
Đề bài
Mô tả
Bạn đang ăn trưa ở một nhà hàng buffet. Có nhiều món ăn khác nhau và bạn có thể kết hợp chúng tùy thích. Một số món, chẳng hạn bánh bao hay khoai tây nướng, gồm các miếng có kích thước gần như bằng nhau, và bạn có thể lấy một số nguyên miếng của món đó (không được cắt nhỏ). Gọi đây là các "món rời". Những món khác, chẳng hạn sốt tzatziki hay khoai tây nghiền, ở dạng sệt và bạn có thể lấy một lượng thực tùy ý. Gọi loại thứ hai này là các "món liên tục".
Tất nhiên bạn thích một số món hơn các món khác, nhưng bạn thích một món đến mức nào còn phụ thuộc vào việc bạn đã ăn món đó bao nhiêu rồi. Chẳng hạn, dù nói chung bạn thích bánh bao hơn khoai tây, bạn vẫn có thể thích một miếng khoai tây hơn một cái bánh bao nếu đã ăn mười cái bánh bao. Để mô hình hóa điều này, mỗi món có độ ngon ban đầu và tốc độ giảm độ ngon . Với món rời, độ ngon bạn cảm nhận khi ăn miếng thứ của món đó là . Với món liên tục, độ ngon bạn cảm nhận khi ăn thêm một lượng vô cùng nhỏ gam của món sau khi đã ăn gam là . Nói cách khác, tổng độ ngon bạn cảm nhận khi ăn miếng của một món rời, hoặc gam của một món liên tục, lần lượt là
Để đơn giản, ta không xét việc các món có hợp nhau hay không, nên tổng độ ngon của một bữa ăn được định nghĩa là tổng độ ngon của từng món trong bữa (khối lượng của bữa ăn cũng là tổng khối lượng các món, không có "phản hạt thức ăn" nào trong nhà hàng cả!).
Bạn đã dành nhiều ngày nghiên cứu vất vả để xác định các số và của mọi món trong buffet. Việc còn lại chỉ là tính tổng độ ngon lớn nhất có thể đạt được của một bữa ăn có khối lượng đúng bằng . Nhanh lên, bữa trưa sắp được dọn ra rồi!
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , lần lượt là số món khác nhau trong buffet và tổng khối lượng mong muốn của bữa ăn (tính bằng gam).
Tiếp theo là dòng, dòng thứ mô tả món thứ theo một trong hai dạng sau:
- Dòng có dạng
Dcho biết đây là một món rời, mỗi miếng nặng gam, độ ngon ban đầu và tốc độ giảm độ ngon . - Dòng có dạng
Ccho biết đây là một món liên tục với độ ngon ban đầu và tốc độ giảm độ ngon .
Dữ liệu ra
In ra tổng độ ngon lớn nhất có thể của một bữa ăn có khối lượng từ các món hiện có. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá . Nếu không thể tạo một bữa ăn có tổng khối lượng đúng bằng từ các món hiện có, in ra impossible.
Ràng buộc
- , .
- Các số , , là số nguyên thỏa mãn và .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 15 D 4 10 1 C 6 1 |
40.500000000 | Ăn miếng món rời ( gam, độ ngon ) và gam món liên tục (độ ngon ), tổng . |
| 3 15 D 4 10 1 C 6 1 C 9 3 |
49.000000000 | Ăn miếng món rời ( gam, độ ngon ), gam món liên tục thứ nhất (độ ngon ) và gam món liên tục thứ hai (độ ngon ), tổng . |
| 2 19 D 4 5 1 D 6 3 2 |
impossible | Mọi miếng đều nặng hoặc gam nên tổng khối lượng luôn chẵn, không thể bằng . |
Bình luận