BANK - Chiến lược cho vay
Xem dạng PDF
Nhân dịp kỉ niệm 100 năm thành lập, ngân hàng EDU dự định dành không quá ~n~ đồng cho sinh viên vay vốn không lãi suất. Có ~m~ sinh viên đăng ký vay vốn, các sinh viên được đánh số từ ~1~ đến ~m~, sinh viên thứ ~i~ đăng ký vay ~t_i~ đồng ~(i = 1, 2, ..., m)~. Ngân hàng muốn đáp ứng được cho nhiều sinh viên nhất và đương nhiên nếu sinh viên thứ ~i~ được vay vốn thì phải bảo đảm nhận đúng ~t_i~ đồng. Trong các cách lựa chọn các sinh viên vay vốn thỏa mãn điều kiện, ngân hàng muốn chọn cách cho vay mà sinh viên vay ít nhất là lớn nhất.
Yêu cầu: Cho ~t_1, t_2, ..., t_m~ và ~Q~ giả định ~n_1, n_2, ..., n_Q~, trong đó, ~n_k~ là giả định thứ ~k (k = 1, 2, ..., Q)~, khi ngân hàng dự định dành không quá ~n_k~ đồng cho sinh viên vay vốn, với mỗi giả định này, hãy đưa ra cách cho vay thỏa mãn điều kiện đề bài.
Input
- Dòng đầu chứa hai số nguyên ~m, Q~.
- Dòng thứ hai chứa ~m~ số nguyên dương ~t_1, t_2, ..., t_m (t_i ≤ 10^9~).
- Dòng thứ ba chứa ~Q~ số nguyên dương ~n_1, n_2, ..., n_Q (n_i ≤ 10^{18}~).
Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.
Giới hạn:
- Có 25% số test ứng với 25% số điểm của bài có ~m, Q ≤ 10~;
- Có 25% số test khác ứng với 25% số điểm của bài có ~m, Q ≤ 300~;
- Có 25% số test khác ứng với 25% số điểm của bài có ~m, Q ≤ 6000~;
- Có 25% số test khác ứng với 25% số điểm của bài có ~m, Q ≤ 90000~;
Output
- Gồm ~Q~ dòng, mỗi dòng chứa hai số nguyên ~s, v~, trong đó ~s~ là số lượng sinh viên được vay vốn, ~v~ là số tiền mà sinh viên được vay ít nhất tương ứng với giả định trong dữ liệu vào.
Sample
Input #1
5 2
1 3 2 3 5
6 8
Output #1
3 1
3 2
Problem source: Kc97ble - Free Contest 40
Bình luận
ad giải thích đề bài này giúp em với em đọc mà k hiểu
5 2 1 3 2 3 5 6 8 mà out put là : 3 1 3 2 thì theo ý mình hiểu là với n0=6 thì sẽ cho được 3 người vay là nhiều nhất (1 + 3+ 2) hoặc chọn (1 +2 +3) thì trong 2 cách chọn này thì người vay ít nhất đều là 1 nên in ra 1 -còn với n1=8 thì sẽ có 33 cách chọn cho nhiều người vay nhất (3 người vay) là {1,3(ở vị trí t1),5} ,{1,3,5},{3,2,3} sẽ không quan tâm đến cách chọn {3,5} vì số người vay được sẽ ít hơn , và ta in ra số lượng tiền người vay ít nhất trong 3 cacghs chọn là 2 ...