Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# KöMaL Problems in Informatics, February 2016

Show/hide problems of signs:

## Problems with sign 'I'

Deadline expired on March 10, 2016.

I. 394. An imperial probe droid is searching for rebels in the city of Nhalo. The buildings in the city are rectangular, and the corresponding sides are parallel to one another. The probe droid starts its mission in a given building; it scans the entire building, then proceeds to the closest building which is the smallest. Its algorithm is described more precisely below.

The time to scan a building is equal to the area of the building. After the droid has finished scanning a building, it considers the closest unvisited buildings and picks one of the smallest. If there are more smallest buildings, the droid chooses the one having the smallest $\displaystyle X$ coordinate. If there are equal $\displaystyle X$ coordinates, it chooses the building with the smallest $\displaystyle Y$ coordinate. The time needed for the droid to move from one building to another is negligible. The distance between two buildings is defined by the smallest distance between any two of their respective points.

The rebels are currently hiding in a given building. They know the algorithm of the droid, and also the building the droid starts its search from. The rebels immediately start the evacuation, but they need to know how much time they have: they should leave before the droid finds their building.

Your program reads the city map and the starting positions of the rebels and the droid from the standard input (A discussion about handling the standard I/O can be found, for example, in the file stdio.pdf, downloadable from our web page, after the solution of the problem S.64.).

The first line of the input contains a positive integer representing the number of buildings $\displaystyle P$ ($\displaystyle 2\le P\le 100$). The next $\displaystyle P$ lines of the input contain the coordinates of the buildings (each coordinate is an integer between $\displaystyle -100$ and $\displaystyle +100$). The next-to-last line of the input contains the starting position of the droid, while the last line of the input contains the coordinates of a point of the rebel building. The first line of the standard output should contain the available time for the rebels for the evacuation. The second line of the output should contain the time for the droid to scan the individual buildings before it finds them.

Example (with newline characters replaced by / characters):

The source code and a short documentation of your program—containing a brief description of your solution, and the name of the developer environment to compile your code—should be submitted in a compressed file i394.zip.

(10 pont)

solution, statistics

I. 395. (É). The files lemeztar.txt, ismerteto.txt and skala.txt contain data about some old LP jazz records of a commercial company. The field names are contained in the first lines of the tab-separated and UTF­8-encoded text files.

1. Create a new database i395. The above data files (downloadable from our web page) should be imported into the database by using the same names.

2. The appropriate data formats and keys should be set upon importing. The table ismerteto should contain the key field, but no other fields should appear in the other tables.

Tables:

Now solve the following tasks. At each query below, only the requested values should appear. Your solutions should be saved by using the names in parentheses.

3. By using a query, list all data corresponding to LP records created in East Germany (country code GDR, before the German reunification). Sort the list into descending order according to price. (3ndk)

4. By using a query, give the country codes of the 3 countries producing the most LP records bewtween 1960 and 1970 inclusive. (4soklemez)

5. Unopened LP records are the most valuable ones. By using a query, list the performer, title and price of the records whose cover condition is still unopened (,,bontatlan''). (5bontatlan)

6. By using a query, create a report about the solo albums of the jazz pianist Oscar Peterson. The report should contain the price, title, publication year and the (English form of the) condition of the LP record. Follow the sample when creating column headings. (6peterson)

7. For a long time it was difficult to publish records in Hungary (country code H) and abroad at the same time. By using a query, list those performers who published records both in Hungary and abroad. The list should contain each name only once. (7nemzetkozi)

8. There are jazz concert recordings that were published in many countries. By using a query, list all data of the LP records having the same performer names, title and publication year, but were published in different countries. The list should contain each LP record only once. (8tobb)

The database with a short documentation (containing the name and version number of the database application) should be submitted in a compressed file i395.zip.

(10 pont)

solution, statistics

I. 396. It is very easy to create interesting games by using the Scratch programming language and environment. One can discover the basics on their own, but studying programs written by others can also be exciting and instructive. A Hungarian introduction to the language is available at http://scratch.inf.elte.hu/. You can create and share your programs on the international web page http://scratch.mit.edu after registration. The language handles visual elements, variables and lists, and objects can send messages to one another.

By using Scratch, create the well-known snake game according to the following description. The snake should move continuously either horizontally or vertically. One can use the left or right arrows to change the orientation of the head by $\displaystyle 90^\circ$ relative to the current direction; the snake's body should follow the head. Initially, the length of the snake, including the head, is 5 units. On the board, five moving food pieces should appear (having random initial position and direction), which can be consumed by the head of the snake. The length of the snake decreases by 1 unit after each 10-second interval, and increases by 1 unit after eating 3 food pieces. When the snake eats a food piece, another piece should immediately appear somewhere, so there are always 5 pieces on the board. If the snake bites itself or hits the wall, the game is over. The user wins the game if the length of the snake reaches 25 units.

A short documentation of your solution with the Internet address of your shared game should be submitted in a file i396.txt.

(10 pont)

solution, statistics

## Problems with sign 'I/S'

Deadline expired on March 10, 2016.

I/S. 6. We are given $\displaystyle N$ ($\displaystyle 1\le N\le 1000$) towers. The height of each tower, an integer between 0 and 100 inclusive, is known. Our city is considered to be nice if the height difference of any two towers is at most 17. Our architects can modify the tower heights: increasing or decreasing the height of any tower by $\displaystyle x$ levels costs $\displaystyle x^2$ units of money. You should determine the minimum amount of money to make the city nice. Each tower should have a non-negative integer number of levels for all the time.

Your program should read the value of $\displaystyle N$ from the first line of the standard input. The tower heights are found in the next $\displaystyle N$ lines. The first and only line of the standard output should contain the minimum amount of money to complete the task.

Explanation. Towers of height 4, 20 and 21 are kept; 3 new levels are added to the tower of height 1, and 3 levels are removed from the tower of height 24.

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 with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file is6.zip.

(10 pont)

solution, statistics

## Problems with sign 'S'

Deadline expired on March 10, 2016.

S. 105. You are given an $\displaystyle N\times M$ map ($\displaystyle 1\le N, M\le 50$) containing at most 15 islands. The land, deep water and shallow water are denoted by X', .' and `S', respectively. Every island is a connected set of X characters.

Bob can swim along any of the four directions parallel to the four sides of the rectangular map. He lands on a chosen island with parachute, and his goal is to visit all islands. He can walk well on land, but he cannot swim in deep water. He can swim in shallow water but he wants to avoid this as much as possible: he wants to minimize the number of S fields he steps on during his journey.

Your program should read the values of $\displaystyle N$ and $\displaystyle M$ from the first line of the standard input. The map is found in the following $\displaystyle N$ lines. The first and only line of the standard output should contain the minimum total length he needs to swim while visiting all islands.

Explanation. Starting from the top island he swims 1 unit down to the middle one, then 2 units to the right and reaches the lower island.

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 with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file s105.zip.

(10 pont)

solution, statistics

\$Var(Body)