Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
2. Siêu thị may mắn In E-mail
(11 votes)
Người viết: Ngô Minh Đức   
20/06/2008

Bài 2. Siêu thị may mắn (7 điểm)

An được mời tham gia trò chơi “Siêu thị may mắn” do đài truyền hình ZTV tổ chức.

Siêu thị được đặt trong trường quay truyền hình có n mặt hàng được đánh số từ 1 đến n và mặt hàng thứ i được niêm yết giá là ci đồng, i = 1, 2, ..., n. Theo thể lệ của trò chơi, An được ban tổ chức tặng một thẻ mua hàng có giá trị là s đồng và phải dùng hết số tiền trong thẻ này để mua hàng trong siêu thị với điều kiện mặt hàng thứ i chỉ được mua với số lượng nhiều nhất là mi,   i = 1, 2, …, n. An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có.

Yêu cầu: Hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị n, s, ci mi (1 ≤ n ≤ 500; 1 ≤ s ≤ 105; 1 ≤ ci ≤ 104; 1 ≤ mi ≤ 100) với i = 1, 2, …, n.

Dữ liệu: Vào từ file văn bản SMARKET.INP

·         Dòng đầu tiên chứa hai số nguyên dương s n;

·         Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên dương ci mi với i = 1, 2, …, n.

Kết quả: Ghi ra file văn bản SMARKET.OUT

·         Dòng đầu tiên ghi số nguyên d là tổng số cách mua hàng tìm được;

·         Nếu d ≥ 1 thì dòng thứ hai ghi một cách mua hàng tìm được là một dãy n số nguyên, trong đó số hạng thứ i là số lượng mặt hàng thứ i mua được trong cách mua hàng này,       i = 1, 2, …, n.

Hai số liên tiếp trên một dòng trong file dữ liệu và file kết quả cách nhau ít nhất một dấu cách.

Ví dụ:

SMARKET.INP

SMARKET.OUT

12 3

4 1

6 2

2 1

2

0 2 0

 
< Trước   Tiếp >