Problem S. 112. (December 2016)

S. 112. Subscribers can reach the text of the problem after signing in. The text will be public from December 28, 2016.]

(10 pont)

Deadline expired on January 10, 2017.

Sorry, the solution is available only in Hungarian. Google translation

A sugárutak egymásra merőlegesek, az egész várost elhelyezhetjük egy koordinátarendszerben és tekinthetünk rá úgy, mint pontok halmazára. A tűzoltóautó a városban a sugárutak mentén tud haladni, így az összes ponttól vett súlyozott Manhattan-távolságot szeretnénk minimalizálni. (Két pont Manhattan-távolsága a megfelelő koordinátáik különbségének összege: \(\displaystyle M=|x1-x2|+|y1-y2|\) ).

A képletből látszik, hogy a minimumszámolást megtehetjük külön-külön az \(\displaystyle x\) és az \(\displaystyle y\) koordinátákra. A tűzoltóállomás oszlopában és sorában is kell lennie tűzcsapnak, különben a sor/oszlop mozgatásával csökkenthető lenne a minimum, azaz csak az előforduló \(\displaystyle x\) illetve \(\displaystyle y\) koordinátákra kell kiszámolni a koordináták súlyozott mediánját.

Az algoritmusunk komplexitása \(\displaystyle O(K*log(K))\) a rendezés miatt, memóriaigénye O(K).

Megoldás: Busa Máté kódja main.cpp

Statistics:

16 students sent a solution.
10 points:	Busa 423 Máté, Csenger Géza, Gáspár Attila, Janzer Orsolya Lili, Kiss Gergely, Molnár Bálint, Németh 123 Balázs.
9 points:	Tóth 827 Balázs.
8 points:	2 students.
7 points:	1 student.
5 points:	1 student.
4 points:	1 student.
2 points:	2 students.
0 point:	1 student.

Problems in Information Technology of KöMaL, December 2016