• 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][X]Imagine

0
  • Publicat de Andrei Avădănei
  • în Fără categorie
  • — 29 iun., 2009 at 10:42 am

Sa consideram o imagine alb-negru de dimensiune LxL pixeli. Un pixel poate fi alb (codificat cu valoarea 0) sau negru (codificat cu valoarea 1). Imaginile pot fi compresate in diverse moduri. Una dintre cele mai cunoscute scheme de compresie este urmatoarea:

1. Daca imaginea este formata atat din pixeli 1, cat si din pixeli 0, se retine valoarea 1, care indica faptul ca imaginea va fi partitionata in alte 4 subimagini, asa cum este descris la pasul 2. Altfel codificam intreaga imagine ca 00 sau 01 semnificand faptul ca intreaga imagine este formata numai din pixeli 0, respectiv numai din pixeli 1.
2. O imagine I este impartita in 4 subimagini A, B, C, D dupa cum este ilustrat in figura urmatoare:

I I I I I I        B B B A A A
I I I I I I        B B B A A A     
I I I I I I  =>    B B B A A A
I I I I I I        C C C D D D  
I I I I I I        C C C D D D
I I I I I I        C C C D D D

Apoi se aplica din nou pasul 1, pentru fiecare dintre cele 4 subimagini, in ordinea A, B, C, D.
Numarul de biti (cifre de 0 sau 1) obtinuti in urma compresiei reprezinta dimensiunea imaginii compresate.
Data fiind o imagine, sa se determine dimensiunea imaginii compresate.

Olimpiada Municipala de Informatica, Iasi 2005

Date de intrare

Fisierul de intrare imagine.in contine pe prima linie numarul natural L, reprezentand dimensiunea imaginii. Urmatoarele L linii contin imaginea codificata, fiecare linie continand exact L valori 0 sau 1 separate prin cate un spatiu.

Date de iesire
Fisierul de iesire imagine.out contine o singura linie pe care se afla un numar natural care reprezinta dimensiunea imaginii compresate.

Restrictie
1< =L<=240 Exemple
imagine.in

4
1 1 1 1
1 1 0 1
0 1 0 0
0 0 1 1

imagine.out

30

imagine.in

8
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

imagine.out

9

Explicatii
1. Compresia imaginii din exemplul 1 se realizeaza astfel:

1 1 1 1
1 1 0 1
0 1 0 0 =1   ( 0 1 )  ( 1 1 )  ( 0 0 )    ( 1 1 )
0 0 1 1         0 0      1 1     1 1         0 1 

=1 1(0)(0)(0)(1) 01 1(1)(0)(1)(0) 1(0)(1)(1)(1) =
=1 1 00 00 00 01 01 1 01 00 01 00 1 00 01 01 01

Deoarece dupa compresare sunt necesari 30 de biti, dimensiunea imaginii compresate este 30.
2. Compresia imaginii din exemplul 2 se realizeaza astfel:

0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1  = 1   ( 1 1 1 1 )  (  0 0 0 0 ) ( 1 1 1 1 ) ( 1 1 1 1 )
1 1 1 1 1 1 1 1          1 1 1 1        0 0 0 0     1 1 1 1      1 1 1 1
1 1 1 1 1 1 1 1          1 1 1 1        0 0 0 0     1 1 1 1      1 1 1 1
1 1 1 1 1 1 1 1          1 1 1 1        0 0 0 0     1 1 1 1      1 1 1 1

= 1 01 00 01 01
In acest caz dimensiunea imaginii compresate este 9.

Solutie oficiala :
Timp executie: Nu am reusit sa-l calculez
Memorie folosita : O(n^2)

Vom avea nevoie de o functie ce verifica daca o sub-imagine ce incepe la pozitia x1,y1 si se termina la x2,y2 are aceeasi culoare.Daca doar unul din pixelii respectivei imagini substrase este diferit se imparte imagine de lungime |x1-x2| si inaltime |y1-y2| in 4 cadrane si se aduna numarul de biti recursiv la solutie.

Solutie problema Imagine

Etichete: algoritmicaC++ImagineOJIOlimpiadaProbleme algoritmicăprobleme 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 [OJI][IX] Cartele
  • Articolul următor Windows 7 vandut pe stick-uri

  • 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
  • august 2022
    L Ma Mi J V S D
    1234567
    891011121314
    15161718192021
    22232425262728
    293031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • [OJI][X]Imagine
  • 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