ŠIOM — Plokštelės su skylutėmis

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1997_2et_ploksteles_vyr.in

Rezultatų failas: lmio_1997_2et_ploksteles_vyr.out

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

Plokštelės su skylutėmis

Turime dvi vienodo dydžio kvadratines plokšteles. Jų kraštinės ilgis lygus $n$ . Plokštelės padalytos į $n\\timesn$ vienodų kvadratėlių. Kai kurie kvadratėliai iškirpti – vietoj jų yra kvadratinės skylutės. Pirmojoje plokštelėje yra $s_1$ , antrojoje – $s_2$ skylučių.

Užduotis

Parašykite algoritmą, kuris nustatytų, ar galima plokšteles uždėti vieną ant kitos taip, kad nesimatytų nė vienos skylutės. Jei negalima, reikia rasti, kiek mažiausiai skylučių matysis. Plokšteles galima visaip sukioti ir vartyti (bet uždėjus plokšteles vieną ant kitos, jų kraštai turi sutapti).

Pradiniai duomenys

Pradiniai duomenys: pirmoje eilutėje plokštelių kraštinės ilgis $n$ , antroje eilutėje – skylučių skaičiai pirmojoje ir antrojoje plokštelėse: $s_1$ ir $s_2$ . Tolesnėse $s_1$ eilutėse įrašytos pirmosios plokštelės skylučių koordinatės, likusiose $s_2$ eilutėse – antrosios plokštelės skylučių koordinatės.

Rezultatai

Rezultatas – mažiausias galimas matomų skylučių skaičius.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
3 3 2 1 1 2 2 1 3 1 1 2 2	1	Nepavyksta uždengti viduriniosios skylutės.

Ribojimai