== include(page="template/taskheader" task_id="tractor") ==
Poveste si cerinta...
Zaharel si-a cumparat tractor si s-a inscris la un concurs de tractorit. La acest concurs sunt inscrisi $N = 2^K^$ participanti in total, iar concursul se desfasoara dupa sistemul eliminatoriu:
* La inceput cei $N$ participanti (numerotati convenabil de la $1$ la $N$) sunt asezati de catre organizatorii intr-o ordine oarecare.
* In prima runda, participantul de pe pozitia $1$ se intrece cu cel de pe pozitia $2$, cel de pe pozitia $3$ cu cel de pe pozitia $4$, cel de pe pozitia $5$ cu cel de pe pozitia $6$ etc. Castigatorii avanseaza in runda urmatoare, pierzatorii sunt elimitati din concurs.
* In a doua runda, castigatorul dintre participantii de pe pozitiile $1$ si $2$ se intrece cu castigatorul dintre participantii de pe pozitiile $3$ si $4$, etc., castigatorul dintre participantii de pe pozitiile $N - 3$ si $N - 2$ se intrece cu castigatorul dintre participantii de pe pozitiile $N - 1$ si $N$.
* Concursul continua in acelasi mod, la fiecare runda eliminandu-se jumatate din participanti, pana cand mai ramane unul singur. Participantul care ramane singur va fi considerat castigatorul concursului.
La fiecare intrecere in tractorit in care participantul cu numarul $i$ il bate pe participantul cu numarul $j$ se aduna la premiu valoarea $A{~i, j~}$. Premiul este luat de ultimul participant cara ramane in concurs.
Fiecare din cei $N$ jucatori isi imagineaza cel mai favorabil scenariu (care depinde de asezarea data de organizatori si de castigatorii fiecarei intreceri) in care el castiga turneul iar premiul strans este maxim posibil.
h2. Cerinta
Determinati pentru fiecare din cei $N$ jucatori care este premiul maxim pe care il poate obtine, considerand ca el castiga turneul.
h2. Date de intrare
...
In fisierul $tractor.in$ se afla pe prima linie un numar natural $T$ reprezentand numarul de teste. Urmeaza apoi descrierea celor $T$ teste. Pe prima linie a unui test se va afla numarul $N$ de participanti, iar pe urmatoarele $N$ linii cate $N$ numere naturale separate prin spatii reprezentand matricea $A$ pentru testul respectiv.
h2. Date de iesire
...
Fisierul de iesire $tractor.out$ va contine cate $N$ linii pentru fiecare test reprezentand premiile maxime care se pot obtine pentru fiecare jucator, in ordinea numerotarii de la $1$ la $N$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 4$
* $1 ≤ N ≤ 16$ ({$N$} este o putere a lui $2$)
* $0 ≤ A{~i, j~} ≤ 1 000 000$, $A{~i, i~} = 0$
h2. Exemplu
table(example). |_. tractor.in |_. tractor.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
2
0 2
3 0
4
0 6 3 5
2 0 5 1
3 5 0 2
4 1 3 0
| 2
3
16
12
13
13
|
h3. Explicatie
...
Vom considera exemplul cu $N = 4$ in care jucatorul cu numarul $1$ vrea sa stie premiul maxim pe care il poate obtine. Daca asezarea initiala este $1 4 2 3$ iar intrecerile se desfasoara astfel:
$ [1]$
$ / \$
$ 1 2$
$ / \ / \$
$1 4 2 3$
Premiul care se obtine este $A{~1, 4~} + A{~2, 3~} + A{~1, 2~} = 16$, iar acesta este maxim considerand toate cele $24$ posibiltati pentru asezarea initiala si toate posibilitatile de desfasurare a meciurilor.
== include(page="template/taskfooter" task_id="tractor") ==
