25535번 - IZAZOV 서브태스크점수다국어

Mirko je na ulici pronašao ploču koja se sastoji od R × S polja (jediničnih kvadrata) koji su raspoređeni u R redaka i S stupaca. U trenutku kada je Mirko pronašao ploču, sva su njena polja bila ispunjena bijelom bojom. Mirko je odlučio neka polja obojiti crnom bojom. Nakon što je to napravio, ploču je poslao svom prijatelju Slavku zajedno sa sljedećom porukom:

“Dragi Slavko, izazivam te da pronađeš što manji broj pravokutnika koji će prekriti sva crna polja. Pritom nijedno bijelo polje ne smije biti prekriveno pravokutnikom, nijedno crno polje ne smije biti prekriveno s dva ili više pravokutnika te nijedan pravokutnik ne smije izlaziti izvan ploče.”

Kao što vjerojatno već pretpostavljate, Slavko nije dorastao izazovu pa je zamolio vas za pomoć.

U prvom su retku prirodni brojevi R i S koji predstavljaju dimenzije Mirkove ploče.

U svakom od sljedećih R redaka nalazi se po S znakova koji predstavljaju polja Mirkove ploče. Preciznije, znak ‘B’ označava bijelo polje, a znak ‘C’ označava crno polje.

U svakom od R redaka izlaza potrebno je ispisati po S brojeva odvojenih razmakom koji predstavljaju rješenje Mirkova izazova.

Polja koja su prekrivena prvim pravokutnikom potrebno je u ispisu označiti brojem 1, polja koja su prekrivena drugim pravokutnikom potrebno je označiti brojem 2, i tako dalje sve do posljednjeg, N-tog pravokutnika čija se prekrivena polja označavaju brojem N. Polja koja nisu prekrivena nijednim pravokutnikom, odnosno bijela polja, potrebno je označiti brojem 0.

Testni primjeri na kojima vaše rješenje prekrši neki od uvjeta iz teksta zadatka bodovat će se s 0 bodova.

Testni primjeri na kojima vaše rješenje ispravno prekrije sva crna polja, ali pritom ne koristi minimalan broj pravokutnika bodovat će se s

0.75 · (A / B)¹⁰ · X

bodova, pri čemu A označava optimalan broj pravokutnika, B označava broj pravokutnika u vašem rješenju, a X označava broj bodova koje nosi spomenuti test podatak.

Naravno, testni primjeri na kojima vaše rješenje ispravno prekrije sva crna polja koristeći optimalan broj pravokutnika donijet će vam sve predviđene bodove.