ŠIOM — Grioveliai

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1996_3e2_grioveliai.in

Rezultatų failas: lmio_1996_3e2_grioveliai.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Grioveliai

Per kvadratinės plokštelės centrą lygiagrečiai kraštinėms gali būti išskobtas vienas griovelis arba du vienas kitam statmeni grioveliai:

< insert image here >

Šiais grioveliais rieda rutuliukas.

Turime $n$ plokštelių su vienu grioveliu, $nn$ plokštelių su dviem grioveliais ir neribotą skaičių plokštelių be griovelių.

Iš plokštelių (panaudojus visas $n$ ir $nn$ plokšteles su grioveliais) reikia sudėti tokį mažiausią kvadratą, kad visi grioveliai susisiektų, t. y. jais visais be kliūčių galėtų riedėti rutuliukas.

Plokšteles su vienu grioveliu, konstruodami iš jų kvadratą, galime pasukti reikiama kryptimi (taip, kad jų griovelis eitų horizontaliai arba vertikaliai). Rutuliukas gali atsitrenkti tik į tuščią plokštelę.

Užduotis

Parašykite programą šiam uždaviniui išspręsti.

Pradiniai duomenys

Pradiniai duomenys – du skaičiai: $n$ ir $nn$ .

Rezultatai

Pirmoje eilutėje turi būti vienas skaičius – mažiausio kvadrato kraštinės ilgis, kitose eilutėse – plokštelių išdėstymas kvadratu (reikia pateikti tik bet kurį vieną išdėstymo variantą).

Minuso ženklu (-) žymima plokštelė su vienu grioveliu, kai ji dedama horizontaliai, raide I – plokštelė su vienu grioveliu, kai dedama vertikaliai, pliuso ženklu (+) – su dviem grioveliais, o tuščios plokštelės – nuliu (0).

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
4 1	3 0I0 -+- 0I0	Šis bei keletas kitų galimų sprendimų pateikti žemiau esančiuose paveikslėliuose.

Ribojimai

$0\\leqn\\leq100$

$0\\leqnn\\leq100$