Bài 4: Nhà sưu tập
Nam luôn tự hào mình là người sưu tập được nhiều tem nhất. Hồng cũng sưu tập tem, cô ấy muốn chứng tỏ bộ sưu tập tem của mình còn lớn hơn của Nam và cô ta có một kế hoạch. Cô ấy bí mật hỏi bạn bè cho cô ấy mượn tem. Nam rất tin tưởng vào sự tốt nhất của bộ tem của mình, cho nên anh ta luôn nói cho mọi người biết anh ta sẽ trưng bày bao nhiêu con tem. Hồng biết mình có bao nhiêu con tem và cô ta biết rằng mình cần bao nhiêu con tem nữa. Cô ấy cũng biết có bao nhiêu người bạn sẽ cho cô mượn tem và mỗi người sẽ cho mượn bao nhiêu. Nhưng cô ấy muốn mượn từ một số người bạn ít nhất có thể. Bạn hãy viết chương trình, tính giúp cô ấy cần mượn tem từ ít nhất bao nhiêu người bạn.
Dữ liệu vào:
Dòng 1: Hai số nguyên s và n (1<= s <= 106, 1<= n <= 105) ngăn cách nhau bởi một dấu cách, ở đó s là số con tem tối thiểu mà Hồng cần mượn và n là số người bạn sẽ cho Hồng mượn tem.
Dòng 2: n số nguyên dương a1, a2, ..., an là số tem của mỗi người bạn sẽ cho Hồng mượn.
Kết quả: Một số duy nhất là số người bạn ít nhất mà Hồng cần mượn tem. Trong trường hợp Hồng không mượn được số tem tối thiểu mình cần thì ghi ra số 0.
Ví dụ:
Dữ liệu vào | Kết quả |
100 6 13 17 42 9 23 57 | 3 |
1000 3 314 159 265 | 0 |
ngon ngu lap trinh pascal nha.
program NhaSuuTapTem;
var a: array[1..100000] of Integer;
s, n, i, j, sum, count: Integer;
procedure SortDescending(var arr: array of Integer; n: Integer);
var i, j, temp: Integer;
begin
for i := 1 to n - 1 do
for j := i + 1 to n do
if arr[i] < arr[j] then
begin
temp := arr[i];
arr[i] := arr[j];
arr[j] := temp;
end;
end;
begin
ReadLn(s, n);
for i := 1 to n do
Read(a[i]);
SortDescending(a, n);
sum := 0;
count := 0;
for i := 1 to n do
begin
sum := sum + a[i];
count := count + 1;
if sum >= s then
begin
WriteLn(count);
Exit;
end;
end;
WriteLn(0);
end.
