Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Problema ferestre  (Citit de 10985 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
cristib84
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« : Septembrie 22, 2017, 16:22:18 »

Avem N ferestre date prin coordonatele coltului stanga-sus si dreapta-jos: (x1,y1) si (x2,y2).
Stiind rezolutia ecranului X*Y si faptul ca toate ferestrele incap integral pe ecran(0 <= x1,x2 <= X si 0 <= y1,y2 <= Y), sa se afle care este numarul maxim de ferestre care se suprapun in oricare din regiunile ecranului.
Sa va afisa acest numar maxim de ferestre gasit in regiuni si suma ariilor ce contin acest maxim(nu se cer coordonatele regiunilor).

Observatii:
1) N < 10.000.000
2) X <= 1280 si Y <= 1024
3) N este in general foarte mare, si poate fi mai mare decat numarul de pixeli X*Y
4) Timpul de rulare permite doar complexitate O(N)
5) Memorie suficienta: 32MB

Intrare
N X Y
x11 y11 x12 y12
x21 y21 x22 y22
...
xn1 yn1 xn2 yn2

Iesire
MAX SUPRAFATA_MAX

Exemplu:
Intrare:
2 10 10
1 1 8 8
2 2 3 3
Iesire:
2 4

Pentru cele 2 ferestre(notate a si b pe vizualizare) ecranul arata asa:
A A A A A A A A o o
A B B A A A A A o o
A B B A A A A A o o
A A A A A A A A o o
A A A A A A A A o o
A A A A A A A A o o
A A A A A A A A o o
A A A A A A A A o o
o o o o o o o o o o
o o o o o o o o o o

Unde se vede clar ca regiunea maxima coincide cu fereastra B(deoarece fereastra A era sub ea) si are aria 4.

« Ultima modificare: Septembrie 29, 2017, 10:31:35 de către Cristi B » Memorat
cristib84
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #1 : Septembrie 29, 2017, 10:44:05 »

Problema ajutatoare:

Se da un fisier de lungime D si N comenzi de scriere in acest fisier. Comenzile sunt de forma: a b insemnand ca se vor schimba in fisier octetii incepand cu a(inclusiv) si terminand cu b(inclusiv).
Sa se afle MAX care este numarul maxim de schimbari a oricarui octet si cati octeti au fost schimbati de MAX ori.

Observatii:
1) D < 1000000
2) N < 10000000 (deci N poate fi mult mai mare decat D)
3) timpul de rulare permite doar complexitate O(n)
3) memorie suficienta: 16MB

Intrare:
N D
a1 b1
a2 b2
...
an bn

Iesire
MAX NR_OCTETI_MAX

Exemplu
Intrare
4 3
1 3
2 3
3 3
1 1

Iesire
3 1

Explicatii:
Fisierul este de 3 octeti [- - -]
comanda 1: [x x x]
comanda 2: [- x x]
comanda 3: [- - x]
comanda 4: [x - -]
Se observa ca octetul 3 s-a schimbat de 3 ori deci MAX=3 si NR_OCTETI_MAX = 1

Memorat
dnprx
Strain


Karma: 42
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #2 : Septembrie 29, 2017, 10:48:35 »

Ambele probleme se rezolvă cu șmenul lui Mars.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines