Finále

C: Nákladní loď

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Obrovská nákladní loď letí vesmírem. Loď je tvořena krychlovými komorami uspořádanými v krychlové mřížce (jsou zarovnány do řádků, sloupců a řad a v každém směru jich je milion). Každá komora je určena čísly x, y a z podle toho, v jakém řádku, sloupci a pozici v řadě se nachází.

Kuba, vesmírný kovboj, se dohodl s pašeráky, že naplní spoustu komor zlatem a oni mu pak celou loď i s pokladem vymění za lepší, která jej dostane až ke Kasiopee. Slíbil pašerákům, že když loď oskenují zepředu, zboku a zvrchu, uvidí přesně K, L a M zaplněných komor. Skener však vidí jen první plnou komoru v daném řádku, sloupci nebo řadě. Pomozte Kubovi najít, kolik zlata musí získat a jak jej má rozložit, aby pašerákům dal zlata co nejméně. Pokud Kuba slíbil něco nesplnitelného, vypište -1.

Na pořadí K, L a M nezáleží, pokud existují skeny (přední, boční a horní), které nabývají všech těchto čísel, je odpověď správná.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů.

Každý problém je zadán třemi čísly K, L a M na jednom řádku, které udávají, kolik komor plných zlata musíme vidět, pokud se díváme ze tří stran.

Tvar výstupu

Pokud neexistuje řešení, vypište -1. Jinak nejprve vypište X, minimální počet komor plných zlata, které musel Kuba naplnit, a na dalších X řádcích vypište jejich pozice. Pro každou souřadnici komory s musí platit, že 0 ≤ s ≤ 1 000 000.

Lehká verze

  • T ≤ 10
  • 0 ≤ K, L, M ≤ 100

Těžká verze

  • T ≤ 10
  • 0 ≤ K, L, M ≤ 100 000

Ukázkový vstup

3
1 1 1
5 6 7
100 2 2

Ukázkový výstup

1
0 0 1
7
0 0 1
0 1 1
1 1 2
2 1 1
2 2 1
4 2 3
3 3 3
-1

Vysvětlení ukázkového vstupu a výstupu

V prvním vstupu vidíme jenom jednu komoru ze všech stran.

Druhý vstup potřebuje alespoň 7 komor zlata, což je maximum, které vidíme z jedné strany. Popsané rozložení splňuje i zbylé dva skeny.

Ve třetím případě musíme ze dvou stran vidět 2 komory, ale za ně se neschová 100 komor, které mají být vidět z posledního skenu.

Správných řešení je mnohem více než jedno. Protože nás nezajímá směr, můžeme prohodit sloupce. Zároveň pokud ke každé souřadnici přičteme 1, taky se nic nezkazí.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)