| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 57 | 7 | 7 | 43.750% |
Ponoć se približavala, valjalo se požuriti. Nakon što je Margarita uspješno pozdravila sve goste, oni su nesmetano zasjeli za dugačak stol. Goste možemo označiti brojevima od 1ドル$ do $N,ドル točno onim redom kojim su zasjeli na stol. Iz nepoznatih razloga, broj gostiju na velikom balu kod Sotone uvijek je potencija broja 2ドル$.
No, Margarita se sada nalazi u problemu, jer između svakog para gostiju vlada određena netrpeljivost koju možemo označiti nenegativnim brojem. Netrpeljivost između gostiju $i$ te $j$ možemo označiti kao $netrp(i, j)$. Uvijek vrijedi $netrp(i, j) = netrp(j, i)$ te $netrp(i, i) = 0$.
Kako su se gosti već (ne)ugodno smjestili, Margarita ne smije drastično mijenjati njihov poredak. Gosti zapravo ni ne znaju da se nalaze u listovima velikog Sotoninog potpunog binarnog stabla, popularno zvanom VSPBS, koje je prikazano na slici u slučaju $N = 4$.
Margarita može odabrati neki čvor, i u jednom potezu zamijeniti lijevo i desno dijete toga čvora, time promijenivši poredak gostiju koji se nalaze u pripadajućim listovima. Prikazano je stanje stabla, a time i stola, nakon što Margarita napravi jedan potez nad korijenom stabla. Margarita može napraviti prozivoljan broj poteza nad proizvoljnim čvorovima.
Ukupna netrpeljivost stola definira se kao zbroj netrpeljivosti susjeda za stolom. Pomozite Margariti odrediti najmanju moguću netrpeljivost stola koju može postići!
U prvom je retku prirodan broj $N,ドル broj gostiju.
U i-tom od sljedećih $N$ redaka nalaze se redom brojevi $netrp(i, j)$ koji zadovoljavaju gornja svojstva.
Potrebno je ispisati traženi broj iz zadatka.
U svim podzadacima vrijedi 1ドル ≤ N ≤ 2048$ te $N$ je potencija broja 2ドル,ドル 0ドル ≤ netrp(i, j) ≤ 10^9$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N ≤ 16$ |
| 2 | 17 | $N ≤ 128$ |
| 3 | 32 | $N ≤ 512$ |
| 4 | 41 | Nema dodatnih ograničenja. |
2 0 2 2 0
2
4 0 2 3 1 2 0 4 5 3 4 0 3 1 5 3 0
6
8 0 2 5 8 5 9 2 6 2 0 8 4 3 7 5 3 5 8 0 3 8 4 3 3 8 4 3 0 2 2 7 7 5 3 8 2 0 7 3 3 9 7 4 2 7 0 6 7 2 5 3 7 3 6 0 4 6 3 3 7 3 7 4 0
25
Pojašnjenje probnih primjera: U drugom primjeru, jedan od mogućih rasporeda koji postiže najmanju netrpeljivost je 2 1 4 3.
Olympiad > Croatian Highschool Competitions in Informatics > 2023 > Croatian Olympiad in Informatics 2023 3번