tuankiet65

Untitled

Sep 20th, 2016
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 1.76 KB | None | 0 0
  1. Const
  2.     fi = '';
  3.     fo = '';
  4. Var f, g: TEXT;
  5.     n, k, i, res, t, test: LONGINT;
  6.     a, aa: Array[1..100000] Of LONGINT;
  7.     b: Array[1..100000] Of BOOLEAN;
  8. {Function factable(x, n: LONGINT):BOOLEAN;
  9. Var j: LONGINT;
  10. Begin
  11.     If x=0 Then Exit(TRUE);
  12.     For j:=n DownTo 1 Do
  13.     If b[j] And (a[j]<=x) Then
  14.     Begin
  15.         b[j]:=FALSE;
  16.         If factable(x-a[j], n) Then
  17.         Begin
  18.             b[j]:=TRUE;
  19.             Exit(TRUE);
  20.         End;
  21.         b[j]:=TRUE;
  22.     End;
  23.     Exit(FALSE);
  24. End;}
  25. Procedure Sort(l, r: LONGINT);
  26. Var i, j, x, temp: LONGINT;
  27. Begin
  28.     x:=aa[(l+r) Div 2];
  29.     i:=l;
  30.     j:=r;
  31.     While i<=j Do
  32.     Begin
  33.         While aa[i]<x Do Inc(i);
  34.         While aa[j]>x Do Dec(j);
  35.         If i<=j Then
  36.         Begin
  37.             temp:=aa[i];
  38.             aa[i]:=aa[j];
  39.             aa[j]:=temp;
  40.             Inc(i);
  41.             Dec(j);
  42.         End;
  43.     End;
  44.     If i<r Then Sort(i, r);
  45.     If l<j Then Sort(l, j);
  46. End;
  47. Function check(n: LONGINT):BOOLEAN;
  48. Var i: LONGINT;
  49.     sum: INT64;
  50. Begin
  51.     For i:=1 To n Do aa[i]:=a[i];
  52.     Sort(1, n);
  53.     sum:=0;
  54.     For i:=1 To n Do
  55.     Begin
  56.         If aa[i]>sum+1 Then Exit(FALSE);
  57.         sum:=sum+aa[i];
  58.         If sum>=k Then Exit(TRUE);
  59.     End;
  60.     Exit(sum>=k);
  61. End;
  62. Function find(l, r: LONGINT):LONGINT;
  63. Var k, x: LONGINT;
  64. Begin
  65.     k:=-1;
  66.     While l<=r Do
  67.     Begin
  68.         x:=(l+r) Div 2;
  69.         If check(x) Then
  70.         Begin k:=x; r:=x-1; End Else
  71.         l:=x+1;
  72.     End;
  73.     Exit(k);
  74. End;
  75. BEGIN
  76.     Assign(f, fi); Reset(f);
  77.     Assign(g, fo); Rewrite(g);
  78.     Readln(f, t);
  79.     For test:=1 To t Do
  80.     Begin
  81.         Readln(f, n, k);
  82.         For i:=1 To n Do Read(f, a[i]);
  83.         res:=find(1, n);
  84.         Writeln(g, res);
  85.     End;
  86.     Close(g);
  87. END.
Advertisement