Am nevoie urgent de o rezolvare a acestei probleme!
Problem Cort
Fisier de intrare: cort.in
Fisier de iesire: cort.out
O curte dreptunghiular˘a de lungime N s, i l˘at, ime M (vom numi N linii s, i M coloane) este pavat˘a cu dale
p˘atrate de dimensiune 1. Dalele au dou˘a culori, sunt albe sau negre (vom codifica dalele albe cu 0 s, i
dalele negre cu 1). Dalele negre sunt fabricate dintr-un material mult mai rezistent decˆat dalele albe, iar
Ionel ar vrea sa monteze un cort de suprafat,˘a maxim˘a sub care s˘a fie doar dale negre. El s,tie de asemenea
c˘a exist˘a doar corturi dreptunghiulare s, i p˘atrate, de orice dimensiune. Din motive tehnice, Ionel poate
s˘a fac˘a doar urm˘atoarele operat, ii cu dalele din curte:
• s˘a schimbe ˆıntre ele oricˆate dale de pe aceeas, i linie;
• s˘a schimbe de oricate ori dores,te o linie ˆıntreag˘a cu alt˘a linie tot ˆıntreag˘a;
Cerinta
Scriet¸i un program care rezolv˘a urm˘atoarele dou˘a cerint¸e:
1. Afis,eaz˘a num˘arul maxim de dale negre care s-ar putea obt, ine pe o coloan˘a dup˘a rearanjare;
2. Afis,eaz˘a aria maxim˘a a cortului ce poate fi amplasat doar pe dale negre.
Date de intrare
Fis, ierul de intrare cort.in cont, ine pe prima linie un num˘ar natural C reprezentˆand cerint,a din problem˘a
care trebuie rezolvat˘a (1 sau 2). A doua linie din fis, ier cont, ine dou˘a numere naturale N s, i M, reprezentˆand
lungimea, respectiv l˘at, imea curt, ii. Pe fiecare dintre urm˘atoarele N linii se g˘asesc cˆate M valori de 0 sau
1, acestea indicˆand culoarea dalei de pe acea pozit, ie.
Date de iesire
Dac˘a C = 1, fi¸sierul de ie¸sire cort.out va cont¸ine un num˘ar reprezentˆand r˘aspunsul la cerint,a 1.
Dac˘a C = 2, fi¸sierul de ie¸sire cort.out va cont¸ine un num˘ar reprezentˆand r˘aspunsul la cerint,a 2.
Restrictii
• 1 ≤ N ≤ M ≤ 1000
• Exist˘a cel put, in o dal˘a neagr˘a
• Pentru rezolvarea corect˘a a cerint¸ei 1 se acord˘a 25 de puncte; pentru rezolvarea corect˘a a cerint,ei
2 se acord˘a 75 de puncte.
Exemple
cort.in cort.out
1
6 5
1 0 1 0 1
1 1 1 1 0
1 0 0 0 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
4
2
6 5
1 0 1 0 1
1 1 1 1 0
1 0 0 0 0
0 0 0 0 0
0 1 1 1 1
0 0 0 0 0
9
Explicatii:
Pentru primul exemplu, cerinta deste 1. Se pot rearanja sub urmatoarea form˘a:
1 1 1 0 0
1 1 1 1 0
1 0 0 0 0
1 1 1 0 0
0 0 0 0 0
0 0 0 0 0
Pe coloana 1 exist˘a 4 dale negre.
Pentru al doilea exemplu, cerint¸a este 2. Se pot rearanja sub urm˘atoarea form˘a:
1 1 1 1 0
1 1 1 1 0
1 1 1 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Se formeaz˘a o zon˘a de arie 9.
Dau coroana!
Răspunsuri la întrebare
Răspuns:
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int Problema_1(vector<vector<int>> matrix,int n)
{
int negre=0;
for (int i = 0; i < n; i++)
if (matrix[i][0] == 1)
negre++;
return negre;
}
int Problema_2(vector<vector<int>> matrix, int n, int m)
{
int aria = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if ((matrix[i][j] != 0)&&((i+1)*(j+1)>aria))
{
aria = (i + 1) * (j + 1);
}
return aria;
}
int main() {
int c, n, m, a;
fstream f("cort.in");
ofstream out("cort.out");
f >> c >> n >> m;
vector<vector<int> > matrix;
if ((n < 0) || (m > 1000))
return -1;
for (int i = 0; i < n; i++) {
vector<int> v;
for (int j = 0; j < m; j++)
{
f >> a;
v.push_back(a);
}
matrix.push_back(v);
}
if (matrix[0][0] == 0)
return -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m - 1; j++)
for (int k = j + 1; k < m; k++)
if ((matrix[i][j] == 0) && (matrix[i][k] == 1))
{
swap(matrix[i][j], matrix[i][k]);
k = m;
}
for (int j = 0; j < m; j++)
for (int i = 0; i < n - 1; i++)
for (int k = i + 1; k < n; k++)
if ((matrix[i][j] == 0) && (matrix[k][j] == 1))
{
for (int l = 0; l < m; l++)
swap(matrix[i][j], matrix[k][j]);
k = n;
}
if (c == 1)
out << Problema_1(matrix, n);
else
if (c == 2)
out << Problema_2(matrix, n, m);
}
La restrictie ai 1<=n<=m<1000
Exemplul nu indeplineste conditia deoare n=6 si m=5 => n>m deci nu am pus restrictia asta;
Daca vrei o poti adauga in primul if.