//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Bộ sưu tập

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 18 – Thi QG 2005 – Bảng A


Đề bài


(Tên chương trình: COLLECT.PAS )

Một bộ sưu tập tiền xu cổ được coi là có giá trị phải gồm không ít hơn Z0 đồng tiền vàng, S0 đồng tiền bạc và M0 đồng tiền đồng. Bộ sưu tập ban đầu của Alibaba có một số lượng nhất định các đồng tiền vàng, bạc và đồng nhưng chưa phải là một bộ sưu tập có giá trị. Tại Trụ sở của Hiệp hội những người sưu tầm tiền cổ có đặt một máy đổi tiền để giúp hội viên đổi được các bộ sưu tập có giá trị. Tuy nhiên, máy đổi chỉ hỗ trợ việc đổi tiền trọn gói theo quy tắc đổi gói (Z1,S1,M1) lấy gói (Z2,S2,M2) đồng tiền. Các quy tắc đổi tiền khác nhau từng đôi một, được gán số hiệu tuần tự 1,2,3,… và được công bố trước. Hội viên có thể tạo gói tiền thích hợp từ bộ sưu tập của mình để thực hiện việc đổi tiền. Các đồng tiền nhận được sau mỗi lần đổi được gộp lại với các đồng tiền mà hội viên đang có để thành một bộ sưu tập mới và có thể được sử dụng để đổi trong những lần sau nếu cần. Số lần đổi không hạn chế, tuy nhiên, là người thực dụng, Alibaba luôn cố gắng giảm tới mức tối đa số lần đổi tiền. Mặt khác, để ngăn chặn việc đầu cơ, Hiệp hội quy định, trong mọi thời điểm, mỗi hội viên không được giữ quá 4 đồng tiền mỗi loại và không được phép đổi tiếp khi đã đổi được một bộ sưu tập có giá trị.

Yêu cầu: Cho biết số lượng Z, S, M các đồng tiền vàng, bạc, đồng mà Alibaba có ban đầu và các quy tắc đổi tiền. Hãy chỉ ra tất cả các bộ sưu tập tiền cổ có giá trị mà Alibaba có thể có được sau một số lần đổi không vượt quá k cho trước.

Dữ liệu: Vào từ file văn bản COLLECT.INP.
– Dòng đầu ghi số nguyên dương k (k ≤ 1000); dòng thứ 2 ghi 6 số nguyên không âm Z, S, M, Z0, S0, M0 (0 ≤ Z, S, M, Z0, S0, M0 ≤ 4.
– Các dòng tiếp theo mỗi dòng ghi 6 số nguyên không âm Z1, S1, M1, Z2,S2, M2 xác định một quy tắc đổi tiền (0 ≤ Z1, Z2, S1, S2, M1, M2 ≤ 4).

Kết quả: Đưa ra file văn bản COLLECT.OUT.
– Nếu không tồn tại cách đổi để có được bộ sưu tập có giá trị, file kết quả chỉ gồm một số -1. Trong trường hợp ngược lại, dòng đầu ghi số v là số các bộ tiền cổ có giá trị mà Alibaba có thể đổi được.
– Dòng thứ i trong v dòng tiếp theo ghi 4 số nguyên Zi, Si, Mi, ki mô tả bộ sưu tập có giá trị thứ i và số lần đổi ki ít nhất không vượt quá k cần thực hiện để có được bộ sưu tập ấy.
Các số trên một dòng của file dữ liệu và file kết quả đặt cách nhau ít nhất một dấu cách.

Ví dụ:

COLLECT.INP COLLECT.OUT
2

4 0 1 3 3 3

1 0 1 1 1 1

2 0 1 1 3 3

2

3 3 3 1

3 4 3 2


Hướng dẫn


[]


Chương trình


{**************************************************************************
*  Program   :   Bo SUU TAP (Thi QG 2005 - Bang A)                        *
*  Date      :   01-10-2006                                               *
*  Group     :   Do thi                                                   *
**************************************************************************}
{$r+}
const
   tfi          =       'COLLECT.INP';
   tfo          =       'COLLECT.OUT';

type
   mang1        =       array[1..125,1..125] of byte;
   mang2        =       array[1..125] of integer;

var
   fi, fo       :       text;
   K            :       integer;
   z0,s0,m0     :       integer;
   a            :       mang1;
   xp           :       integer;

   Q            :       mang2;
   qf,ql        :       integer;
   Muc          :       mang2;
   Ds           :       integer;
   x            :       mang2;
   y            :       mang2;

procedure InitQ;
begin
   qf:=1;
   ql:=1;
end;

procedure Put(u: integer);
begin
   q[ql]:=u;
   inc(ql);
end;

function Get: integer;
begin
   Get:=q[qf];
   inc(qf);
end;

function Qempty: boolean;
begin
   Qempty:=(qf=ql);
end;

function Doiso(z,s,m: integer): integer;
begin
   Doiso:=25*z+5*s+m+1
end;

procedure Doidinh(p: integer; var z,s,m: integer);
var p1: integer;
begin
   z:=(p-1) div 25;
   p1:=(p-1) mod 25+1;
   s:=(p1-1) div 5;
   m:=(p1-1) mod 5;
end;


procedure Nhap;
var u,v,z,s,m,z1,s1,m1,z2,s2,m2: integer;
begin
   assign(fi,tfi); reset(fi);
   readln(fi,K);
   readln(fi,Z,S,M,Z0,S0,M0);
   fillchar(a,sizeof(a),0);
   while not seekeof(fi) do
      begin
         readln(fi,z1,s1,m1,z2,s2,m2);
         u:=Doiso(z1,s1,m1);
         v:=Doiso(z2,s2,m2);
         a[u,v]:=1;
      end;
   close(fi);
   xp:=Doiso(z,s,m);
end;

function Giatri(u: integer): boolean;
var zu,su,mu: integer;
begin
   Doidinh(u,zu,su,mu);
   Giatri:=(zu>=z0) and (su>=s0) and (mu>=m0);
end;

procedure Tinh;
var i,u: integer;
    zu,su,mu,z,s,m,r,r1,z1,s1,m1,v,zv,sv,mv: integer;
label l1;
begin
   InitQ;
   for i:=1 to 125 do Muc[i]:=-1;
   Put(xp);
   Muc[xp]:=0;
   repeat
      u:=Get;
      if Giatri(u) then
         begin
            inc(Ds);
            x[Ds]:=u;
            y[Ds]:=Muc[u];
            goto l1;
         end;
      if Muc[u]=K then goto l1;
      Doidinh(u,zu,su,mu);
      for z:=0 to zu do
         for s:=0 to su do
            for m:=0 to mu do
               begin
                  r:=Doiso(z,s,m);
                  for r1:=1 to 125 do
                     if (a[r,r1]=1) then
                        begin
                           Doidinh(r1,z1,s1,m1);
                           zv:=(zu-z)+z1; if zv>4 then zv:=4;
                           sv:=(su-s)+s1; if sv>4 then sv:=4;
                           mv:=(mu-m)+m1; if mv>4 then mv:=4;
                           v:=Doiso(zv,sv,mv);
                           if (Muc[v]=-1) then
                              begin
                                 Put(v);
                                 Muc[v]:=Muc[u]+1;
                              end;
                        end;
               end;
      l1:
   until Qempty;
end;

procedure Xuat;
var i,z,s,m: integer;
begin
   if Ds=0 then Ds:=-1;
   assign(fo,tfo); rewrite(fo);
   writeln(fo,Ds);
   for i:=1 to Ds do
      begin
         DoiDinh(x[i],z,s,m);
         writeln(fo,z,#32,s,#32,m,#32,y[i]);
      end;
   close(fo);
end;

BEGIN
   Nhap;
   Tinh;
   Xuat;
END.

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 149,868 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: