trang chủ / đề bài / icpcwf06_b

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 P và I, lần lượt là số loại bánh và số loại kem. Dòng tiếp theo chứa P 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 I 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à P dòng, mỗi dòng chứa I 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 0 được phủ một viên kem loại 0; số tiếp theo là lợi nhuận khi một lát bánh loại 0 được phủ một viên kem loại 1, và cứ thế. Giá trị lợi nhuận −1 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ố 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ 1), 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

  • 1≤P≤50, 1≤I≤50.
  • 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ừ 1 đến 100.
  • Mỗi lợi nhuận khác −1 lớn hơn 0, không vượt quá 10 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á 10 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 1 không được kết hợp với kem loại 0, nên cả 27 viên kem loại 0 phải đi với bánh loại 0. 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 40·1.01=40.40.
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: 7 lát bánh đi với 7 viên kem, lợi nhuận 17.50. Bộ 2: bánh loại 0 không đi được với kem loại 1. Nếu bánh loại 0 lấy cả 2 viên kem loại 2 thì bánh loại 1 lấy kem loại 0 và 1, lợi nhuận 2·0.5+1+3=5; nếu bánh loại 0 lấy viên kem loại 0 và một viên kem loại 2 thì lợi nhuận là 10+0.5+3+0.05=13.55.

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