Velika Božićna Patuljasta Fotografija

Djed Božićnjak želi napraviti božićnu fotografiju za uspomenu. Slikaju se svi patuljci točnije njih 1000, posloženih u 10 redova po 100 patuljaka. Djedica je jako sentimentalan i želi sačuvati svaki dragocjeni trenutak pa je ovakva slika idealna.

Patuljci su jako društveni, ali i osjetljivi. Svaki patuljak ima mišljenje o drugom patuljku. Neki se obožavaju (100), a neki se ne podnose uopće(0). Mišljenje o drugom patuljku je u biti skala [0, 100].

Tvoja zadaća je posložiti patuljke u 10×100 panoramu tako da budu što sretniji sa svojim najbližim susjedima.

Ulazni podaci

1000 redaka gdje svaki redak predstavlja mišljenja jednog patuljka o svim ostalim patuljcima
Svaki redak ima točno 1000 cijelih brojeva od 0 do 100, odvojenih zarezom (bez razmaka)
Broj na poziciji (i, j) = koliko i-ti patuljak voli j-tog patuljka
Dijagonala je uvijek - ( Patuljak nema mišljenje o sebi)
Matrica nije nužno simetrična ( i-ti patuljak može voljeti j-tog patuljka (100), ali j-ti patuljak ne voli i-tog (0))

Izlazni podaci

Jedan jedini redak sa točno 1000 brojeva od 1 do 1000, odvojenih zarezom (bez razmaka i bez novog retka na kraju). Svaki patuljak može i mora se pojaviti točno jednom tj. svi brojevi 1–1000 moraju se pojaviti točno jednom. Prvih 100 brojeva u redku predstavlja prvi redak fotografije, drugih 100 brojeva predstavalja drugi redak fotografije itd.

Primjer izlaza: 542,883,121,76,997,234,567,890,12,445,378,255,901,666,123,...,999

Bodovanje

Bodovanje se sastoji od dva dijela:

Ukupna sreća
Minimalna sreća

Bodovna skala je [0, 100 000].
Ukupan broj bodova = Ukupna sreća + Minimalna sreća

Ukupna sreća (80% bodova)

Svaki patuljak gleda samo svoje orto-susjede (gore, dolje, lijevo, desno):

Sreća pojedinog patuljka = zbroj sreća prema svim njegovim orto-susjedima
Ukupna sreća = zbroj sreća svih patuljaka

Teoretski maksimum: 378 000 (svi susjedi 100)
Teoretski minimum: 0 (svi susjedi 0)
Bodovi = ( tvoja_ukupna_sreća ) / 378 000 × 80 000

-> ako svaki patuljak mrzi sve svoje susjede (svi susjedi 0) = 0 bodova za ovaj dio
-> ako svaki patuljak jako voli sve svoje susjede (svi susjedi 100) = 80 000 bodova za ovaj dio

Minimalna sreća (20% bodova)

Nesreća pojedinog patuljka = najmanja sreća prema bilo kojem orto-susjedu
Minimalna sreća = najmanja sreća bilo kojeg patuljka prema orto-susjedima na slici

Teoretski maksimum: 100 (svi susjedi 100)
Teoretski minimum: 0
Bodovi = (tvoja_minimalna_sreća) / 100 × 20 000

-> ako postoji patuljak koji ima susjeda kojeg mrzi (jedan od njegov susjeda ima voljenost 0) = 0 bodova za ovaj dio
-> ako postoji patuljak koji jako voli sve svoje susjede (svi susjedi 100) = 20 000 bodova za ovaj dio

Primjer

Ovo je pojednostavljeni primjer sa 9 patuljaka, slika sa 3 reda po 3 patuljaka.

Ulaz

-,39,80,24,76,45,33,32,53
0,-,73,51,67,57,41,57,43
33,53,-,77,75,40,76,46,18
33,55,62,-,53,41,22,37,65
58,26,51,37,-,64,63,30,47
50,43,48,64,87,-,57,55,29
67,41,23,32,52,43,-,58,40
84,67,53,29,26,23,53,-,4
74,77,58,54,61,28,38,87,-

Izlaz

5,2,6,3,1,7,8,4,9

Ovo u prijevodu označava:

red: 5 2 6
red: 3 1 7
red: 8 4 9

Patuljak 5 je u gornjem lijevom kutu. Njegovi susjedi su patuljak 2 desno i patuljak 3 ispod. Njegova sreća je zbroj koliko voli patuljka 2 i koliko voli patuljka 3. U matrici to su brojevi na pozicijama (5,2) i (5,3), odnosno 26 i 51. Sreća patuljka 5 je 26 + 51 = 77. Njegova minimalna sreća prema susjedima je manji od ta dva broja, znači 26.

Za patuljka 2 koji je gore u sredini susjedi su patuljak 5 lijevo, patuljak 6 desno i patuljak 1 dolje. Njegova sreća je zbroj brojeva (2,5), (2,6) i (2,1) odnosno 67 + 57 + 0 = 124. Njegova minimalna sreća prema susjedima je najmanji od ta tri broja, ovdje 0.

Patuljak 1 je u sredini slike. Njegovi susjedi su patuljak 2 gore, patuljak 4 dolje, patuljak 3 lijevo i patuljak 7 desno. Njegova sreća je zbroj brojeva (1,2), (1,4), (1,3) i (1,7), odnosno 39 + 24 + 80 + 33 = 176. Njegova minimalna sreća prema susjedima je najmanji od ta četiri broja, u ovom slučaju 24.

Na isti način računa se sreća za preostale patuljake. Ukupna sreća slike je zbroj sreća svih patuljaka. Minimalna sreća slike je najmanja minimalna sreća među svim patuljcima, znači uzme se patuljak koji je prema svojim susjedima najmanje zadovoljan i njegova vrijednost definira minimalnu sreću cijele slike. U ovome primjeru ukupna sreća je 1090, a minimalna sreća je 0.

Sada je na tebi da za pravi problem od 1000 patuljaka pronađeš raspored u kojem su svi što sretniji!

Sretno i veselo kodiranje! 🎄📸

Zadaci

Rang lista