Domácí kolo

D: Jídelna

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

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Ústředí Kasiopey má problém! Během stavby nového komplexu budov na Ma-stře konstruktéři zapomněli na jídelnu pro všechny zaměstnance – nyní je pro ni potřeba najít nejvhodnější místo. Komplex je obdélníková síť čtvercových budov, přičemž v každé budově je pro jídelnu dostatek prostoru. Pro každou budovu víme, kolik v ní pracuje zaměstnanců.

Potřebujeme zjistit, v jaké budově je optimální jídelnu otevřít, aby toho museli zaměstnanci v součtu nachodit co nejméně. Vzdáleností dvou budov přitom myslíme součet rozdílů sloupců a řádků, tedy budova na souřadnicích 3 2 je od budovy na souřadnicích 5 1 vzdálena |5-3|+|2-1|=3 jednotky.

Tvar vstupu

Na prvním řádku souboru je číslo T – počet testovacích vstupů. Na prvním řádku každého testu je N – počet budov v jednom sloupci (počet řádků) a M – počet budov v jednom řádku (počet sloupců). Potom následuje N řádků, v každém M čísel K udávajících počet zaměstnanců v dané budově.

Tvar výstupu

Pro každý testovací výstup vypište součet vzdáleností, které budou muset zaměstnanci do jídelny ujít za předpokladu, že bude jídelna umístěna optimálně.

Lehká verze

  • 1 ≤ T ≤ 10
  • N = 1
  • 1 ≤ M ≤ 100
  • 0 ≤ K ≤ 100

Těžká verze

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 1000
  • 0 ≤ K ≤ 1000

Ukázkový vstup

2
1 5
1 5 4 2 1
4 3
3 1 1
4 4 6
3 6 2
2 2 3

Ukázkový výstup

11
54

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

V prvním případě postavíme jídelnu na pozici 3, potom jeden člověk, musí jít dvě políčka vpravo, pět lidí jedno vpravo, dva jedno vlevo a jeden dva vlevo. Ostatní nemusí chodit nikam, tedy celkem 11.

V druhém případě postavíme jídelnu do druhého řádku a prostředního sloupce. Když pro každého člověka spočítáme jak daleko musí jít, vyjde nám 54. Druhý ukázkový vstup je už těžká verze.

Máš na to!

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