Afişează mesaje
|
Pagini: [1]
|
1
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Problema ferestre
|
: 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
|
|
|
2
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Problema ferestre
|
: 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.
|
|
|
|