Mái ngói | Câu khó - Đề thi HSG tin 12 Nghệ An | Năm 2012-2013

Cho M (1 £ M £ 10) viên ngói vuông kích thước 5 ´ 5, được lợp trên một mái nhà hình vuông kích thước N x N (5 £ N £ 15), lần lượt mỗi lần 1 viên, các cạnh của chúng song song với các cạnh của mái. Các viên ngói được đặt tên là chữ cái liên tiếp bắt đầu từ A (theo bảng chữ cái tiếng Anh).
            Ví dụ viên ngói A được mô tả là:       AAAAA
                             AAAAA
                             AAAAA
                             AAAAA
                             AAAAA
và nếu có 5 viên ngói thì chúng sẽ được gọi là A, B, C, D, E. Viên ngói đặt sau có thể che một phần hoặc che cả viên ngói đặt trước đó. Sau khi viên ngói cuối cùng được đặt lên mái ta thu được một Mai_ngoi. Ví dụ, Mai_ngoi 1 biểu thị rằng viên ngói A được đặt sau viên ngói B trên một mái vuông 11 x 11.
      Mai_ngoi 1              Mai_ngoi 2                 Mai_ngoi 3                 Mai_ngoi 4
...........   ...........    ...........    ...AAAAA...
..BBBBB....   ..BBBBB....    ...........    ...AAAAA...
..BBBBB....   ..BBBBB....    ....AAAA...    ...AAAAA...
..BBBBB....   ..BBBBB....    ...BAAAAB..    ...AAAAADDD
..BBAAAAA..   ..BBAAAAA..    ...BAAAAB..    BBBBBAAADDD
..BBAAAAA..   ..BBAAAAACC    ...BAAAAB..    BBBBB.DDDDD
....AAAAA..   DDDDAAAAACC    .CCCAAAAB..    BBBCCCDDDDD
....AAAAA..   DDDDAAAAACC    .C.CCCBBB..    BBBCCCDDDDD
....AAAAA..   DDDDAAAAACC    .CCCCC.....    BBBCCCCC...
...........   DDDDD.CCCCC    .CCCCC.....    ...CCCCC...
...........   DDDDD......    .CCCCC.....    ...CCCCC...
The tiles are named with consecutive letters beginning from A.  For example, if there are 5 tiles, then they will be called A, B, C, D and E.  In a top-view, each position on the table is represented either by a “.” if that position is not covered or a letter which is the name of the tile that is top-most at that position.            Trong một Mai_ngoi, mỗi vị trí trên mái được ký hiệu bởi một dấu chấm "." nếu vị trí đó không bị phủ bởi một chữ cái là tên của viên ngói trên cùng tại vị trí đó.
If the given top-view is valid, it is possible to decide a set of tiles each of which might have been the very first tile that was placed on the table.  For example, consider Top-view 2.  It is possible that tile B or C or D is the first tile that was placed on the table. However, it is impossible that A is the first tile that was placed on the table.            Một Mai_ngoi là hợp lệ nếu có thể xác định được một tập các viên ngói mà mỗi một trong chúng có thể là viên đầu tiên đã được đặt lên mái. Ví dụ ở Mai_ngoi2, có thể viên ngói B hoặc C hoặc D là viên ngói đầu tiên đã được đặt lên mái, nhưng A không thể là viên ngói đầu tiên đã được đặt lên mái.
            There are two possible reasons that a top-view is invalid.  The first reason is that some tiles are not a 5 ´ 5 square.  For example, Top-view 3 is invalid: A is a 4 ´ 5 tile, the width of B exceeds 5, and C has a hole.  Any of these reasons is enough to conclude that this top-view is invalid. Một Mai_ngoi là không hợp lệ nếu xảy ra một trong hai điều sau:
            - Có viên ngói không đúng dạng mô tả. Ví dụ  Mai_ngoi 3 là không hợp lệ vì có A là viên 4 x 5, hay chiều rộng của viên B vượt quá 5, hay viên C có một lỗ thủng.
The second reason is that tiles could not have been placed one after another. It is impossible that the tiles in Top-view 4 were placed one at a time ¾ the four tiles are interlocking.  Hence, this top-view is invalid.            - Các viên ngói không được đặt theo lần lượt viên này sau viên kia. Ví dụ trong Mai_ngoi 4 được đặt một lúc 4 viên ngói lồng vào nhau. Do đó, Mai_ngoi4 là không hợp lệ.
5.1 RequirementsYêu cầu:Given a top-view, if it is invalid, you are to output the 2 letters “NO”.  Otherwise, you are to output the letters in ascending order of the tiles each of which might be the first tile. Cho một Mai_ngoi, nếu nó không hợp lệ thì đưa ra ‘NO’. Nếu hợp lệ thì đưa ra các chữ cái theo thứ tự tăng dần của các viên ngói mà mỗi một trong số đó có thể là  viên ngói đầu tiên.
5.2 Input File TILE.IN Dữ liệu: Vào từ file văn bản Bai4.inp:

• The file contains the integer M , the number of tiles, on the first line; the integer N , the size of the N ´ N square table on the next line; and then the top-view, given as one row at each line. Dòng đầu tiên chứa số nguyên M là số lượng viên ngói;
• Dòng tiếp theo chứa số nguyên N là kích thước của bảng vuông N x N ;
• N dòng tiếp theo miêu tả Mai_ngoi.

5.3 Output File TILE.OUT Kết quả: Ghi ra file văn bản Bai4.out:

• The output file contains either the string “NO”, or a string of letters (in ascending order) representing the possible first tiles.  There should be no spaces between the letters. Là chuỗi "NO" nếu Mai_ngoi không hợp lệ, còn nếu Mai_ngoi hợp lệ thì đưa ra một chuỗi các chữ cái (theo thứ tự tăng dần) là đại diện cho các viên ngói có thể là viên đầu tiên. Không có dấu cách giữa các chữ cái.

 Ví dụ:

Bai4.inp	Bai4.out
4 4 15 10 ......................... ..BBBBB... ..BBBBB... ..BBBBB... ..BBAAAAA. .CCCCCAAA. .CCCCCAAA. .CCCCCAAA. .CCCCCAAA. .CCCCC....	BD

 

Code mẫu bằng Pascal

const   fi      =       'bai4.inp';
        fo      =       'bai4.OUT';
        chu     =       'ABCDEFGHIJ.';
        so      =       '0123456789';

var     f       :       text;
        a       :       array[1..15] of string;
        d       :       array[1..11,1..4]of byte;
        g,kq    :       array[1..11]of byte;
        m,n     :       byte;
function min(a,b:byte):byte;
begin if a>b then min:=b
        else min:=a;
end;

function max(a,b:byte):byte;
begin if a>b then max:=a
        else max:=b;
end;

procedure nhap;
var i,j,r:byte;
begin
    assign(f,fi);reset(f);
    readln(f,m);
    readln(f,n);
    for i:=1 to m do g[i]:=1;
    for i:=1 to m do kq[i]:=1;
    for i:=1 to m do begin d[i,1]:=11;d[i,2]:=11;end;
    for i:=1 to n do
        begin
             for j:=1 to n do
                 begin
                      read(f,a[i,j]);
                      r:=pos(a[i,j],chu);
                      if (r=0)or(r=11) then continue;
                      g[r]:=0;
                      kq[r]:=0;
                      d[r,1]:=min(d[r,1],i);
                      d[r,2]:=min(d[r,2],j);
                      d[r,3]:=max(d[r,3],i);
                      d[r,4]:=max(d[r,4],j);
                 end;
        readln(f);
        end;
    close(f);
end;

procedure lat(i,j:byte;ch:char);
var x,y,r:byte;s:string;
begin
    r:=pos(ch,chu)-1;
    str(r,s);
    ch:=s[1];
    for x:=i to i+4 do
    for y:=j to j+4 do a[x,y]:=ch;
end;

function kt:boolean;{kiem tra trong}
var i,u,v:byte;
begin
    kt:=true;
    for i:=1 to m do
        begin
             if (d[i,3]-d[i,1]>4)or(d[i,4]-d[i,2]>4) then
                                begin
                                kt:=false;
                                exit;
                                end;

             for u:=d[i,1] to d[i,3] do
             for v:=d[i,2] to d[i,4] do
                if pos(a[u,v],chu)=0 then
                                begin
                                kt:=false;
                                exit;
                                end;
        end;
end;
function kt_lat(u,v:integer;k:char):boolean;
var i,j:byte;
begin
    kt_lat:=true;
    for i:=u to u+4 do
    for j:=v to v+4 do
        if (a[i,j]<>k)and(pos(a[i,j],chu)>0) then
                                                begin
                                                    kt_lat:=false;
                                                    exit;
                                                end;
end;

function kt_cuoi(i,j:byte):boolean;
var r:char;u,v:byte;
begin
    r:=a[i,j];
    kt_cuoi:=true;
    for u:=i to i+4 do
    for v:=j to j+4 do if a[u,v]<>r then begin kt_cuoi:=false;exit;end;
end;

procedure xuat(r:byte);
var i:byte;
begin
    assign(f,fo);rewrite(f);
    if r=1 then writeln(f,'NO')
    else for i:=1 to m do if kq[i]=1 then write(f,chu[i]);
    close(f);
end;
procedure thuc_hien;
var i,j,r,sll:byte;
    u,v:integer;
begin
    if not kt then begin xuat(1);halt;end;

    sll:=0;
    for i:=1 to m do
        begin
             for j:=1 to m do
                if g[j]=0 then
                  begin
                     for u:=d[j,3]-4 to d[j,1] do
                     if (u>0)and(u+4<=n) then
                     for v:=d[j,4]-4 to d[j,2] do
                     if (v>0)and(v+4<=n) then
                     if kt_lat(u,v,chu[j]) then
                        begin
                                lat(u,v,chu[j]);
                                g[j]:=1;
                                inc(sll);
                        end;
                 end;
        end;

    for i:=1 to m do if g[i]=0 then begin xuat(1);halt;end;

    if (sll=1) then begin xuat(2);halt;end;

    for i:=1 to n-4 do
    for j:=1 to n-4 do
    if pos(a[i,j],so)>0 then
    if kt_cuoi(i,j) then
                                            begin
                                                r:=pos(a[i,j],so);
                                                kq[r]:=1;
                                            end;
    xuat(2);
end;
BEGIN
nhap;
thuc_hien;
END.

Các test

Các test được đính kèm cuối bài nhé.

 

Tham gia thảo luận

Để trao đổi ý kiến, phải hồi hay gửi các thắc mắc cũng như yêu cầu giải đề, mời các bạn tham gia nhóm và trang facebook sau:
Nhóm facebook: f / BAITAPONHA
Trang facebook: f / HỌC MÃI