Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2014
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 2.39 KB | None | 0 0
  1. program doitien;
  2. const   fi='doitien.inp';
  3.         fo='doitien.out';
  4.  
  5.         nmax=20;
  6.  
  7. var     a:array[1..20] of word;
  8.         n:byte;
  9.         m,s:longint;
  10.         f:text;
  11.         KQmin,KQ:array[1..20] of longint;
  12.         sl,slmin:longint;
  13.  
  14. procedure docfile;
  15. var     i:byte;
  16. begin
  17.         assign(f,fi); reset(f);
  18.         readln(f,n,m);
  19.  
  20.         for i:=1 to n do
  21.                 read(f,a[i]);
  22.  
  23.         close(f);
  24. end;
  25.  
  26. procedure sort(l,r: longint);
  27.       var
  28.          i,j,x,y: longint;
  29.       begin
  30.          i:=l;
  31.          j:=r;
  32.          x:=a[(l+r) div 2];
  33.          repeat
  34.            while a[i]>x do
  35.             inc(i);
  36.            while x>a[j] do
  37.             dec(j);
  38.            if not(i>j) then
  39.              begin
  40.                 y:=a[i];
  41.                 a[i]:=a[j];
  42.                 a[j]:=y;
  43.                 inc(i);
  44.                 j:=j-1;
  45.              end;
  46.          until i>j;
  47.          if l<j then
  48.            sort(l,j);
  49.          if i<r then
  50.            sort(i,r);
  51.       end;
  52.  
  53. procedure init;
  54. begin
  55.         fillchar(kq,sizeof(kq),0);
  56.         s:=0;
  57.         sl:=0;
  58.         slmin:=maxlongint;
  59. end;
  60.  
  61.  
  62. procedure try(i:byte);
  63. var     j:byte;
  64. begin
  65.         if s=m then
  66.                 begin
  67.                         kqmin:=kq;
  68.                         slmin:=sl;
  69.                 end
  70.         else
  71.                 for j:=1 to n do
  72.                         if (s+a[j]<=m) and (sl<slmin) then
  73.                         begin
  74.                                 inc(s,a[j]);
  75.                                 inc(sl);
  76.                                 inc(kq[j]);
  77.                                 try(j);
  78.                                 dec(kq[j]);
  79.                                 dec(sl);
  80.                                 dec(s,a[j]);
  81.                         end;
  82. end;
  83.  
  84. procedure xuat;
  85. var i:byte;
  86. begin
  87.         assign(f,fo); rewrite(f);
  88.  
  89.         if slmin<>maxlongint then
  90.                 begin
  91.                         writeln(f,slmin);
  92.                         for i:=1 to n do
  93.                                 if kqmin[i]<>0 then
  94.                                         writeln(f,a[i],' ',kqmin[i]);
  95.                 end
  96.         else
  97.                 writeln(f,'KO TIM DC');
  98.         close(f);
  99. end;
  100.  
  101.  
  102. begin
  103.         docfile;
  104.         sort(1,n);
  105.         init;
  106.         try(0);    // try may cung dc, chi la cai bat dau thoi, ko qan trong
  107.         xuat;
  108.         //readln;
  109. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement