Petro

(Джерело: http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=117)

Задача. Петрик П'яточкін хоче дістати яблуко, яке висить на висоті N (N>=1) метрів. Для цього йому потрібно зв'язати кілька жердин, довжини яких він знає. Таких жердин у нього М (М>=1), кожна має довжину L_і. Яку найменшу кількість жердин йому потрібно зв'язати щоб дістати яблуко? Вважати, що жердини монтуються стик в стик, тобто при зв'язуванні жодний сантиметр жодної жердини не втрачається.

Технічні умови. Програма Petro читає з клавіатури рядок чисел через пропуск: N, M, L₁, L₂, ..., L_M. Програма виводить єдине число - шукану величину. Якщо яблуко дістати неможливо, програма повинна вивести 0.  

Приклади.
Введення: 10 5 1 3 4 3 6
Виведення: 2

Введення: 10 5 1 1 1 1 1
Виведення: 0

Розв'язання.

Після введення даних, будемо шукати найбільшу жердину (Lm) та її номер (Im) і додаватимемо її до зв'язаних жердин (Ld) доки останні не досягнуть потрібної висоти (N).

Запишемо алгоритми мовами програмування.

Free Pascal:
Var N, M, I, J,
    Ld, Lm, Im : Integer;
             L : Array [1..50] Of Integer;
Begin
 Read (N, M);
 For I := 1 To M Do
  Read (L[I]);
 Ld := 0;
 For I := 1 To M Do Begin
  Lm := L[I];
  Im := I;
  For J := I+1 To M Do
   If L[J] > Lm
    Then Begin
     Lm := L[J];
     Im := J;
    End;
  Ld += Lm;
  If Ld >= N
   Then Break;
  L[Im] := L[I];
 End;
 If Ld >= N
  Then Write (I)
  Else Write (0);
End.

C++:
#include <iostream>
using namespace std;
int main(){
 int n, m, i;
 cin >> n >> m;
 int l[m-1], ld=0;
 for (i=0; i<m; i++)
  cin >> l[i];
 for (i=0; i<m; i++) {
  int lm=l[i], im=i;
  for (int j=i+1; j<m; j++)
   if (l[j]>lm)
    lm=l[j], im=j;
    ld+=lm;
    if (ld>=n) break;
    l[im]=l[i];
 }
 if (ld>=n)
  cout << i+1;
  else cout << 0;
}