| Fişierul intrare/ieşire: | danger.in, danger.out | Sursă | Algoritmiada 2016, Runda Finala, Seniori |
| Autor | Adrian Budau | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Danger
La şcoala generală numărul 2016 sunt exact N clase formate din M copii. Deoarece cele N clase nu prea interacţioneaza pe parcursul anului directorul şcolii a decis sa reorganizeze copiii in M clase, fiecare formate din N copii în aşa fel încât să nu existe 2 copii care iniţial erau în aceeaşi clasa, iar după reorganizare se află tot în aceeaşi clasă.
Pe deasupra directorul ştie pentru fiecare copil care este riscul pe care îl adauga într-o clasa. Riscul unei clase este dat de maximul sumei riscurilor a doi copii din acea clasa. Astfel dacă într-o clasa se afla 3 copii cu riscurile 1, 2 şi 3, riscul acelei clase este 5 = 2 + 3.
Directorul vă roagă sa-i spuneţi cum să reorganizeze copiii în aşa fel încat cel mai mare risc al unei clase sa fie minim, iar in schimb va promite 100 de puncte.
Date de intrare
Fişierul de intrare danger.in va conţine pe prima linie 2 numere N si M reprezentând numărul iniţial de clase si respectiv numărul iniţial de copii din fiecare clasă.
Urmatoarele N linii vor conţine M numere naturale fiecare reprezentând riscurile copiilor. Fiecare rând din aceste N va conţine riscurile copiilor dintr-o singură clasă.
Date de ieşire
În fişierul de ieşire danger.out trebuie să se afle M linii, iar pe fiecare din aceste M linii trebuie să se afle N numere, reprezentând riscurile copiilor din fiecare clasă dupa reorganizare. A j-a valoare de pe rândul i va reprezenta riscul unui copil care iniţial se afla in clasa j.
Restricţii
- 2 ≤ N, M, N * M ≤ 100.000
- 1 ≤ riscul unui copil ≤ 1.000.000.000
- Orice soluţie corectă care minimizează cel mai mare risc al claselor este corecta
- Pentru teste care valorează 5 puncte N, M ≤ 4
- Pentru teste care valoreaza alte 5 puncte N ≤ 2
- Pentru teste care valoreaza alte 20 de puncte N ≤ 3
- Pentru teste care valoreaza 80 de puncte N * M ≤ 15.000
Exemplu
| danger.in | danger.out |
|---|---|
| 3 3 1 2 3 3 1 2 2 1 3 | 1 2 3 2 3 1 3 1 2 |
| 2 3 1 5 8 3 3 3 | 1 3 5 3 8 3 |
Explicaţie
Pentru primul test s-au format 3 clase noi:
- din primul copil din prima clasă, al trelea copil din a doua clasă si al treilea copil din a treia clasă
- din al doilea copil din prima clasă, primul copil din a doua clasă şi al doilea copil din a treia clasă
- din al treilea copil din prima clasă, al doilea copil din a doua clasă si primul copil din a treia clasă
Pentru al doilea exemplu o altă soluţie corecta este:
5 3
1 3
8 3
dar urmatoarea nu este corecta deoarece nu există niciun copil în prima clasă cu riscul 3
3 5
3 1
3 8
Nici urmatoarea soluţie nu este corectă deoarece nu există 2 copii cu riscul 1 in prima clasa înainte de reorganizare
5 3
1 3
1 3
