La întâlnirea anuală a cârtițelor, la concursul pentru selecția noilor membri ai consiliului director, a fost propusă următoarea problemă:
De jur-împrejurul unui teren dreptunghiular împărțit în n*m celule de formă pătrată, cu aceeași arie, cârtițele au săpat galerii exterioare. Celulele aflate pe marginea terenului sunt numerotate consecutiv, de la 1 la 2*(n+m), începând din colțul din stânga-sus, ca în imaginea alăturată. În galeriile exterioare, pe marginea terenului, se află t cârtițe care sunt pregătite să sape galerii interioare. Cârtițele aflate pe latura de Nord a terenului se vor deplasa către Sud, cele care se află pe latura de la Est se vor deplasa către Vest, cele care se află pe latura de la Sud se vor deplasa către Nord, iar cele care se află pe latura de la Vest se vor deplasa către Est.
Cârtițele încep să sape în același timp. În fiecare oră, o cârtiță sapă într-o singură celulă a terenului.
O cârtiță se oprește dacă:
- ajunge într-o altă galerie interioară; ea nu sapă în aceasta, iar galeria ei se unește cu cea în care ajunge;
- în celula în care sapă, mai sapă și alte cârtițe, în aceeași oră; galeriile lor se unesc într-o singură galerie și toate aceste cârtițe se opresc;
- ajunge pe marginea terenului, în partea opusă celei din care a plecat, galeria săpată de ea până în acest moment comunicând acum cu galeria exterioară, în care ea nu sapă.
De exemplu, dacă pe marginea unui teren format din 7x5 celule, se află 5 cârtițe, în celulele 3, 8, 10, 19 și 23, atunci, după o oră, terenul are configurația din fig.1, după două ore, configurația din fig.2, după trei ore, configurația din fig.3 (ultima cârtiță ajunge în galeria primei cârtițe și primele două cârtițe sapă în aceeași celulă și apoi se opresc), după 4 ore, configurația din fig.4, după 5 ore, configurația din fig.5, când cele două cârtițe rămase sapă pe marginea terenului și apoi se opresc pentru că au ajuns în galeria exterioară (fig.6). Galeriile acestora nu se unesc pentru că niciuna dintre ele nu a intrat în galeria celeilalte și nici nu s-au întâlnit într-o celulă.
Cerința
Cunoscându-se numerele n, m, t și cele t celule exterioare în care se află cârtițele, să se determine:
1. numărul maxim de celule în care sapă o cârtiță până la oprirea tuturor cârtițelor;
2. numărul maxim de celule din care este formată o galerie interioară.
Date de intrare
Fișierul de intrare galerie.in conține pe prima linie una dintre valorile 1 sau 2 reprezentând cerinţa 1, dacă se cere determinarea numărului maxim de celule în care sapă o cârtiță până la oprirea tuturor cârtițelor, respectiv cerinţa 2, dacă se cere determinarea numărul maxim de celule din care este formată o galerie interioară.
Linia a doua conține, separate prin câte un spațiu, trei numere naturale: n, m (reprezentând dimensiunile terenului) și t (reprezentând numărul de cârtițe aflate în galeriile exterioare).
Linia a treia conţine cele t numere naturale separate prin câte un spațiu, reprezentând pozițiile celor t cârtițe.
Date de ieșire
Fișierul de ieșire galerie.out va conține pe prima o valoarea naturală reprezentând numărul maxim de celule în care sapă o cârtiță până la oprirea tuturor cârtițelor, dacă cerinţa a fost 1, respectiv un număr natural reprezentând numărul maxim de celule din care este formată o galerie interioară, dacă cerinţa a fost 2.
Restricții și precizări
3 ≤ n,m ≤ 200;1 ≤ t ≤ 2*(n+m);- Într-o celulă numerotată, exterioară terenului, se poate afla o singură cârtiță.
- Pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.
Exemplul 1
galerie.in
1 7 5 5 19 3 8 10 23
galerie.out
5
Explicație
Cârtița care pleacă din poziția 23 sapă în două celule; cârtițele care pleacă din pozițiile 3 și 8, sapă în 3 celule, iar celelalte două cârtițe în 5 celule.
Exemplul 2
galerie.in
2 7 5 5 19 3 8 10 23
galerie.out
7
Explicație
S-au format trei galerii interioare, două formate din câte 5 celule și o galerie interioară formată din 7 celule (fig.6).
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 Galerie:
#include <fstream>
#include <iostream>
#include <set>
using namespace std;
ifstream f("galerie.in");
ofstream g("galerie.out");
int n,m,t,k,x,i,pas,inou,jnou,a[205][205],di[]={-1,0,1,0},dj[]={0,1,0,-1},sapa_cineva;
struct cartita{int i,j,l,di,dj;}C[1000];
set<int> s;
set<int> sterse;
set<int>::iterator it;
set<int>::iterator it1;
int interior(int i, int j)
{ if(i*j==0)return 0;
if(i>n)return 0;
if(j>m)return 0;
return 1;
}
void uneste_galerii(int i,int j,int c1,int c2)
{ int k,i1,j1;
if(interior(i,j))
for(k=0;k<4;k++) {i1=i+di[k];j1=j+dj[k];
if(a[i1][j1]==c1) { a[i1][j1]=c2;
uneste_galerii(i1,j1,c1,c2);
}
}
}
int main()
{ f>>k>>n>>m>>t;
for(i=1;i<=t;i++)
{f>>x;
if(x<=m) {C[i].i=0;C[i].j=x;C[i].di=1;C[i].dj=0;}
else
if(x<=n+m) {C[i].i=x-m;C[i].j=m+1; C[i].di=0;C[i].dj=-1;}
else
if(x<=2*m+n){C[i].i=n+1;C[i].j=2*m+n+1-x;C[i].di=-1;C[i].dj=0;}
else {C[i].i=2*n+2*m+1-x;C[i].j=0;C[i].di=0;C[i].dj=1;}
s.insert(i);
}
for(i=1;i<=n;i++)a[i][0]=a[i][m+1]=-1;
for(i=1;i<=m;i++)a[0][i]=a[n+1][i]=-1;
while(!s.empty())
{ sapa_cineva=0;
sterse.clear();
for(it=s.begin();it != s.end(); it++)
{ i=*it;
inou=C[i].i+C[i].di;
jnou=C[i].j+C[i].dj;
x=a[inou][jnou];
if(x==0) {a[inou][jnou]=i;C[i].l++;C[i].i=inou;C[i].j=jnou;sapa_cineva=1;}
else
{ if(x!=-1)
{
uneste_galerii(inou,jnou,i,x);
C[x].l+=C[i].l;
if (x<i && a[inou+C[x].di][jnou+C[x].dj]!=x) sterse.insert(x);
}
sterse.insert(i);
}
}
for(it=sterse.begin();it != sterse.end(); it++)
{ i=*it;
if(s.count(i)!=0) s.erase(i);
}
if(sapa_cineva) pas++;
}
if(k==1) g<<pas<<'\n';
else
{ x=C[1].l;
for(i=2;i<=t;i++) if(C[i].l>x)x=C[i].l;
g<<x<<'\n';
}
f.close();g.close();
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 #1616 Galerie
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1616 Galerie 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!