Задание »

Pentamino – 2

ID: pentam2
Grūtība: 2/5
Laika limits: 1


Uzdevums

Pentamino figūras veido no pieciem kvadrātiem, novietojot tos tā, ka katram kvadrātam ir kopīga mala ar kādu citu.
Šoreiz izmantosim tikai pieca veida pentamino figūras:

Sauksim tās par A, B, C, D un E veida figūrām. Katra veida figūrai viens kvadrāts ir iekrāsots citādi. Sauksim to par attiecīgā veida figūras galveno kvadrātu.

Kvadrātveida rūtiņu laukumā, kura izmēri ir K*K rūtiņas, izvietosim ne vairāk kā 100 iepriekšminētā veida figūras tā, lai katras figūras kvadrāti sakristu ar laukuma rūtiņām, un katra no figūrām pilnībā ietilptu laukumā. Figūras drīkst pārklāties. Figūras nedrīkst būt pagrieztas vai apgrieztas. Laukuma kolonnas ir sanumurētas no kreisās puses uz labo ar naturāliem skaitļiem no 1 līdz K pēc kārtas. Analoģiski no lejas uz augšu ir sanumurētas arī rindas.

Jūsu uzdevums ir uzrakstīt programmu, kas nosaka, cik no laukuma rūtiņām noklāj vismaz viena pentamino figūra.

Ievaddati

Teksta faila pentam2.in pirmā rinda satur naturālu skaitli K, 1 <= K <= 100, kas apzīmē laukuma malas garumu.
Faila otrā rinda satur naturālu skaitli N, 1 <= N <= 100, kas apzīmē uz laukuma izvietoto pentamino figūru skaitu.
Katrā no nākošajām N faila rindām tiek dotas kādas figūras apraksts formā

burts kolonnas_numurs rindas_numurs

, kur burts norāda attiecīgās figūras veidu (A,B,C,D vai E), bet kolonnas un rindas numurs norāda laukuma rūtiņu, kuru noklāj šīs figūras galvenais kvadrāts. Starp burtu un kolonnas numuru, kā arī starp kolonnas numuru un rindas numuru ir viens tukšumsimbols.

Izvaddati

Teksta faila pentam2.out vienīgajā rindā jāizvada viens naturāls skaitlis – laukuma rūtiņu skaits, ko noklāj dotās pentamino figūras.

Piemērs

pentam2.in pentam2.out
8
5
A 2 5
D 5 7
B 7 6
D 8 1
E 4 6
23

Atsauces

Uzdevums ideja ņemta no uzdevuma, kas izmantots ACSL sacensībās 1996./97. gadā.
Autors: M.Opmanis


© 2001-2002 olimps! http://www.lio.lv/olimps/

Решение »

program pentam1;
var f:text; a,b,i,n,s:byte; t:char; arr:array [1..101,1..101] of byte;
procedure add();
 begin
  arr[a,b]:=1;
  case t of
   'A': begin arr[a,b-1]:=1; arr[a,b-2]:=1; arr[a+1,b-2]:=1; arr[a+2,b-2]:=1; end;
   'B': begin arr[a+1,b]:=1; arr[a+1,b-1]:=1; arr[a,b-1]:=1; arr[a,b-2]:=1; end;
   'C': begin arr[a+1,b]:=1; arr[a-1,b]:=1; arr[a+1,b-1]:=1; arr[a-1,b-1]:=1; end;
   'D': begin arr[a,b+1]:=1; arr[a-1,b]:=1; arr[a-2,b]:=1; arr[a-3,b]:=1; end;
   'E': begin arr[a,b+1]:=1; arr[a-1,b]:=1; arr[a-2,b]:=1; arr[a-2,b-1]:=1; end;
  end;
 end;
{========================}
begin
assign(f,'pentam2.in');
reset(f);
readln(f,s);
readln(f,n);
for i:=1 to n do
 begin
  readln(f,t,a,b);
  add();
 end;
close(f);

a:=0;
for i:=1 to s do
 for n:=1 to s do
  a:=a+arr[i,n];

assign(f,'pentam2.out');
rewrite(f);
writeln(f,a);
close(f);
end.

Результат: 10/10

Задача по аналогии с предыдущей, поэтому пришлось дописать не много. =)