[OJI][IX] Cartele
0In sediul unei firme se intra doar cu ajutorul cartelelor magnetice. De cate ori se schimba codurile de acces, cartelele trebuie formatate. Formatarea presupune imprimarea unui model prin magnetizare. Dispozitivul in care se introduc cartelele, numit cititor de cartele, verifica acest model. Toate cartelele au aceleasi dimensiuni, suprafata patrata si grosimea neglijabila. Cele doua fete plane ale unei cartele se impart fiecare in NxN celule patrate, identice ca dimensiuni. Prin formatare unele celule, marcate cu negru in exemplu, se magnetizeaza permitand radiatiei infrarosii sa treaca dintr-o parte in cealalta a cartelei. In interiorul cititorului de cartele se ilumineaza uniform una dintre fetele cartelei. De cealalta parte fasciculele de lumina care strabat cartela sunt analizate electronic. Pentru a permite accesul in cladire modelul imprimat pe cartela trebuie sa coincida exact cu modelul sablonului care memoreaza codul de intrare. Prin fanta dispozitivului nu se pot introduce mai multe cartele deodata. Cartela se poate introduce prin fanta cu oricare dintre muchii spre deschizatura fantei si cu oricare dintre cele doua fete orientate catre sablon. Dupa introducere cartela se dispune in plan paralel cu sablonul, lipit de acesta, astfel incat cele patru colturi ale cartelei se suprapun exact cu colturile sablonului. Modelele imprimate pe cele doua fete ale unei cartele sunt identice. Unei celule magnetizate ii corespunde pe fata opusa tot o celula magnetizata, iar unei celule nemagnetizate ii corespunde una nemagnetizata. O celula magnetizata este transparenta pentru radiatia infrarosie indiferent de fata care se ilumineaza.
Un angajat al firmei are mai multe cartele. Pe unele dintre acestea a fost imprimat noul cod de intrare, iar pe altele sunt coduri mai vechi. Pentru a afla care sunt cartelele care-i permit accesul in sediul firmei angajatul este nevoit sa le verifice pe toate, introducandu-le pe rand, in toate modurile pe care le considera necesare, in fanta cititorului de cartele.
OJI,2007
Cerinta
Scrieti un program care determina care dintre cartele permite accesul in sediul firmei.
Date de intrare
Fisierul de intrare cartele.in contine pe prima linie doua numere naturale N si C despartite printr-un spatiu. N este dimensiunea tablourilor care reprezinta modelul sablon si modelele cartelelelor. C reprezinta numarul de cartele. Urmeaza C+1 blocuri de cate N linii fiecare. Primul bloc de N linii codifica sablonul. Urmatoarele C blocuri de cate N linii codifica fiecare cate o cartela. Pe fiecare linie sunt cate N valori intregi, despartite printr-un singur spatiu. Celulelor magnetizate le corespunde valoarea 1, iar celorlalte, valoarea 0.
Date de iesire
In fisierul de iesire cartele.out se vor scrie C linii, cate o valoare pe linie. Pe linia i se va scrie valoarea 1 daca cartela i permite accesul in cladire si valoarea 0 in caz contrar.
Restrictii si precizari
1 < N, C <= 50
Exemplu
cartele.in
3 2
0 1 0
0 0 1
1 0 0
1 0 0
0 0 1
0 1 0
0 0 1
0 0 1
0 1 0
cartele.out
1
0
Explicatie
Datele de intrare corespund situatiei din figura. Cartela 1 se potriveste perfect sablonului, daca se roteste in sens trigonometric cu 90 de grade. Cartela 2 nu se potriveste sablonului, indiferent de modul in care se introduce in fanta.
Timp maxim de executie/test: 1 secunda
Solutie oficiala:
Timp executie : O(c*(n^2)),unde c este numarul de cartele iar n este dimensiunea matricei
Memorie folosita : O(2n*n),solutia originala a problemei avea O((c+1)n*n)
Solutie:
Vom citi intr-o matrice sablonul dupa care vom citi cartele valoare cu valoare si le testam in cele 4 pozitii : 0 grade,90 grade,180 grade,270 grade si oglindite la 0 grade,90 grade,180 grade si respectiv 270 grade.
Solutie problema Cartele
