Leneşul este un animal foarte leneş. El se deplasează numai în linie dreaptă, dar face din când în când câte un popas. În această problemă leneşul trebuie să traverseze de la nord la sud şi înapoi un teren reprezentat de o matrice de dimensiuni M×N cu valori numere naturale. Valorile reprezintă efortul cerut pentru traversarea zonei respective. Leneşul va alege o coloană pentru traversarea matricei, iar pentru popasuri, în număr de k1, va alege zone alăturate drumului din coloana din stânga sau cea din dreapta. În cazul în care se va întoarce va proceda la fel, dar va face k2 popasuri. Regulile problemei cer ca cele două drumuri să nu aibă zone comune.
Cerințe
Cunoscând dimensiunile M, N ale terenului, numărul de popasuri k1, k2 și efortul pentru traversarea fiecărei zone a terenului, să se determine:
- Efortul minim de parcurgere a terenului de la Nord la Sud, folosind
k1popasuri. - Efortul minim de parcurgere a terenului de la Nord la Sud și înapoi de la Sud la Nord, folosind
k1popasuri la deplasarea Nord – Sud, respectivk2popasuri la deplasarea Sud – Nord.
Date de intrare
Fișierul de intrare lenes.in conține:
- Pe prima linie un număr natural
preprezentând cerința de rezolvare. Pentru toate testele de intrare numărulppoate avea doar valoarea1sau2. - Pe linia a doua sunt
4numere naturaleM,N,k1,k2, separate prin câte un spațiu cu semnificaţia de mai sus. - Pe următoarele
Mlinii se găsesc câteNnumere naturale separate prin câte un spațiu, reprezentând eforturile de traversare a fiecărei zone a terenului.
Date de ieșire
Dacă valoarea lui p este 1, se va rezolva numai cerința 1. În acest caz fişierul lenes.out va conţine un singur număr natural reprezentând efortul minim necesar pentru traversarea terenului în condiţiile date de la Nord la Sud.
Dacă valoarea lui p este 2, se va rezolva numai cerința 2. În acest caz fişierul lenes.out va conţine un singur număr natural reprezentând efortul minim necesar pentru traversarea terenului în condiţiile date în ambele sensuri de la Nord la Sud și de la Sud la Nord.
Restricții și precizări
3 ≤ M, N ≤ 5000 ≤ k1, k2 ≤ M- Valorile din matrice sunt numere naturale din intervalul
[1, 1000]. - Leneșul poate să facă popasuri pe aceeaşi linie în ambele celule din stânga şi din dreapta coloanei parcurse.
- Deplasarea între ultima zonă a drumului parcurs de la Nord la Sud şi prima zonă a drumului parcurs de la Sud la Nord la întoarcere se face cu efort
0.
Exemplul 1
lenes.in
1 4 7 2 3 99 1 33 9 2 4 7 99 1 44 8 1 2 3 98 1 55 8 2 3 2 97 1 66 4 3 2 1
lenes.out
12
Explicație
p = 1
Leneșul traversează terenul de la Nord la Sud pe coloana a 5-a cu popas în zonele (2, 6) și (4, 6).
Atenție! Pentru acest test se rezolvă doar cerința 1.
Exemplul 2
lenes.in
2 4 7 3 2 99 1 33 9 2 4 7 99 1 44 8 1 2 3 98 1 55 8 2 2 2 97 1 66 4 3 2 1
lenes.out
35
Explicație
p = 2
Leneșul traversează terenul de la Nord la Sud pe coloana a 7-a cu popasuri în zonele (3, 6), (1, 6), (4, 6), iar de la Sud la Nord pe coloana a 5 – a, cu popas în zonele (4, 4) și (2, 6).
Atenție! Pentru acest test se rezolvă doar cerința 2.
Exemplul 3
lenes.in
2 3 7 2 2 2 1 33 9 99 4 7 1 1 44 9 99 2 3 2 1 55 9 99 2 2
lenes.out
19
Explicație
p = 2
Leneșul traversează terenul de la Nord la Sud pe coloana a 6-a cu popasuri în zonele (2, 7), (3, 7), iar de la Sud la Nord pe coloana a 2 – a, cu popasuri în zonele (3, 1) și (2, 1). Efortul de deplasare între zonele (3, 6) și (3, 2) este nul.
Atenție! Pentru acest test se rezolvă doar cerința 2.
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 Lenes:
/**
* Problema: Lenes O(n^2)
* Stud. Popescu Silviu-Emil
* Automatica si Calculatoare
* Facultatea Politehnica Bucurest
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMax 1010
#define VMax 1010
#define oo 0x3f3f3f3f
using namespace std;
const char IN[] = "lenes.in", OUT[] = "lenes.out";
int Case, N, M, k1, k2;
int Mat[NMax][NMax];
int Sum[NMax], V[NMax], left[NMax], right[NMax];
int get_line_sum( int lin, int k, bool up = true, bool down = true ) {
int res = Sum[lin];
static int v[VMax];
memset(v, 0, sizeof(v));
for ( int i = 1; i <= M; ++ i ) {
if ( up )
++ v[ Mat[lin - 1][i] ];
if ( down )
++ v[ Mat[lin + 1][i] ];
}
for ( int i = 0; i < VMax && k ; ++ i )
if ( k >= v[i] ) {
res += i * v[i];
k -= v[i];
} else if ( v[i] ) {
res += k * i;
k = 0;
}
return res;
}
int case1() {
int ret = get_line_sum(1, k1);
for ( int i = 1; i <= N; ++ i )
ret = min( ret, get_line_sum(i, k1));
return ret;
}
int case2() {
int ret = oo;
for ( int i = 1; i <= N; ++ i )
V[i] = get_line_sum(i, k2);
left[1] = V[1];
for ( int i = 2; i <= N; ++ i )
left[i] = min(V[i], left[i - 1]);
right[N] = V[N];
for ( int i = N - 1; i > 0; -- i )
right[i] = min(V[i], right[i + 1]);
// computing distant lines
for ( int i = 1; i <= N; ++ i ) {
int r = get_line_sum(i, k1);
int other = oo;
if ( i > 3 ) other = min(other, left[i - 3]);
if ( i < N - 2) other = min(other, right[i + 3]);
ret = min(ret, r + other);
}
// computing adiacent lines
for ( int i = 1; i < N; ++ i ) {
int r1 = get_line_sum(i, k1 , true, false);
int r2 = get_line_sum(i + 1, k2, false, true);
ret = min( ret, r1 + r2 );
r1 = get_line_sum(i, k2 , true, false);
r2 = get_line_sum(i + 1, k1, false, true);
ret = min( ret, r1 + r2 );
}
//fprintf(stderr, "%d
", ret);
// computing common margin lines
bool parity = true;
for ( int i = 1; i < N - 1; ++ i ) {
int sum = Sum[i] + Sum[i + 2];
int up = i - 1;
int mid = i + 1;
int down = i + 3;
int index_up = 1;
int index_down = 1;
for ( int j = 1; j <= M && j <= k1 + k2; ++ j )
sum += Mat[mid][j];
// adding extra elements
for ( int j = M + 1; j <= k1 + k2; ++ j ) {
if ( index_up <= k1 && Mat[up][index_up] <= Mat[down][index_down] || index_down > k2 ) {
sum += Mat[up][index_up];
++ index_up;
} else {
sum += Mat[down][index_down];
++ index_down;
}
}
ret = min(ret, sum);
//fprintf(stderr, "begining with: (%d, %d, %d)
", index_up - 1, min(M, k1 + k2), index_down - 1);
for ( int j = min(M, k1 + k2); j > 0; -- j ) {
sum -= Mat[mid][j];
if ( index_up <= k1 && Mat[up][index_up] <= Mat[down][index_down] || index_down > k2 ) {
sum += Mat[up][index_up];
++ index_up;
} else {
sum += Mat[down][index_down];
++ index_down;
}
ret = min( ret, sum );
if ( ret == sum ) {
//fprintf(stderr, "(up: %d, mid: %d, down: %d -> %d
", index_up - 1, j - 1, index_down - 1, ret);
}
}
if ( parity ) {
parity = false;
-- i;
} else {
parity = true;
}
swap( k1, k2 );
}
return ret;
}
int (*Work[])() = { case1, case2 };
int main() {
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
scanf("%d%d%d%d%d", &Case, &N, &M, &k1, &k2);
for ( int i = 1; i <= N; ++ i)
for ( int j = 1; j <= M; ++ j )
scanf("%d", &Mat[j][i]);
swap(N, M);
for ( int i = 1; i <= N; ++ i )
for ( int j = 1; j <= M; ++ j )
Sum[i] += Mat[i][j];
for ( int i = 1; i <= M; ++ i )
Mat[0][i] = Mat[N + 1][i] = VMax - 1;
for ( int i = 1; i <= N; ++ i )
sort( Mat[i] + 1, Mat[i] + M + 1);
printf("%d
", Work[Case - 1]());
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 #1189 Lenes
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1189 Lenes 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!