Hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị n,s,c[i],m[i]...

Question

An được mời tham gia trò chơi "Siêu thị may mắn" do đài truyền hình ZTV tổ chức. Siêu thi được đặt trong trường quay truyền hình có n mặt hàng được đánh số từ 1 đến n và mặt hàng thứ i được niêm yết giá là c[i] đồng. Theo thể lệ trò chơi, An được ban tổ chức tặng một thẻ mua hàng có giá trị là s đồng và phải dùng hết số tiền trong thẻ này để mua hàng trong siêu thi với điều kiện mặt hàng thứ i chỉ được mua với số lượng nhiều nhất là m[i]. An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có.

Yêu cầu: Hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị n,s,c[i],m[i] (1<=n<=500; 1<=s<=10^4; 1<=c[i]<=10^4; 1<=m[i]<=100)</strong>

Input: Cho trong file văn bản SMARKET.INP

• Dòng đầu ghi hai số s, n
• N dòng tiếp theo, dòng thứ i chứa hai số c[i], m[i]

Output: Ghi ra file văn bản SMARKET.OUT

• Dòng đầu ghi d là phần dư của  tổng số cách mua hàng chia cho 131131
• Nếu d³1 thì dòng thứ hai ghi một cách mua hàng tìm được là một dãy gồm N số nguyên, trong đó số hạng thứ i là số lượng mặt hàng thứ i mua được trong cách mua này.

Ví dụ:

SMARKET.INP	SMARKET.OUT
12 3 4 1 6 2 2 1	2 0 2 0

Answer 1

{*************************************************************************
Program    :   SIEU THi MAY MAN
*************************************************************************}
const
   tfi='SMARKET.INP';
   tfo='SMARKET.OUT';
   MAXN=501;
   MAXS=10001;

var
   fi, fo: text;
   s,n: integer;
   x,c,m: array[1..MAXN] of longint;
   f: array[0..MAXS,0..MAXN] of longint;
   d: array[0..MAXS] of longint;
   sl: array[0..MAXS] of longint;

procedure doc;
var i: integer;
begin
   assign(fi,tfi); reset(fi);
   readln(fi,s,n);
   for i:=1 to n do readln(fi,c[i],m[i]);
   close(fi);
end;

procedure Tinh;
var k,i,l: integer;
begin
   for k:=0 to S do f[k,0]:=0; f[0,0]:=1;
   for i:=1 to n do
      for k:=0 to S do
         begin
            f[k,i]:=f[k,i-1];
            for l:=1 to m[i] do
               begin
                  if k-l*c[i]<0 then break;
                  f[k,i]:=(f[k,i]+f[k-l*c[i],i-1]) mod 131131;
               end;
         end;
end;

procedure viet;
var i: integer;
begin
   assign(fo,tfo); rewrite(fo);
   writeln(fo,f[s,n]);
   if f[s,n]<>0 then
      for i:=1 to n do write(fo,x[i],' '); writeln(fo);
   close(fo);
end;

procedure Tim;
var u,max,i,j,l: integer;
label l1;
begin
   if f[s,n]=0 then exit;
   fillchar(d,sizeof(d),0);
   d[0]:=-1;
   max:=0;
   for i:=1 to n do
      for j:=max downto 0 do
         if d[j]<>0 then
            begin
               for l:=1 to m[i] do
                  begin
                     if j+l*c[i]>s then break;
                     if d[j+l*c[i]]=0 then
                        begin
                           d[j+l*c[i]]:=i;
                           sl[j+l*c[i]]:=l;
                           if max0 do
      begin
         i:=d[u];
         x[i]:=sl[u];
         u:=u-x[i]*c[i];
      end;
end;

BEGIN
   doc;
   tinh;
   tim;
   viet;
END.