Bánh nướng kèm kem
Đề bài
Mô tả
Hugh Samston là chủ dịch vụ cung cấp đồ ăn "You Want It, Hugh Got It", vừa được mời cung cấp món tráng miệng cho các thí sinh của kỳ ICPC World Finals năm nay. Hugh sẽ phục vụ các lát bánh nướng (pie) phủ kem tại các buổi giao lưu diễn ra trong suốt tuần. Như mọi doanh nhân tận tâm khác, Hugh muốn phục vụ tốt nhất có thể, nên đã đặt rất nhiều loại bánh và loại kem để chiều lòng cả những khẩu vị kỳ lạ nhất.
Hugh định phục vụ mỗi lát bánh với đúng một viên kem, và để khách tự chọn cách kết hợp. Nhưng tất nhiên, như mọi doanh nhân tận tâm khác, Hugh cũng muốn kiếm được càng nhiều lợi nhuận càng tốt. Anh biết trước lợi nhuận thu được từ mỗi cách kết hợp một lát bánh với một viên kem, cũng như những cách kết hợp bánh và kem không bao giờ được phục vụ (ví dụ: kem Peppermint Banana Chunk trên bánh Key Lime).
Với các thông tin này, cùng với số lát bánh của mỗi loại bánh và số viên kem của mỗi loại kem, Hugh muốn tính được cả lợi nhuận nhỏ nhất và lợi nhuận lớn nhất mà anh có thể nhận. Vì hy vọng còn được làm dịch vụ ăn uống cho các kỳ World Finals sau, anh muốn có một chương trình tổng quát giải bài toán này và các bài toán tương tự sau này.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên và , lần lượt là số loại bánh và số loại kem. Dòng tiếp theo chứa số nguyên là số lát bánh có sẵn của từng loại bánh. Dòng sau đó chứa số nguyên là số viên kem có sẵn của từng loại kem. Tổng số lát bánh luôn bằng tổng số viên kem, và mọi lát bánh, mọi viên kem đều phải được dùng hết.
Tiếp theo là dòng, mỗi dòng chứa số thực là lợi nhuận của từng cách kết hợp bánh và kem: số thứ nhất là lợi nhuận khi một lát bánh loại được phủ một viên kem loại ; số tiếp theo là lợi nhuận khi một lát bánh loại được phủ một viên kem loại , và cứ thế. Giá trị lợi nhuận nghĩa là cách kết hợp loại bánh và loại kem đó không bao giờ được bán.
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ ), tiếp theo là lợi nhuận nhỏ nhất và lợi nhuận lớn nhất, theo đúng định dạng như ví dụ. Mọi số đều in với đúng hai chữ số sau dấu chấm thập phân.
Ràng buộc
- , .
- Số lát bánh của mỗi loại bánh và số viên kem của mỗi loại kem là số nguyên từ đến .
- Mỗi lợi nhuận khác lớn hơn , không vượt quá và có không quá hai chữ số sau dấu chấm thập phân.
- Mỗi bộ test đều có ít nhất một cách dùng hết mọi lát bánh và mọi viên kem.
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 40 50 27 30 33 1.11 1.27 0.70 -1 2 0.34 4 4 10 10 10 10 10 10 10 10 1.01 -1 -1 -1 -1 1.01 -1 -1 -1 -1 1.01 -1 -1 -1 -1 1.01 0 0 |
Problem 1: 91.70 to 105.87 Problem 2: 40.40 to 40.40 |
Bộ 1: bánh loại không được kết hợp với kem loại , nên cả viên kem loại phải đi với bánh loại . Bộ 2: mỗi loại bánh chỉ đi được với đúng một loại kem, nên chỉ có một cách phục vụ, lợi nhuận . |
| 1 1 7 7 2.5 2 3 2 2 1 1 2 10 -1 0.5 1 3 0.05 0 0 |
Problem 1: 17.50 to 17.50 Problem 2: 5.00 to 13.55 |
Ví dụ tự thêm. Bộ 1: lát bánh đi với viên kem, lợi nhuận . Bộ 2: bánh loại không đi được với kem loại . Nếu bánh loại lấy cả viên kem loại thì bánh loại lấy kem loại và , lợi nhuận ; nếu bánh loại lấy viên kem loại và một viên kem loại thì lợi nhuận là . |
Bình luận