Editorial for Chấm điểm


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const max=200;
var n,m,s:byte;
    a:array[1..20,1..20] of integer;
    b:array[0..20,1..20,0..max] of byte;
    d:array[1..20] of byte;

procedure rf;
var i,j:byte;
begin
     readln(s,n,m);
     for i:=1 to m do
     begin
          for j:=1 to n do
              read(a[i,j]);
          readln;
     end;
end;

procedure pr;
var i,j,k,p:integer;
begin
     fillchar(b,sizeof(b),0);
     for i:=1 to m do
         b[1,i,a[i,1]]:=i;
     for i:=2 to n do
       for j:=1 to m do
         for k:=1 to s do
           for p:=1 to m do
            if (k>a[p,i]) and (b[i-1,j,k-a[p,i]]>0) and (a[j,i-1]<=a[p,i]) 

then
               b[i,p,k]:=j;
end;

procedure wf;
var i,j,t:byte; kt:boolean;
begin
     kt:=false;
     for i:=1 to m do
         if b[n,i,s]>0 then
         begin
              kt:=true;
              break;
         end;
     if kt then
     begin
          writeln('YES');
          d[n]:=i; t:=s;
          for i:=n-1 downto 1 do
          begin
               d[i]:=b[i+1,d[i+1],t];
               t:=t-a[d[i+1],i+1];
          end;
          for i:=1 to n do write(a[d[i],i],' ');
     end
     else write('NO');
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 25
#define K 25
#define S 205

int s, k, n, f[K][S], a[K][N];

int main() {
    //freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
    scanf( "%d%d%d", &s, &k, &n );
    rep(j, n) rep(i, k) scanf( "%d", &a[i][j] );
    rep(i, k+1) rep(j, s+1) {
        if( i == 0 && j == 0 ) f[i][j] = 0;
        else if ( i == 0 || j == 0 ) f[i][j] = INF;
        else {
            f[i][j] = INF;
            rep(x, n) if( a[i-1][x] < f[i][j] && a[i-1][x] <= j && f[i-1][j-a[i-1][x]] <= a[i-1][x] )
                f[i][j] = a[i-1][x];
        }
    }
    if( f[k][s] == INF ) puts("NO"); 
    else {
        puts("YES");
        stack<int> st;
        while( s != 0 ) {
            st.push(f[k][s]);
            s -= f[k--][s];
        }
        for(;!st.empty(); st.pop()) printf( "%d ", st.top() );
        putchar(10);
    }
    return 0;
}

Code mẫu của ladpro98

program v8score;//dp
uses    math;
const   fi='';
var     a,trace:array[0..21,0..21] of longint;
        f,check:array[0..21,0..21,0..200] of boolean;
        n,k,s:longint;
procedure input;
var     inp:text;
        i,j:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,s,k,n);
        for i:=1 to n do
        begin
                for j:=1 to k do
                read(inp,a[i,j]);
                readln(inp);
        end;
        close(inp);

end;

procedure init;
var     i,j:longint;
begin
        for i:=1 to n do
        begin
                f[i,0,0]:=true;
                check[i,0,0]:=true;
                a[i,0]:=low(longint);
        end;

end;

function dp(i,j,k:longint):boolean;
var     c:longint;
begin
        if (k<a[i,j]) and (j<>0) then exit(false);
        if (check[i,j,k]) then exit(f[i,j,k]);
        check[i,j,k]:=true;

        for c:=1 to n do
        begin
                if a[c,j-1]>a[i,j] then continue;
                if dp(c,j-1,k-a[i,j])
                then
                begin
                        f[i,j,k]:=true;
                        trace[i,j]:=c;
                        exit(true);
                end;
        end;
        f[i,j,k]:=false;
        exit(false);
end;

procedure process;
var     i,j:longint;
begin
        for i:=1 to n do
                dp(i,k,s);

end;

procedure output;
var     res:array[0..21] of longint;
        ok:boolean;
        i,j,hang:longint;
begin
        ok:=false;
        for i:=1 to n do
        begin
                if dp(i,k,s) then
                begin
                        writeln('YES');
                        hang:=i;
                        for j:=k downto 1 do
                        begin
                                res[j]:=a[hang,j];
                                hang:=trace[hang,j];
                        end;
                        ok:=true;
                        break;
                end;
        end;
        if ok then
        for i:=1 to k do
        write(res[i],' ')
        else write('NO');
end;

begin
        input;
        init;
        //process;
        output;

end.

Code mẫu của RR

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=20;
  MAXS=200;
var
  s,k,n:longint;
  trace,d:array[1..MAXN,1..MAXS,1..MAXN] of longint;
  c:array[1..MAXN,1..MAXN] of longint;
procedure inp;
var
  f:text;
  i,j:longint;
begin
  assign(f,FINP); reset(f);
  read(f,s,k,n);
  for i:=1 to n do
  for j:=1 to k do
    read(f,c[i,j]);
  close(f);
end;
procedure solve;
var
  sum,last,pre,i:longint;
begin
  for i:=1 to n do
    d[k,c[i,k],i]:=1;
  for i:=k-1 downto 1 do
  for sum:=1 to s do
  for last:=1 to n do
    for pre:=1 to n do
      if (sum>c[last,i]) and (d[i+1,sum-c[last,i],pre]=1) and (c[last,i]<=c[pre,i+1]) then
        begin
          d[i,sum,last]:=1;
          trace[i,sum,last]:=pre;
        end;
end;
procedure ans;
var
  f:text;
  i,j,sum,u:longint;
begin
  assign(f,FOUT); rewrite(f);
  sum:=s;
  i:=1; while (i<=n) and (d[1,sum,i]=0) do inc(i);
  if i=n+1 then writeln(f,'NO')
  else
    begin
      writeln(f,'YES');
      for j:=1 to k do
        begin
          write(f,c[i,j],' ');
          u:=sum-c[i,j];
          i:=trace[j,sum,i];
          sum:=u;
        end;
    end;
  close(f);
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của ll931110

Program V8SCORE;
        Const
                input  = '';
                output = '';
        Var
                      a: array[1..20,1..20] of integer;
                      F: array[1..400,1..20] of integer;
                      x: array[1..20] of integer;
                n,k,sum: integer;

Procedure init;
          Var
                fi: text;
               i,j: integer;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Readln(fi, sum, k, n);
                For i:= 1 to n do
                    Begin
                         For j:= 1 to k do read(fi, a[i,j]);
                         Readln(fi);
                    End;

                Close(fi);
          End;

Procedure optimize;
          Var
                i,s,t: integer;
          Begin
                Fillchar(F, sizeof(F), 0);
                  For i:= 1 to n do F[a[i,1],1]:= a[i,1];

                For t:= 1 to k - 1 do
                    For i:= 1 to 200 do
                        For s:= 1 to n do

                   if (F[i,t] <> 0) and ((F[i + a[s,t + 1],t + 1] = 0)
                       or (a[s,t + 1] < F[i + a[s,t + 1],t + 1])) and (a[s,t + 1] >= F[i,t])
                         then F[i + a[s,t + 1],t + 1]:= a[s,t + 1];
          End;

Procedure solve;
          Var
                fo: text;
                 i: integer;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                If F[sum,k] = 0 then writeln(fo, 'NO') else
                        Begin
                                For i:= k downto 1 do
                                        Begin
                                                x[i]:= F[sum,i];
                                                sum:= sum - x[i];
                                        End;

                                Writeln(fo, 'YES');
                                For i:= 1 to k do write(fo, x[i], ' ');
                        End;
                Close(fo);
          End;

Begin
        init;
        optimize;
        solve;
End.

Code mẫu của skyvn97

#include<stdio.h>
int s,n,k;
bool fin;
int a[22][22];
int x[22];
int tmp;
void swap(int &a,int &b)
{
     int sw;
     sw=a;a=b;b=sw;
}
void init(void)
{
     int i,j,l;
     scanf("%d",&s);
     scanf("%d",&k);
     scanf("%d",&n);
     for (i=1;i<=n;i=i+1)
         for (j=1;j<=k;j=j+1)
             scanf("%d",&a[i][j]);
     fin=false;
     for (i=1;i<=k;i=i+1)
         for (j=1;j<n;j=j+1)
             for (l=j+1;l<=n;l=l+1)
                 if (a[j][i]<a[l][i]) swap(a[j][i],a[l][i]);
     tmp=0;
     x[0]=-1;
}
void print(void)
{
     if (s!=tmp) return;
     printf("YES\n");
     int i;
     for (i=1;i<k;i=i+1)
         printf("%d ",x[i]);
     printf("%d",x[k]);
     fin=true;
}
void btrk(int t)
{
     int i;
     for (i=1;i<=n;i=i+1)
         {
          if (a[i][t]<x[t-1]) break;
          x[t]=a[i][t];
          tmp=tmp+a[i][t];
          if (s-tmp>=x[t]*(k-t))
             {
              if (t==k) print();
              else
                  if (!fin) btrk(t+1);
             }
          tmp=tmp-a[i][t];
         }
}
int main(void)
{
    init();
    btrk(1);
    if (!fin) printf("NO");
}

Code mẫu của khuc_tuan

var
 s, k, n : integer;
 F : array[0..20,0..200,0..200] of boolean;
 a : array[1..20,1..20] of integer;
procedure nhap;
var
 i, j : integer;
begin
    read( s, k, n);
    for i:=1 to n do for j:=1 to k do read(a[i,j]);
end;
procedure qhd;
var
 bai, gk, dmax, tong : integer;
begin
     F[0,0,0] := true;
     for bai:=1 to k do begin
         for gk:=1 to n do begin
             for dmax:=0 to a[gk,bai] do begin
                 for tong:=0 to s-a[gk,bai] do if F[bai-1,dmax,tong] then
                      F[bai,a[gk,bai],tong+a[gk,bai]] := true;
             end;
         end;
     end;
end;

procedure truy( sb, dm, tong : integer);
var
   gk, ndm : integer;
      ok : boolean;
begin
     if sb=0 then exit;
     for gk:=1 to n do if (a[gk,sb]=dm) and (tong>=a[gk,sb]) then begin
       ok := false;
         for ndm:=0 to dm do if f[sb-1,ndm,tong-a[gk,sb]] then
         begin
              ok := true;

              truy( sb-1, ndm, tong - a[gk,sb]);
              write( a[gk,sb],' ');
              break;
         end;
        if ok then break;
     end;
end;

var dm : integer;
 co : boolean;
begin
    nhap;
    qhd;
    co := false;
    for dm:=0 to s do if F[k,dm,s] then begin
    writeln('YES');
      truy( k, dm, s);
      co := true;
      break;
    end;
    if not co then writeln('NO');
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.