KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up


KöMaL Problems in Informatics, February 2012

Please read the rules of the competition.

Show/hide problems of signs:

Problems with sign 'I'

Deadline expired on 12 March 2012.

I. 286. The following game is played on a 4×8 board. The aim is to fill it completely by 8 pieces of different shape. Each piece should be used only once. The example shows a possible solution (also specifying the shapes).

Of course, these pieces can be arranged differently, but they should fill the board completely. Pieces can be rotated by 90 degrees, or flipped, so each piece can have 8 positions.

The color of each piece is also specified, and it is may be prescribed that some squares should be covered by a specified color.

Your program should give a possible arrangement of the pieces. The first command line argument of your program is the name of the file describing the color of the pieces and the color of certain squares. The second command line argument is the name of the file containing your solution. Only solvable cases will be used during testing.

The first line of the input file contains colors of the 8 pieces (in a similar order as in the figure), separated by a space. The color is denoted by a single character. The next 4 lines describe the obligatory colors of the board, with 8 characters in each line, separated by a space: either a color code or a *, if the color of that square can be arbitrary after covering.

The output file describes the filled rectangle. It should contain exactly 4 lines, with 8 digits in each line, separated by a space. The digits give the number of the actual piece.

In the example, be.txt is the sample input, while ki.txt is the corresponding output.

The source code (i286.pas, i286.cpp, ...) together with a short documentation (i286.txt, i286.pdf, ...) -- also describing which developer environment to use for compiling, further a brief description of your solution -- should be submitted in a compressed file i286.zip.

(10 pont)

solution (in Hungarian), statistics

I. 287. Before going hiking for a day, it is worth making a thorough plan. There can be many interesting details.

For the trip between Bükkszentkereszt and Eger, we select the track on a map by using data of a map making software. For different segments of the track, the source file contains tourist symbols (`` jelzés'' in the example), road materials (``burkolat''), road lengths (``hossz''), the elevation (``emelkedés'') and depression (``süllyedés'') in meters, and the planned time in minutes (``idő'') to accomplish that distance. Data in this example are taken from http://turistautak.hu/.

By using a spreadsheet application, you should solve the following tasks.

    1. Load the file utterv.txt. (UTF-8 encoded, tabulator separated text file) into the spreadsheet, beginning with cell A1, and save it as i287 in the default file format.

    2. By inserting columns and completing the header, create the structure similar to the example.

    3. Column E should contain the distance in meters from the starting point. Column J should contain the average speeds in km/h for each section (by using the given length and time values).

    4. Column H should contain the altitudes in meters after covering each section, if the original altitude (Eger) is in cell M1.

    5. By using a function, cell M3 should contain the total length (in km) of the tour.

    6. By using a formula, cell M4 should contain the average speed of the complete tour (using the total distance covered and the sum of planned times).

    7. Cell M5 should contain the number of sections in which the speed will be greater than the total average speed.

    8. We will also take rests during the excursion. Cell M6 should contain the number of hours in rest, provided that after each 5 km, we are going to pause for 10 minutes.

    9. Cell M7 should contain in hours the planned time for the tour, being the sum of the section times and resting minutes.

    10. By using a copyable formula, to the right and down of cell L9 you should determine the number of different road materials and their total length.

    11. Now format the sheet according to the following description.

      a. Cells in the first row should be centered horizontally and vertically.

      b. Column names and texts in the first row should be displayed in bold face.

      c. Precision in cells that may contain non-integer computed values should be set to 2 digits.

      d. Computed quantities in range I2:I4 should have the units according to the example, further, 2 digits of precision. To the right of column L, each computed values should have units.

      e. Cells containing data should be surrounded by a thin frame from inside. Cells in range A1:J57 should be framed by a thick line from outside. The first line should be framed by a thick line also from below. The other data should not be framed.

    12. Create a PointXY diagram. The vertical axis is the altitude in meters, and the horizontal axis corresponds to the distance covered in km.

      a. Axis labels should be displayed. The diagram should be scaled so that the data fills the complete area.

      b. The diagram should contain no legend. The title should be ,,Altitude diagram''.

The spreadsheet (i287.xls, i287.ods, ...) together with a short documentation (i287.txt, i287.pdf, ...) also describing the name and version number of the spreadsheet application should be submitted in a compressed file i287.zip.

(10 pont)

solution (in Hungarian), statistics

I. 288. There are two task descriptions below, but you should solve only one of them. Before you select, you may want to consider

  • whether there is a wireless network in your school interesting enough to be examined, and

  • what kind of devices are present (phone, netbook, notebook).

Task a): school WiFi map.

Wireless networks have become more and more widespread in schools, covering not only community places, but the complete premises of the school. Areas covered by different hotspots are necessary overlapping.

Build a map of your school's WiFi network. The diagram should contain the location of the hotspots, and the connection speeds between a given point and the nearby hotspots. (To achieve nice visualization, you can consult user interfaces of programs managing wireless networks or even tourist maps.) You should also create a textual description of the WiFi network, e.g. it is in operation since when, what kind of devices are in use, who is allowed to connect, what methods are used for identification, and so on.

The file i288.pdf should be submitted, containing the textual description, the map, your method of creating the map and the type of device you actually used to collect data.

Task b): street WiFi map.

More and more companies or private persons operate WiFi hotspots. Just by walking through a street in a city, you pass many nearby hotspots.

Build a map to graphically represent the available hotspots. Then create a statistics about how they choose the SSIDs (company name, person name, factory settings or random), about the channels set, and about the security protocol.

The file i288.pdf should be submitted, containing the map, the statistical data, your conclusions, your method of creating the map and the type of device you actually used to collect data.

(10 pont)

solution (in Hungarian), statistics

Problems with sign 'S'

Deadline expired on 12 March 2012.

S. 69. Given a text of N characters, we would like to find K patterns, each of length M characters. Unfortunately, letters of the patterns to be recognized are scrambled, consequently, you have to find any permutations of the given patterns in the text.

The text is read from the standard input. The first line of the input contains 3 integers, separated by a space: the values of N, M and K (1\le N\le
1\;000\;000, 1\leM\le1000, 1\le K\le 10\;000). The second line of the input contains the text of length N, finally, the next K lines contain the K patterns of length M. Characters are chosen only from the 26 lower case letters of the English alphabet.

The solution -- written to the standard output -- should contain K lines. The ith line should contain either the least position from which one can find an arbitrary permutation of the ith pattern in the text of length N, or the number ,,0'', if there is no such position.

In the example, ,,Példa bemenet'' is the sample input, while ,,Példa kimenet'' is the corresponding output.

The source code of your program (s69.pas, s689.cpp, ...) -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted in a compressed file s69.zip, also containing a brief description of your solution (s69.txt, s69.pdf, ...) and the name of the developer environment to use for compiling.

(10 pont)



Upload your solutions above

Our web pages are supported by:   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