Page 159 - MATINF Nr. 1

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 159

Dimensiunile tijelor permit as , ezarea chiar s , i a tuturor pieselor, dac˘a acestea sunt decupate ˆın
celulele corespunz˘atoare tijelor. Fiecare pies˘a este prev˘azut˘a cu elemente speciale de sust , inere,

astfel c˘a dac˘a exist˘a N × N tije pe toat˘a suprafat , a suportului, iar o pies˘a este decupat˘a ˆın toate
celulele p˘atrate, atunci piesa se poate as , eza pe suport. Nu este permis˘a as , ezarea unei piese care
are mai multe celule decupate decˆat num˘arul tijelor. Cum Ionel este prea mic, neavˆand suficient˘a
ˆındemˆanare de a manevra piesele pentru a le introduce prin tijele de pe suport, ajutat , i-l s˘a le
as , eze, dac˘a este posibil.

Cerint , ˘a
Scriet , i un program care determin˘a care dintre piese pot fi as , ezate pe suport.

Date de intrare
Fis , ierul de intrare joc.in cont , ine pe prima linie dou˘a numere naturale N s , i P desp˘art , ite
printr-un spat , iu. N este dimensiunea suportului, precum s , i a pieselor, iar P reprezint˘a num˘arul
pieselor. Urmeaz˘a P + 1 blocuri de cˆate N linii fiecare. Primul bloc de N linii codific˘a suportul.
Valoarea 1 apare dac˘a suportul este prev˘azut cu tij˘a vertical˘a, iar valoarea 0 ˆın caz contrar.
Urm˘atoarele P blocuri de cˆate N linii codific˘a fiecare cˆate o pies˘a. Pe fiecare linie sunt cˆate
N valori ˆıntregi, desp˘art , ite printr-un singur spat , iu, valoarea 1 codific˘a partea decupat˘a, iar
valoarea 0 partea care nu este decupat˘a.

Date de ies , ire
ˆ
In fis , ierul de ies , ire joc.out se vor scrie P linii, cˆate o valoare pe linie. Pe linia i se va scrie
valoarea 1 dac˘a piesa i poate fi as , ezat˘a pe suport astfel ˆıncˆat tijele s˘a p˘atrund˘a prin port , iunile
decupate ale piesei s , i valoarea 0 ˆın caz contrar.
Restrict , ii s , i preciz˘ari

• 1 < N, C ≤ 50

Exemplu
joc.in joc.out Explicat , ie

3 2 1 Piesa 1 se potrives , te perfect suportu-
0 1 0 0 lui, dac˘a se rotes , te ˆın sens trigonome-
0 0 1 tric cu 90 de grade.
1 0 0 Piesa 2 nu se potrives , te suportului, in-
1 0 0 diferent de modul ˆın care se ˆıncearc˘a
0 0 1 as , ezarea sa prin tijele aflate pe suport.
0 1 0
0 0 1
0 0 1
0 1 0

Timp maxim de execut , ie: 1 secund˘a/test.

Memorie total˘a disponibil˘a 5 MB.

Cristina Constantinescu, Pites , ti (Dan Barbilian, 2018)