Tính tổng

Tính tổng                                                                                     Tên chương trình: SUM.PAS

    Cho số nguyên dương S và tập A gồm N số nguyên dương a1, a2, ... a_N, đôi một khác nhau và a₁=1. Ta biết rằng S có thể viết thành tổng các phần tử trong tập A.

    Hãy cho biết tổng này chứa ít nhất là bao nhiêu số hạng.

Ví dụ: Với S=14 và tập A gồm 6 phần tử là 1, 2, 3, 5, 7 , 10  thì có thể viết S theo nhiều phương án như sau:

      S = 1 + 1 + 2 + 10       ( 4 số hạng )

      S = 1 + 3 + 10                         ( 3 số hạng )

      S = 7 + 7                     ( 2 số hạng )

      .....

trong đó phương án thứ 3 là tối ưu vì chỉ dùng 2 số hạng.

Dữ liệu vào: tập tin văn bản SUM.IN, gồm:

-         Dòng đầu tiên là hai số nguyên dương S và n

-         Tiếp đến là giá trị a₁, a₂, ..., a_N có thể viết trên nhiều dòng. Các số được viết cách nhau ít nhất một dấu cách. 1  ≤   S  ≤  10000, 1  ≤   N  ≤   100, a₁=1 , dãy A được sắp tăng với các phần tử đôi một khác nhau.

Kết quả: Ghi vào tập tin văn bản SUM.OU một số nguyên dương k là số số hạng tối thiểu trong tổng biểu diễn của S.

 tải đáp án tại đây