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. 59. An investor plans to build a new luxury supermarket in the heart Manhattan. He knows that the building should be built as close to his future clients as possible. He already accurately surveyed the number of possible clients from each part of the city. Your task is to specify a location for the supermarket such that customers can reach it with the least travelling on the average.

Your program should solve this task. As usual, the map of Manhattan is considered as a regular grid with two-way streets, and crossings having integer coordinates.

For simplicity, we identify clients' flats and the supermarket with the corresponding nearest crossings. Instead of the Euclidean distance, we measure the distance between crossing \mathbf{p}_{i} with coordinates (xi,yi) and crossing \mathbf{p}_{j} with coordinates (xj,yj) by the following formula (which is often termed as Manhattan distance): d(\mathbf{p}_i,\mathbf{p}_j)= |x_j -x_i|+ |y_j -y_i|, measuring the shortest distance along the grid.

The result of the investor's survey is read from the standard input: its first line contains the number of crossings 1\le N\le
1\;000\;000, and the following N lines describe each crossing. There are three integers in the (i+1)st line separated by a space: the two coordinates 0\le x_i,y_i \le 1\;000\;000 of the ith crossing and the number of expected clients 1\lewi\le1000 living there.

Your program should find the optimal crossing \mathbf{p}_{0} such that the average weighted distance between \mathbf{p}_{0} and all the crossings listed above is minimal (with weights being the number of clients living on the actual crossing). In other words, the quantity


\overline D = \frac{\sum_{i=1}^N d(\mathbf{p}_0,\mathbf{p}_i)\cdot
w_i}{\sum_{i=1}^N w_i}

is to be minimized. The standard output should only contain three numbers separated by a space: the two coordinates x0, y0 of the optimal location \mathbf{p}_{0} and the average weighted distance \overline D with 4 digits of precision. If there are many solutions, any of them can be given. In the example, ``Példa bemenet'' is a sample input, ``kimenet'' is output, while ``Térképvázlat'' is the corresponding map.

Evaluation: the maximal 8 points can be awarded if your program solves the largest test cases within one minute. 5 points can be awarded if your program correctly handles test cases already with N\le1000. The documentation is worth 2 points.

The source code and project files of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (s59.txt, s59.pdf, ...) in a compressed folder s59.zip.

(10 points)

Deadline expired on 10 February 2011.


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

Megoldásvázlat

A megoldáshoz azt kellett észrevenni, hogy az átlagos távolság épp akkor minimális, amikor a súlyozott távolságösszeg minimális (hisz egymás konstansszorosai), ennek pedig függőleges és vízszintes összetevői egymástól teljesen függetlenek, így külön-külön minimalizálhatóak.

Tehát két egydimenziós problémát kaptunk: két, abszolútérték-függvények összegeiből felépített függvény minimumhelyét kell meghatároznunk. Az ilyen függvények konvexek, és egyenes szakaszokra bonthatóak: minimumhelyük tehát ott van, ahol ezen szakaszok meredeksége negatívból pozitívba fordul, amely egy rendezés után lineáris időben meghatározható.

C++ mintamegoldás


Statistics on problem S. 59.
8 students sent a solution.
10 points:Borsos 607 Zalán, Nagy 111 Miklós, Szabó 928 Attila.
9 points:Nagy Róbert.
8 points:1 student.
7 points:1 student.
5 points:1 student.
4 points:1 student.


  • Problems in Information Technology of KöMaL, January 2011

  • 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