trang chủ / đề bài / icpcwf14_b

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 i có độ ngon ban đầu ti và tốc độ giảm độ ngon Δti. Với món rời, độ ngon bạn cảm nhận khi ăn miếng thứ n của món đó là ti−(n−1)Δti. 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ỏ dx gam của món sau khi đã ăn x gam là (ti−xΔti)dx. Nói cách khác, tổng độ ngon bạn cảm nhận khi ăn N miếng của một món rời, hoặc X gam của một món liên tục, lần lượt là

∑n=1N(ti−(n−1)Δti)và∫0X(ti−xΔti)dx.

Để đơ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ố ti và Δti 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 w. 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 d và w, 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 dòng, dòng thứ i mô tả món thứ i theo một trong hai dạng sau:

  • Dòng có dạng D wi ti Δti cho biết đây là một món rời, mỗi miếng nặng wi gam, độ ngon ban đầu ti và tốc độ giảm độ ngon Δti.
  • Dòng có dạng C ti Δti cho biết đây là một món liên tục với độ ngon ban đầu ti và tốc độ giảm độ ngon Δti.

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 w 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á 10−6. Nếu không thể tạo một bữa ăn có tổng khối lượng đúng bằng w từ các món hiện có, in ra impossible.

Ràng buộc

  • 1≤d≤250, 1≤w≤10000.
  • Các số wi, ti, Δti là số nguyên thỏa mãn 1≤wi≤10000 và 0≤ti,Δti≤10000.

Ví dụ

Input Output Giải thích
2 15
D 4 10 1
C 6 1
40.500000000 Ăn 3 miếng món rời (12 gam, độ ngon 10+9+8=27) và 3 gam món liên tục (độ ngon ∫03(6−x)dx=13.5), tổng 40.5.
3 15
D 4 10 1
C 6 1
C 9 3
49.000000000 Ăn 2 miếng món rời (8 gam, độ ngon 19), 4.5 gam món liên tục thứ nhất (độ ngon 16.875) và 2.5 gam món liên tục thứ hai (độ ngon 13.125), tổng 49.
2 19
D 4 5 1
D 6 3 2
impossible Mọi miếng đều nặng 4 hoặc 6 gam nên tổng khối lượng luôn chẵn, không thể bằng 19.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0