Candale Silviu (silviu) 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 m2 ş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 m2 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 m2. 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 m2.
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:
- numărul
Cde camere pe care a reuşit să le acopere Gigel şi numărulRde m2 de parchet care îi rămân, procedând aşa cum a hotărât iniţial; - 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 m2. 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
20de camere şi casa are pereţi spre exterior. - Suprafaţa unei camere nu depăşeşte
(N-2)*(M-2)m2. - 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 m2. 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.