KöMaL Problems in Informatics, April 2013
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on May 10, 2013.
I. 319. A few decades ago several network types existed, but nowadays almost all networks are based on TCP/IP. Devices are organized into subnetworks for more efficacy. Subnetworks can be created solely on a logical basis, however, they are generally also separated physically. Devices within the same network can communicate directly; other devices are accessed through the default gateway.
Every device in a TCP/IP network should have its IP address (that is, the device identifier), its netmask, the IP address of the default gateway (these last two items are properties of the subnetwork), finally, for an access by using domain names, the DNS server address. These addresses consist of four numbers, typically in a decimal format, separated by a period and each containing one byte of data.
The size of a subnetwork (that is, the number of corresponding IP addresses) can be determined from the netmask according to the following. There are some leading 1s in the binary form of the netmask, the remaining digits are then entirely 0s. Let k denote the number of 0s in the binary form of the netmask. The number of binary numbers having k binary digits, 2k, gives the corresponding number of addresses. Since the first address is the subnetwork address, and the last one is a special one (the ``broadcast address''), the total number of devices with distinct IP addresses in the subnetwork is 2k-2.
The subnetwork address and the broadcast address can be determined from the IP address of a device and from the corresponding netmask as follows. On one hand, the subnetwork address is formed by applying a logical AND operation to each binary digit pairs of the IP address and the netmask. On the other hand, the broadcast address is obtained if a bitwise logical OR operation is applied to the binary form of the IP address and the ones' complement of the netmask.
The file ipadat.txt (downloadable from our home page) contains data on some devices in the intranet of a certain company. Each line contains two pieces of data separated by one space character: the IP address and the netmask. The first few lines of the file is given below.
Your program should solve the following tasks. First, the number of the actual task (e.g., ``Task #6'') should be displayed. If the user is prompted for an input, a message describing the input should also appear (e.g., ``Give the number of employees''). Diacritical marks in the output may be omitted.
1. Read and store data from the file ipadat.txt in the appropriate format needed later.
2. Display on the screen the number of IP addresses in the file.
3. Create a function binbe. It should convert the successive (decimal) numbers in an IP address to adjacent blocks of 8-bit binary numbers as a text. For example, 10.32.0.17 is converted to 00001010 00100000 00000000 00010001 (where space characters have been inserted here only for better readability).
4. Create your function binbol. It should convert a 32-digit binary number stored as text to the corresponding IP address in decimal form.
The following tasks can use the above functions directly, or through some other functions or procedures.
5. Read the value of a netmask in decimal form, then display on the screen the number of possible devices with different IP addresses within this network. (For example, the netmask 255.255.240.0 corresponds to at most 4094 devices.)
6. In a certain institution subnetworks were created in such a way that their size is the smallest possible, but the number of devices with different IP addresses is at least 3 times the number of employees. Read the number of employees, then determine the decimal form of the netmask in the network.
7. Let us consider the company in the introduction above again. The last usable IP address of each subnetwork is assigned to the gateway. Display on the screen the line numbers in the file (separated by a space) that contain the subnetwork side IP address of such gateways.
8. Create a file csoport.txt containing the IP addresses of the ipadat.txt file grouped by subnetworks. The first line in each group should be the subnetwork address, then the corresponding addresses should be listed in each line (these lines containing an IP address should be indented with a tabulator character).
The output corresponding to the above input is shown below.
The source code (i319.pas, i319.cpp, ...) together with a short documentation (i319.txt, i319.pdf, ...) describing which developer environment to use for compiling should be submitted.
Downloadable file: ipadat.txt
I. 320. Your task with your friends is to create an easily understandable web page, similar in structure to the port.hu page, containing your school events. Your page should also contain past and known future events. The following content should be created.
When an event (a performance, lecture, and so on) is chosen, its title, date(s), location and the list of performers or contributors are to be displayed.
When a location (e.g., a room) is chosen, the name and date of the events at that location should be displayed.
When a date is chosen, all the events taking place that day should be listed with title, date and location.
When a performer is chosen, the event name with their role should be displayed.
The above task is divided among the group members. Your task is to design the appropriate database, fill it with some test data, further, make the SQL queries needed to create the above content. You should use the MySQL database manager (MySQL is also contained in the multi-platform XAMPP package we recommend; as for the database server, phpmyadmin may be convenient).
A brief description of your solution (i320.pdf) with an image of the database model (i.e., table relations) and the MySQL version number, the export/dump of the database (i320.sql), and a file i320.txt containing the SQL queries to create the above page contents should be submitted.
I. 321. With today's digital printing services it is very easy to create impressive publications - such as personal calendars, bookmarks or panorama photos - from digital images. Photo mosaic posters, in which hundreds of photos make up a single image, are spectacular examples. If the resolution of the mosaic poster is high enough, the individual images can all be recognized.
Your task is to recreate the cover page of the actual issue of this Középiskolai Matematikai és Fizikai Lapok journal as a photo mosaic by using images, drawings or figures from the journal archives.
You may want to use some freely downloadable programs, such as
- the AndreaMosaic v3.30, to create photographic mosaics,
- the IrfanView image viewer, to modify image formats (even as a group), and
- the HTTrack Website Copier, to download entire web pages.
The cover page of the current issue of our journal can be downloaded from our home page (as an image cimlapnagy.jpg; this image should be recreated as a photo mosaic). The longer side of the image should have length between 70 and 100 cm. Cover pages this year are black and white images, so you should also use this format along with line images.
To create a photo mosaic of sufficiently good quality without too much repetition, you will need at least 200 small images. You should download these images from the KöMaL archives and convert them into the required format.
The photo mosaic image (i321.jpg, with size not exceeding 10 MB) should be submitted, together with a short documentation (i321.txt, i321.pdf, ...) containing the version number of the software products used and a brief description of your solution.
Problems with sign 'S'
Deadline expired on May 10, 2013.
S. 80. Big Bird often visits his friends in a city of N inhabitants. In this city, all streets are one-way. Big Bird does not like walking too much, so, as a first question, he wondered how many and which streets he can use to walk to one of his friends (Big Bird has N-1 friends, since everybody is his friend) such that the distance covered is as small as possible. He then raised a second, harder question: ``what is the number of shortest possible ways from my house to one of my friends' house?''
Your program should read the values of N and M from the first line of the standard input (), denoting the number of houses and streets. Then, from the next M lines it should read the integers ki, vi, si (separated by a space) describing the streets: the first house in the ith street is ki, the last house is vi, and the street length is si. Big Bird lives in house #1. The first line of the standard output should contain the integer a, being the number of streets answering his first question. The next line should contain these a streets in increasing order, separated by a space (their number is specified by their position in the input file). The last line of the output should contain the answer to the second question, that is, the number of ways to each of his friends' house via a shortest route (more precisely, the remainder of this integer upon division by 1000007).
``Példa bemenet'' contains a sample input, while ``Példa kimenet'' is the corresponding output.
Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. The remaining maximal 9 points for your program can only be obtained if it can solve an arbitrary valid input within 1 second of running time. Partial points of the above 9 points can be obtained if your program can solve only smaller test cases within the allotted time. Your program will only score points if it produces correct outputs in at least 20% of the inputs corresponding to the first task.
The source code (s80.pas, s80.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s80.txt, s80.pdf, ...) - also describing which developer environment to use for compiling - should be submitted in a compressed file s80.zip.
Upload your solutions above