Î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.
| Primul an | Al doilea an | Al treilea an | Al patrulea an | Al cincilea an |
 |
 |
 |
 |
 |
Extinderea unui oraş se opreşte când întâlnește un alt oraş sau dacă, deşi nu a întâlnit încă un alt oraş, ajunge la marginea hărţii pe oricare dintre cele patru puncte cardinale. Două oraşe se întâlnesc când suprafeţele ocupate de ele ajung să se atingă sau între cartierele marginale ale celor două orașe se mai află doar un hectar.
| Situaţii în care suprafeţele orașelor se ating | Situaţii în care între suprafeţele orașelor există un spaţiu de un hectar |
 |
 |
Cerințe
- Dimensiunea suprafeţei (în hectare) pe care ar ocupa-o după
tani, dacă nu ar întâlni nici un alt oraş şi nici nu ar ajunge la marginea hărţii. - Timpul scurs până când toate cele
Noraş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 două numere naturale, pe rânduri diferite, reprezentând aria suprafeţei din hartă rămasă neocupată după ce toate cele N oraşe şi-au încetat expansiunea şi, respectiv, timpul scurs până când ultimul oraş s-a oprit din expansiune.
Restricții și precizări
1 ≤ N ≤ 20001 ≤ 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.
Exemplul 1
civilizatie.in
1 7 9 9 2 3 2 4 6
civilizatie.out
145
Explicație
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).
Exemplul 2
civilizatie.in
2 7 9 5 2 3 2 4 6
civilizatie.out
33 4
Exemplul 3
civilizatie.in
2 10 10 5 3 2 2 2 4 3 2
civilizatie.out
97 1
Explicație
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.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Civilizatie:
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("civilizatie.in");
ofstream fout("civilizatie.out");
#define nrCiv 2001 // numarul maxim de civilizatii
int p // tipul de cerinta
,n // mumarul de civilizatii
,nx,ny // dimensiunile hartii
,x[nrCiv],y[nrCiv] // coordonatele initiale ale oraselor
,dxyMin[nrCiv] // timpul pana la atingerea marginilor
,dMin[nrCiv] // timpul pana la oprire
,difMin[nrCiv][nrCiv] // distata dintre oricare doua civilizatii
,difMin2[nrCiv][nrCiv] // timpul minim dintre oricare doua civilizatii
,lMin[nrCiv] // minimele pe linii
,jlMin[nrCiv]; // pozitia minimului pe linii
unsigned long long t // timpul pt cerinta 1
,ct[nrCiv]; // suprafata ocupata de orase
int main()
{
fin>>p>>nx>>ny>>t>>n;
if(p==1){
unsigned long long ct=ct+2*t*(t-1)+1;;
fout<<ct<<'\n';
}
else{
for(int i=1;i<=n;i++)
fin>>x[i]>>y[i];
// minime pana la margini
for(int i=1;i<=n;i++){
int dxMin=min(nx-x[i]+1,x[i]),dyMin=min(ny-y[i]+1,y[i]);
dxyMin[i]=min(dxMin,dyMin);
}
// calcul distantei initiale pana la celelalte civilizatii
for(int i=1;i<=n;i++){
lMin[i]=nx+ny;
for(int j=1;j<=n;j++){
difMin[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j])+1;
difMin2[i][j]=difMin[i][j]/2;
if(difMin2[i][j]<lMin[i] && i!=j){
lMin[i]=difMin2[i][j];jlMin[i]=j;
}
}
}
// selectare orase in ordinea opriri expansiunii
int nr=0;
while(nr<n)
{
// cautare minim
int mMin=nx+ny,iMin,jMin,im=0;
for(int i=1;i<=n;i++){
if(mMin>lMin[i] && !dMin[i]){
mMin=lMin[i];iMin=i;jMin=jlMin[i];im=0;
}
if(mMin>dxyMin[i] && !dMin[i]){
mMin=dxyMin[i];im=i;
}
}
// calcul timp de oprire oras selectat si ajustare timpi pentru celelalte
int i=iMin,j=jMin;
if(im!=0){
i=im;dMin[i]=dxyMin[i];
}
else {
if(dMin[i]){ // civilizatia i verificata deja
i=jMin;j=iMin;
}
dMin[i]=difMin2[i][j];
}
nr++;
lMin[i]=nx+ny;
for(int k=1;k<=n;k++) // pt toate elementele de pe col i
if(!dMin[k] || !dMin[i])
if(difMin2[k][i]!=dMin[i]){
difMin2[k][i]=difMin2[i][k]=difMin[k][i]-dMin[i];
if(difMin2[k][i]<lMin[i] && k!=i && (!dMin[k] || !dMin[i])){
lMin[i]=difMin2[k][i];jlMin[i]=k;
}
if(jlMin[k]==i){
lMin[k]=nx+ny;
for(int ik=1;ik<=n;ik++) // pt toate elementele de pe linia k
if(difMin2[k][ik]<lMin[k] && k!=ik ){
lMin[k]=difMin2[k][ik];jlMin[k]=ik;
}
}
}
}
// calcul suprafete
for(int i=1;i<=n;i++){
t=dMin[i];
ct[i]=2*t*(t-1)+1;
}
unsigned long long tot=0;
int dMax=0;
for(int i=1;i<=n;i++){
tot=tot+ct[i];
if(dMax<dMin[i])
dMax=dMin[i];
}
fout<<(unsigned long long)nx*ny-tot<<'\n';
fout<<dMax<<'\n';
}
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1672 Civilizatie
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1672 Civilizatie de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!