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!

KöMaL Füzetek 1: Tálalási javaslatok matematika felvételire

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

S. 101. We are given the map of a mountain range as a grid of \(\displaystyle N\times M\) numbers containing the elevation data for each coordinate (every elevation is at most \(\displaystyle 1 \,000\,000\,000\). We are also given some nice locations in the mountains. We would like to determine at least how difficult a trip is which starts from some nice location and visits every nice location. In other words, we aim to determine the smallest number \(\displaystyle C\) with the following property: it is possible to start from any nice location and arrive at any other nice location by always proceeding from a square to one of its 4 neighbors with elevation difference at most \(\displaystyle C\).

First your program should read the values of \(\displaystyle N\) and \(\displaystyle M\) (\(\displaystyle 1\le N, M\le 800\), being the number of rows and columns of the map, respectively) from the first line of the standard input. Then read \(\displaystyle M\) integers, representing elevation data, from each of the following \(\displaystyle N\) lines. Next read again \(\displaystyle M\) integers from each of the following \(\displaystyle N\) lines: every integer is either 0 or 1 depending on whether the current location is nice or not, respectively. Your program should write the smallest possible appropriate \(\displaystyle C\) in the first and only line of the standard output.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program without the .exe or any other auxiliary files generated by the compiler but with a short documentation\(\displaystyle -\)also describing which developer environment to use for compiling the source\(\displaystyle -\)should be submitted in a compressed file s101.zip.

(10 points)

Deadline expired on 10 November 2015.


Statistics on problem S. 101.
22 students sent a solution.
10 points:Bálint Martin, Csenger Géza, Fuisz Gábor, Gáspár Attila, Gergely Patrik, Janzer Orsolya Lili, Németh 123 Balázs, Noszály Áron, Zalavári Márton, Zarándy Álmos.
9 points:Alexy Marcell.
8 points:1 student.
7 points:1 student.
6 points:1 student.
5 points:3 students.
3 points:2 students.
1 point:1 student.
0 point:2 students.


  • Problems in Information Technology of KöMaL, October 2015

  • 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