Fişierul intrare/ieşire:civilizatie.in, civilizatie.outSursăONI 2016, clasa a 9-a
AutorMarcel DraganAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Civilizatie

În vremuri străvechi Pământul era locuit de către o civilizaţie neobişnuită condusă după reguli matematice foarte riguroase. Această civilizaţie era formată din mai multe oraşe stat asemeni oraşelor antice. Fiecare oraş s-a dezvoltat treptat pornind de la un singur cartier de formă pătrată cu suprafaţa de un hectar, în jurul căruia se adăugau în fiecare an cartiere de câte un hectar fiecare în felul următor: în primul an s-a format cartierul iniţial, în al doilea an oraşul s-a extins formând patru noi cartiere în toate cele patru puncte cardinale, în anul următor oraşul s-a extins cu 8 noi cartiere dispuse în jurul cartierelor deja formate, şi aşa mai departe, în fiecare an oraşul extinzându-se cu încă un rând de cartiere.

Cerinţe

1. Dimensiunea suprafeţei (în hectare) pe care ar ocupa-o după t ani, dacă nu ar întâlni nici un alt oraş şi nici nu ar ajunge la marginea hărţii.
2. Timpul scurs până când toate cele N oraşe şi-au încetat extinderea, începută din cartierele iniţiale ale căror coordonate se citesc din fişier, şi aria suprafeţei din hartă rămasă neocupată, exprimată în hectare

Date de intrare

Fişierul de intrare civilizatie.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, p poate avea doar valoarea 1 sau valoarea 2.
A doua linie a fişierului conţine două numere naturale x şi y reprezentând dimensiunile hărţii.
A treia linie a fişierului conţine numărul natural t.
A patra linie a fişierului conţine numărul natural N.
Pe următoarele N linii se găsesc câte două numere i şi j reprezentând coordonatele iniţiale ale celor N oraşe.

Date de ieşire

Dacă valoarea lui p este 1, atunci se va rezolva numai prima cerinţă.
În acest caz, în fişierul de ieşire civilizatie.out se va scrie un singur număr natural, reprezentând aria suprafeţei (în hectare) unui oraş după t ani, dacă nu ar întâlni nici un alt oraş şi nici nu ar ajunge la marginea hărţii.
Dacă valoarea lui p este 2 atunci, se va rezolva numai a doua cerinţă.
În acest caz, fişierul de ieşire va conţine pe prima linie un număr natural reprezentând aria suprafeţei din hartă rămasă neocupată după ce toate cele N oraşe şi-au încetat expansiunea, iar pe a doua linie un număr natural reprezentând timpul scurs până când ultimul oraş s-a oprit din expansiune.

Restricţii

  • 1 ≤ N ≤ 2.000
  • 1 ≤ x, y, t ≤ 100.000
  • Pentru 30% din teste se garantează faptul că x, y ≤ 500
  • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 80 de puncte.

Exemplu

civilizatie.incivilizatie.outExplicaţie
1
7 9
9
2
3 2
4 6
145
p = 1, în fişier se va scrie aria suprafeţei ce ar putea fi
ocupată de un oraş în timp de 9 ani.
Atenţie! Pentru acest test se rezolvă doar cerinţa 1).
civilizatie.incivilizatie.outExplicaţie
2
7 9
5
2
3 2
4 6
33
4
p=2, deci se rezolvă doar cerinţa 2
civilizatie.incivilizatie.outExplicaţie
2
10 10
5
3
2 2
2 4
3 2
97
1
p=2, deci se rezolvă doar cerinţa 2
În acest caz, cele 3 civilizaţii nu se vor putea extinde deloc, deci celelalte 97 de  hectare rămân neocupate.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?