GIẢI ĐỀ THI TIN HỌC TRẺ CẤP TỈNH AN GIANG 2021 (BÀI 1 - TAM GIÁC SỐ)

Cho một tam giác số có n dòng (n<=50) như hình minh hoạ. Khi đi từ đỉnh tam giác đến đáy tam giác bằng đường gấp khúc theo quy tắc mỗi bước chỉ được đi từ số ở dòng trên xuống một trong hai số đứng kề bên phải hay bên trái ở dòng dưới. Cộng các số trên đường đi lại ta được một tổng. Hãy tìm tổng lớn nhất trong các đường đi của tam giác và ghi lại giá trị các số của đường đi có tổng lớn nhất.

Ví dụ: tam giác số có n=5

 

 7

      3        8

  8       1         0

                                                            2      7        4        4

                                                        4     5        2         6       5

Input (Dữ liệu vào) Cho từ tệp văn bản BAI01.INP gồm n+1 dòng, cụ thể:

- Dòng thứ nhất ghi giá trị của n.

- Từ dòng thứ 2 đến dòng thứ n+1: dòng thứ i ghi i-1 số cách nhau bằng kí tự trắng.

Output (Dữ liệu xuất) Ghi ra tệp văn bản BAI01.OUT gồm hai dòng:

- Dòng thứ nhất ghi tổng lớn nhất tìm được.

- Dòng thứ hai ghi từ trái sang phải giá trị các số của đường đi có tổng lớn nhất bắt đầu từ đỉnh của tam giác.

Ví dụ:

BAI01.INP	BAI01.OUT
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5	30 7 3 8 7 5

CODE THAM KHẢO:

program tamgiacso;

var A:array[1..100,1..100] of integer;

    n, tong, max, L: integer;

    X, Luu: array[1..100] of integer;

    fi,fo:text;

procedure nhap;

var i,j: byte;

begin

        assign(fi,'BAI01.INP'); reset(fi);

        readln(fi,n);

        for i:=1 to n do

          for j:=1 to i do read(fi,A[i,j]);

        close(fi);

end;

procedure try(i,k:byte);

var j,h: byte;

begin

        for j:=k to k+1 do

        begin

                tong:=tong+A[i,j];

                X[i]:=A[i,j];

                if i = n then

                begin

                        if max < tong then

                        begin

                                max:=tong; luu:=x;

                        end;

                end

                else try(i+1,j);

                tong:=tong-A[i,j];

        end;

end;

begin

        assign(fo,'BAI01.OUT'); rewrite(fo);

        tong:=0; max:=0;

        nhap;

        try(1,1);

        writeln(fo,max);

        for L:=1 to n do write(fo,Luu[l],' ');

        close(fo);

end.