| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Linna ehitatakse uut kaubanduskeskust, mille põhiplaan koosneb $N \times M$ ühikruudust. Ruut $(1, 1)$ on keskuse loodenurgas ja ruut $(N, M)$ kagunurgas. Kuigi keskust alles ehitatakse, on turundajad juba hinnanud, et ruutu $(i, j)$ hakkab päevas külastama $A_{ij}$ ostjat.
Keskuses tahavad oma poed avada $K$ firmat, mis on nummerdatud 1ドル \ldots K$. Iga pood võib paikneda ühes või mitmes ruudus, aga peab olema 4-sidus: poe igast ruudust peab pääsema poe igasse teise ruutu, läbides teel ainult selle poe ruute ja astudes igal sammul ühest ruudust teise üle nende ühise serva. Loomulikult ei saa ühes ruudus olla mitut poodi. Lisaks ei luba ohutusnõuded teha keskusse poodi, mis on suurem kui $S$ ruutu.
Kaubanduskeskuse juhataja tahab pakkuda poodidele pindu nii, et nende alla jäävate ruutude külastatavuste summa oleks võimalikult suur (vähemkülastatavad ruudud jäävad koridorideks ja muudeks abiruumideks). Aita turundusjuhil koostada võimalikult hea pakkumine.
Sisendfaili esimesel real on testi number $T$.
Faili teisel real on neli täisarvu $N,ドル $M,ドル $K$ ja $S$: keskuse laius ja pikkus, poodide arv ja poe maksimaalne suurus.
Järgmisel $N$ real on igaühel täpselt $M$ täisarvu $A_{ij}$: keskuse ruutude külastatavused.
Faili viimasel real on täisarv $Y$: poodide summaarne külastatavus žürii lahenduses.
Väljundfaili esimesele reale väljastada testi number $T$.
Järgmisele $N$ reale väljastada igaühele täpselt $M$ täisarvu $B_{ij}$ (0ドル \le B_{ij} \le K$), kus $B_{ij} > 0$ näitab vastaval ruudul asuva poe omaniku numbrit ja $B_{ij} = 0$ tähistab vabaks jäävat ruutu.
Selles ülesandes on (testimiskeskkona kaudu) antud 10 sisendfaili (input_001.txt kuni input_010.txt) ja lahendusena tuleb esitada neile vastavad väljundfailid (output_001.txt kuni output_010.txt). Programmi esitamine pole vajalik ja seda ei hinnata.
Väljundfail, mille vorming või milles kirjeldatav poodide paigutus ei vasta ülesande tingimustele, teenib 0 punkti. Korrektne fail teenib $$ \min\left( 10, 10 \cdot \left(\frac{X}{Y}\right)^2 \right) $$ punkti, kus $X$ on poodide summaarne külastatavus failis kirjeldatud paigutuse korral ja $Y$ on summaarne külastatavus žürii lahenduses.
0 4 9 2 8 1 7 6 4 2 1 2 1 2 2 5 2 3 1 2 5 3 7 1 8 5 4 2 1 5 1 8 1 2 3 1 2 2 1 2 5 79
0 0 1 1 1 0 0 2 0 0 0 1 0 1 0 2 2 2 2 0 1 1 1 0 0 2 0 2 0 0 0 0 0 0 0 0 2
Poodide summaarne külastatavus on $(7 + 6 + 4 + 5 + 3 + 8 + 5 + 4) + (2 + 2 + 5 + 3 + 7 + 5 + 8 + 5) = 42 + 37 = 79$.