KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

S. 112.

(10 points)

Deadline expired on 10 January 2017.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem S. 112.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley