Máme štvorcovú tabuľku. V tabuľke máme prirodzené čísla. Pekne spôsobne, v každom políčku jedno.
Každý riadok aj každý stĺpec má pri sebe napísané jedno číslo. Toto číslo hovorí, aký súčet chceme v danom riadku/stĺpci dosiahnuť.
Úloha
Daj het niektoré čísla z tabuľky tak, aby všetky súčty sedeli.
Formát vstupu
Toto je open data úloha, dostanete teda od nás úplne všetky vstupy. Môžete sa na ne ľubovoľne pozerať a robiť s nimi čo len chcete. Vstupov je 8 a volajú sa 1.in
až 8.in
. Každý vstup začína číslom \(t\) predstavujúcim počet testov, ktoré obsahuje. Každý test má nasledujúci formát:
- V prvom riadku je číslo \(n\): rozmer tabuľky. (V každom vstupe majú všetky testy rovnaké \(n\).)
- V druhom riadku je \(n\) čísel: predpísané súčty pre riadky zhora dole.
- V treťom riadku je \(n\) čísel: predpísané súčty pre stĺpce zľava doprava.
- V každom z nasledujúcich \(n\) riadkov je \(n\) kladných celých čísel nepresahujúcich \(20\), v poradí, v akom sú rozmiestnené v tabuľke.
Môžete predpokladať, že pre každú zo zadaných tabuliek existuje aspoň jedno riešenie.
Vstupy pre windows tu, pre linux tu.
Formát výstupu
Odovzdajte zip archív a v ňom príslušné výstupy. Tie musia byť pomenované 1.out
až 8.out
a umiestnené v koreňovom adresári zipu. Za každý výstup, ktorý sa v zipe naozaj bude nachádzať a bude úplne správny, dostanete dva body.
Formát výstupu: pre každý test vypíšte \(n\) riadkov a v každom \(n\) čísel: čísla vo výslednej tabuľke, pričom namiesto čísel, ktoré ste “dali het” (čítaj: z tabuľky odstránili) vypíšte nuly.
Môžete vypisovať aj nadbytočné medzery a voľné riadky medzi výstupmi pre jednotlivé testy, náš testovač ich spokojne odignoruje. Ak existuje pre nejakú tabuľku viacero riešení, môžete vypísať ľubovoľné jedno z nich.
Posledné nanajvýš 4 body za úlohu udelíme za popis toho, ako ste úlohu riešili, a obzvlášť programu/ov, ktoré ste použili. Rozumne podrobný popis ľubovoľného postupu, ktorý nejaké vstupy naozaj vyriešil, môže dostať aspoň 3 body.
Príklady
Input:
1
5
15 12 14 14 24
10 20 18 14 17
7 3 2 5 1
3 5 4 3 3
5 3 3 9 5
5 6 4 3 4
4 9 8 8 7
Output:
7 0 2 5 1
3 5 4 0 0
0 0 0 9 5
0 6 4 0 4
0 9 8 0 7
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.