trang chủ / đề bài / booking

Hệ thống đặt bàn

Đề bài

Mô tả

Một nhà hàng nhận được n yêu cầu đặt bàn. Yêu cầu thứ i gồm hai số ci và pi: nhóm khách của yêu cầu này có ci người và nếu được phục vụ thì họ sẽ trả tổng cộng pi đồng.

Cả nhóm khách của một yêu cầu phải ngồi chung một bàn, và mỗi bàn chỉ được dành cho đúng một nhóm. Nhà hàng có k bàn, bàn thứ j chứa được tối đa rj người. Như vậy nhóm của yêu cầu i có thể ngồi ở bàn j khi và chỉ khi ci≤rj. Nếu một yêu cầu không được xếp bàn thì nhóm đó bỏ đi và không trả đồng nào.

Hãy chọn tập các yêu cầu được chấp nhận cùng cách xếp bàn cho chúng sao cho tổng số tiền thu được là lớn nhất.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n là số yêu cầu.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên ci và pi.
  • Dòng tiếp theo chứa số nguyên k là số bàn.
  • Dòng cuối chứa k số nguyên r1,r2,…,rk.

Dữ liệu ra

  • Dòng đầu in ra hai số nguyên m và s: số yêu cầu được chấp nhận và tổng số tiền thu được.
  • m dòng tiếp theo, mỗi dòng chứa hai số nguyên: chỉ số của yêu cầu được chấp nhận và chỉ số của bàn xếp cho nhóm khách đó. Các yêu cầu và các bàn được đánh số từ 1 theo thứ tự xuất hiện trong dữ liệu vào.

Mỗi yêu cầu và mỗi bàn chỉ được xuất hiện nhiều nhất một lần. Nếu có nhiều đáp án tối ưu, in ra đáp án bất kỳ.

Ràng buộc

  • 1≤n≤1000
  • 1≤ci,pi≤1000
  • 1≤k≤1000
  • 1≤rj≤1000

Ví dụ

Input Output Giải thích
3
10 50
2 100
5 30
3
4 6 9		 2 130
2 1
3 2		 Nhóm 2 có 2 người, xếp vào bàn 1 (chứa 4 người). Nhóm 3 có 5 người, xếp vào bàn 2 (chứa 6 người). Nhóm 1 có 10 người, không bàn nào chứa nổi nên bị từ chối. Tổng tiền 100+30=130.
3
10 10
3 5
5 8
3
3 4 10		 2 15
1 3
2 1		 Chỉ bàn 3 (chứa 10 người) đủ lớn cho nhóm 1 hoặc nhóm 3, nên chỉ một trong hai nhóm được phục vụ. Chọn nhóm 1 trả 10 đồng, cộng nhóm 2 ngồi bàn 1 trả 5 đồng, tổng 15 là tối ưu.
2
10 10
5 5
1
4		 0 0 Bàn duy nhất chỉ chứa 4 người, không nhóm nào vừa, nên không chấp nhận yêu cầu nào.

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