Matca cea tânără a decis să părăsească stupul şi să îşi facă propria familie de albine, lucru nu tocmai uşor. Ea, împreună cu albinele sale trebuie să meargă din floare în floare până la marginea plantaţiei. Plantaţia are formă dreptunghiulară cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M). În fiecare punct este o floare. Florile sunt codificate cu 0 sau 1, cele codificate cu 0 putând fi ocupate doar de matcă, cele cu valoarea 1 doar de câte o albină. Roiul de albine pleacă de la marginea stângă a plantaţiei (coloana 1) şi trebuie să ajungă în marginea din dreapta (coloana M). La un pas, toate albinele (inclusiv matca) trebuie să se afle pe poziţii consecutive pe aceeaşi coloană. La pasul următor ele se pot deplasa doar pe coloana următoare, dar tot pe poziţii vecine (eventual îşi pot schimba ordinea). Efortul depus pentru deplasarea de pe o coloană pe alta este egal cu diferenţa dintre prima linie ocupată de un membru al roiului de albine (matca sau albină) la pasul anterior şi prima linie ocupată de un membru al roiului albine (matca sau albină) după mutare.
Cerința
Determinaţi numărul maxim de membri ai roiului de albine (matcă + albine) care pot părăsi stupul pentru a traversa toată plantaţia în scopul formării unei noi familii. Determinaţi, de asemenea efortul total minim cu care matca poate traversa plantaţia cu numărul maxim de albine determinat.
Date de intrare
Prima linie a fişierului de intrare albine.in conţine două numere naturale N şi M separate printr-un spaţiu reprezentând numărul de linii, respectiv numărul de coloane ale plantaţiei.
Următoarele N linii conţin câte M numere din mulţimea {0,1}, separate prin câte un spaţiu, reprezentând codurile florilor de pe fiecare linie a plantaţiei.
Date de ieșire
Prima linie a fişierului de ieşire albine.out conţine 2 numere naturale separate printr-un spaţiu, reprezentând numărul maxim de membri ai familiei de albine (matcă + albine) care pot traversa plantaţia (inclusiv matca) şi costul minim al traversării plantaţiei.
Restricții și precizări
1<=N, M <=1000- Pentru
50%din teste1<=N, M <=300 - Un roi de albine este format dintr-o matcă şi
0sau mai multe albine. - Se garantează existenţa unui traseu.
- Matca poate parcurge plantaţia şi singură.
- Pentru rezolvarea corectă doar a primei cerinţe se acordă
30%din punctaj.
Exemplu
albine.in
5 3 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0
albine.out
3 0
Explicație
Numărul maxim de membri ai familiei de albine care pot traversa plantația este 3 (matca și 2 albine). O posibilitate de traversare a plantației cu cost 0 este evidențiată mai jos.
| 0 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
| 0 | 0 | 0 |
O altă posibilitate (nu şi singura) de a parcurge plantaţia ar fi fost ca grupul de 3 albine sa se aşeze pe prima coloană începând cu poziţia 3, pe coloana a 2–a începând cu poziţia 1, iar pe coloana a 3–a începând cu poziţia 2. În acest caz costul total ar fi fost 3. Această posibilitate este evidențiată mai jos:
| 0 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
| 0 | 0 | 0 |
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 Albine:
//Marius Nicoli O(n*m)
#include <cstdio>
using namespace std;
#define DIM 1002
#define INF 1<<30
int A[DIM][DIM];
int S[DIM][DIM];
int Prev[DIM][DIM];
int Next[DIM][DIM];
int Z[DIM][DIM];
int N, M, i, j, n1, max, min, k, cm;
int modul(int a) {
if (a >= 0)
return a;
return -a;
}
int main(){
FILE *f = fopen("albine.in","r");
FILE *g = fopen("albine.out","w");
fscanf(f,"%d %d", &N, &M);
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
fscanf(f,"%d",&A[i][j]);
fclose(f);
for (j = 1, min = N+3;j <= M;j++) {
for (i = 1, n1 = 0, max = 0;i<=N;i++) {
if (A[i][j] == 1) {
if (A[i-1][j])
A[i][j] = A[i-1][j] + 1;
else
A[i][j] = 0;
Z[i][j] = Z[i-1][j] + 1;
n1++;
} else {
A[i][j] = n1+1;
n1 = 0;
Z[i][j] = 0;
}
if (A[i][j]>max)
max = A[i][j];
}
if (max<min)
min = max;
}
for (i=1;i<=N;i++)
if (A[i][1] >= min && (Z[i][j] <= min - 1))
S[i][1] = 0;
else
S[i][1] = INF;
for (j=2;j<=M;j++) {
for (i=min;i<=N;i++){
if (A[i][j-1] >= min && (Z[i][j-1] <= min - 1))
Prev[i][j] = i;
else
Prev[i][j] = Prev[i-1][j];
}
for (i=N;i>=min;i--){
if (A[i][j-1] >= min && (Z[i][j-1] <= min - 1))
Next[i][j] = i;
else
Next[i][j] = Next[i+1][j];
}
}
for (j=2;j<=M;j++) {
for (i=min;i<=N;i++)
if (A[i][j] >= min && (Z[i][j] <= min - 1)) {
cm = INF;
if (Prev[i][j]!=0)
cm = S[Prev[i][j]][j-1] + modul(i-Prev[i][j]);
if (Next[i][j]!=0 && cm > S[Next[i][j]][j-1] + modul(i-Next[i][j]))
cm = S[Next[i][j]][j-1] + modul(i-Next[i][j]);
S[i][j] = cm;
} else S[i][j] = INF;
}
for (k=min, cm = INF; k<=N; k++)
if (S[k][M] < cm)
cm = S[k][M];
fprintf(g,"%d %d", min, cm);
fclose(g);
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 #720 Albine
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #720 Albine 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!