2017-SIO-neonke

Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Као што сте већ видели, за успешно одржавање другог дана СИО било је потребно отићи у Комисијски тајни подрум и прецизно активирати машину која ће заменити задатке између два дана. Пошто сте претходног дана успешно одредили начин на који је ово потребно урадити, чланови Комисије су успели да активирају машину, и други дан СИО може бити одржан.

Међутим, ова активација машине није била без последица. Наиме, Комисијски подрум је изузетно лоше осветљен, тако да је навигација била јако тешка, и одређени чланови Комисије су били повређени. Како се ускоро очекује посета ИЗС (Инспекције за одржавање Здравља и Сигурности™), Комисија је одлучила да прикладно осветли подрум неонским сијалицама (“неонкама”).

Подрум је представљен као матрица од \(N \times M\) поља. Неонка постављена на позицији \((x_n, y_n)\) је у могућности да осветли поља \((x, y)\) за која важи \(x_n - R \leq x \leq x_n + R\) и \(y_n - R \leq y \leq y_n + R\), где је \(R\) јачина светлости неонке. За ово поље такође мора важити да унутар правоугаоника одређеног координатама \((x, y)\) и \((x_n, y_n)\) нема ни једног зида!

На пример, ако је \(R = 3\), поља означена са 'S' би била осветљена неонком постављеном на позицију означену са 'N':

Због умањења бројности Комисије, ангажована је помоћ малог Перице, који је био одсутан јурећи научне конференције током целог овогодишњег циклуса такмичења. Како Перица нема времена да се ангажује, чак ни када је то најпотребније, одлучио је да наплати постављање сваке неонке са \(C\) динара, и ручно паљење сваке неонке са \(P\) динара. На срећу, није неопходно ручно упалити сваку неонку – уколико светлост од једне неонке захвати другу, она се онда сама пали. Можете сматрати да ће Перица палити неонке тако да је број ручних паљења минималан.

На вама је да одредите на које позиције у подруму треба поставити неонке, тако да се осветли што више његових поља. Комисија је одвојила ограничен буџет за малог Перицу – овај буџет не сме да се премаши!

Напомена

Ово је задатак са познатим улазом (output-only задатак). Вама су дати улазни фајлови (case-01.in, case-02.in, case-03.in, case-04.in), док ви треба да пошаљете само одговарајуће излазне фајлове за њих (case-01.out, case-02.out, case-03.out, case-04.out).

Опис улаза

У првом реду улазних фајлова налазе се три природна броја \(N\), \(M\) и \(R\) - висина и ширина плана подрума, и јачина светлости сваке неонке, редом. У другом реду налазе се три природна броја \(C\), \(P\) и \(B\): цена једне неонке, цена ручног паљења једне неонке, и укупан буџет доступан Комисији, редом. У преосталих \(N\) редова налази се по \(M\) карактера, који представљају план подрума, \({\bf Z}\), један по један ред, редом. Сваки карактер може бити '.', '#' или '-', тако да '.' представља слободно поље, док преостала два карактера представљају зидове.

Опис излаза

Ваши излазни фајлови треба да садрже позиције свих неонки које Комисија треба да купи: за сваку неонку, потребно је у засебном реду излаза приложити два цела броја \(X_i\) и \(Y_i\), који представљају позицију \(i\)-те неонке коју Комисија треба да купи. Обавезно мора да важи \(1 \leq X_i \leq N\), \(1 \leq Y_i \leq M\), и \({\bf Z}_{X_i, Y_i} = \text{'.'}\).

Пример 1

Улаз

Излаз

Објашњење примера

Уколико поставимо неонке на дате две позиције, онда ће осветљеност подрума бити следећа (са 'N' обележавамо позиције неонки, а са 'S' позиције које су осветљене):

Довољно је ручно упалити само једну од ове две неонке да би се обе упалиле. Стога је укупна утрошена цена за ово решење \(2 \times C + 1 \times P = 102\), што је унутар нашег буџета, тако да је решење коректно. Ово решење укупно осветљава \(35\) поља (и не представља оптимално решење!).

Бодовање

Ваше решење за неки од улаза ће се сматрати неважећим уколико је испуњен бар један од следећих услова: - излазни фајл садржи непаран број целих бројева; - излазни фајл садржи позицију која је изван ограничења датог плана; - излазни фајл садржи позицију на којој се налази зид; - излазни фајл садржи две исте позиције; - укупна цена постављања и ручног паљења неонки премашује задати буџет.

У супротном, нека је \(k\) укупан број поља које ваше решење осветљава. За сваки улаз дефинисане су константе \(A\) и \(B\) тако да: - Уколико важи \(k \geq B\), освајате 25 поена за тај улаз; - Уколико важи \(k \leq A\), освајате 0 поена за тај улаз; - Иначе, освајате \(\lfloor 25 \times \frac{k - A}{B - A}\rfloor\) поена за тај улаз.

Тестирање и експериментисање

На коришћење вам је дат програм са којим можете лакше да тестирате своје решење (Neonke.jar).

Покретањем овог програма из директоријума у коме се налазе и одговарајући case-??.in и case-??.out фајлови, моћи ћете да визуелизујете ваше решење за дате улазе, као и информације попут количине поља које сте осветлили и укупне цене коју сте потрошили.

Све неонке које се упале као последица једног ручног паљења ће унутар програма бити приказане истом бојом.