Meseria de parchetar a devenit mai uşoară de când a apărut parchetul laminat. Acesta se livrează în plăci pătratice de câte 1 m² şi montarea lui este destul de uşoară. Gigel este convins că este suficient de priceput să facă această operaţie în propria locuinţă. El dispune de planul locuinţei şi a cumpărat o anumită cantitate reprezentând X m² de parchet laminat. Planul locuinţei este descris printr-un tablou bidimensional de dimensiuni N x M, fiecare element al tabloului reprezentând exact 1 m². Pereţii sunt reprezentaţi prin caracterul ‘P’ iar suprafeţele camerelor prin caracterul ‘S’ (spaţiu). În planul din figura următoare este descrisă o locuinţă cu 5 camere acestea având respectiv, suprafeţele de 10, 2, 1, 3, 5 m².

PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

Gigel nu este sigur de faptul că parchetul cumpărat îi ajunge. Din această cauză a hotărât iniţial să pună parchetul începând cu camera cea mai mare, apoi în următoarea, în ordinea descrescătoare a suprafeţei şi aşa mai departe, până în momentul în care parchetul rămas nu mai este suficient pentru acoperirea suprafeţei următoarei camere. Nu va lăsa neparchetată o cameră pentru a parcheta una cu o suprafaţă mai mică.

Gigel se mai gândeşte şi la posibilitatea de a acoperi complet un număr maxim de camere folosind întreaga cantitate de parchet.

Cerința

Fiind date N, M, X şi planul locuinţei să se determine:

1. numărul C de camere pe care a reuşit să le acopere Gigel şi numărul R de m² de parchet care îi rămân, procedând aşa cum a hotărât iniţial;
2. numărul de posibilităţi de parchetare a unui număr maxim de camere, folosind întreaga cantitate de parchet.

Date de intrare

Fișierul de intrare parchet.in conține pe prima linie un număr natural p reprezentând cerinţa care trebuie să fie rezolvată (1 sau 2). Linia a doua a fişierului de intrare conţine numerele naturale N şi M separate printr-un spaţiu. Pe linia a treia se află numărul natural X. Următoarele N linii conţin câte M caractere ‘P’ şi ‘S’ descriind planul locuinţei.

Date de ieșire

Dacă valoarea lui p este 1, atunci fişierul de ieşire parchet.out conţine pe prima linie două numere naturale C şi R separate printr-un spaţiu, reprezentând respectiv numărul de camere acoperite cu parchet şi cantitatea de parchet rămasă, exprimată în m². Dacă valoarea lui p este 2, atunci pe prima linie a fişierului de ieşire se va scrie numărul de posibilităţi de parchetare a unui număr maxim de camere folosind întreaga cantitate de parchet, respectiv valoarea 0 în cazul în care acest lucru nu este posibil.

Restricții și precizări

• 2 ≤ N, M ≤ 250
• În casă sunt maxim 20 de camere şi casa are pereţi spre exterior.
• Suprafaţa unei camere nu depăşeşte (N-2)*(M-2) m².
• Pentru rezolvarea corectă a cerinţei 1 se acordă 50% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 50% din punctaj.

Exemplul 1

parchet.in

1
7 9
19
PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

parchet.out

3 1

Explicație

Se va rezolva doar cerinţa 1.

Locuinţa are 5 camere având suprafeţele de 10, 2, 1, 3, 5 m². Pot fi parchetate complet 3 camere consumând 18 m~2~ = 10+5+3. Rămâne 1 m~2~ de parchet nefolosit.

Exemplul 2

parchet.in

2
7 9
19
PPPPPPPPP
PSSSPSPSP
PSSSPSPPP
PSSPPPPSP
PSPPSSPSP
PSPSSSPSP
PPPPPPPPP

parchet.out

1

Explicație

Se va rezolva doar cerinţa 2.

Dacă se aleg camerele cu suprafeţele 10, 1, 3, 5 va fi folosită întreaga suprafaţă de parchet. Există o singură posibilitate de a selecta un număr maxim de camere.

SOLUTIE

#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("parchet.in");
ofstream g("parchet.out");
int n,m,p,P,i,j,k,cate,numar;
char a[255][255];
int c[21],sum[21],nr[21],nrp,di[]={-1,0,1,0},dj[]={0,1,0,-1},cer;

void sterge(int i, int j)
{ int inou,jnou;
  cate++;
  a[i][j]='P';
  for(int t=0;t<4;t++)
  { inou=i+di[t];
    jnou=j+dj[t];
    if(a[inou][jnou]=='S')sterge(inou, jnou);
  }
}
void numara(int t)
{ for(int v=0;v<=1;v++)
   { nr[t]=nr[t-1]+v;
     sum[t]=sum[t-1]+v*c[t];
     if(sum[t]==P)
        if(nr[t]>numar) {numar=nr[t];cate=1;}
          else {if(nr[t]==numar) cate++;}
     else
        if(t<k && sum[t]<P) numara(t+1);
   }
}

int main()
{f>>cer>>n>>m>>P;
 for(i=0;i<n;i++)
 {f>>a[i];
  for(j=1;j<m-1;j++) if(a[i][j]=='S') nrp++;
 }
 if(nrp==(n-2)*(m-2))
    if(cer==1)
       {g<<1<<' ';
        if(P>=nrp) g<<P-nrp<<'\n';
          else g<<P<<'\n';
       }
     else
        if(P!=nrp) g<<0<<'\n';
         else g<<1<<'\n';

else
{
 for(i=1;i<n-1;i++)
    for(j=1;j<m-1;j++)
       if(a[i][j]=='S')
        {
         cate=0;
         sterge(i,j);
         c[++k]=cate;
        }
 sort(c+1,c+k+1);
 i=k; while(i>0 && p+c[i]<=P) {p=p+c[i]; i--;}
 if(cer==1)g<<k-i<<' '<<P-p<<'\n';
  else{
 cate=0;
 while(k>0 && c[k]>P) k--;
 numara(1);
 g<<cate<<'\n';}
}
 f.close();g.close();
 return 0;
}