a fost răspuns

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ăspuns :

ElenaSFask

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.

Ask Alte intrebari