• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

[OJI][IX] Cartele

0
  • Publicat de Andrei Avădănei
  • în C/C++ · Probleme algoritmică
  • — 29 iun., 2009 at 10:27 am

In 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

Etichete: algoritmicaC++carteleOJIOlimpiadaprobleme informaticaprogramare

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Decesul lui Michael Jackson a blocat internetul
  • Articolul următor [OJI][X]Imagine

  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • mai 2022
    L Ma Mi J V S D
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • [OJI][IX] Cartele
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons