Advertisement
savrasov

Untitled

Jan 8th, 2017
1,513
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. program lodki;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses
  6.   SysUtils;
  7.  
  8. var
  9.   a: array [1..20000] of integer;
  10.   n, k, i, j, f, t: integer;
  11.   boo: array [1..20000] of boolean;
  12.  
  13. procedure qsort(min, max: Integer);
  14. var
  15.   i, j, s, t: integer;
  16. begin
  17.   s := a[max - ((max - min) div 2)];
  18.   i := min;
  19.   j := max;
  20.   while (i < j) do
  21.     begin
  22.       while a[i] < s do i := i + 1;
  23.       while a[j] > s do j := j - 1;
  24.       if i <= j then
  25.       begin
  26.         t := a[i];
  27.         a[i] := a[j];
  28.         a[j] := t;
  29.         i := i + 1;
  30.         j := j - 1;
  31.       end;
  32.     end;
  33.   if min < j then qsort(min, j);
  34.   if i < max then qsort(i, max);
  35. end;
  36.  
  37. begin
  38.   readln(n, k);
  39.   f := 0;
  40.   for i := 1 to n do read(a[i]);
  41.   qsort(0, n);
  42.   for i := n downto 1 do
  43.     if not (boo[i]) then
  44.     begin
  45.       boo[i] := true;
  46.       inc(f);
  47.       t := k - a[i];
  48.       j := i - 1;
  49.       while (t > 0) and (j > 0) do
  50.         if (not boo[j]) and (t - a[j] >= 0) then
  51.         begin
  52.           boo[j] := true;
  53.           dec(t, a[j]);
  54.           dec(j);
  55.         end
  56.         else dec(j);
  57.     end;
  58.   writeln(f);
  59. end.
Advertisement
RAW Paste Data Copied
Advertisement