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 2015

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on March 10, 2015.


I. 367. Some mirrors are placed diagonally in certain squares of a uniform square grid of size \(\displaystyle M\times N\) (\(\displaystyle 5\le M, N\le 100\)). Both sides of the mirrors reflect the light perfectly, and a mirror can freely rotate about the center of the square. The light in this model travels one unit of distance (=the side length of a square) in one unit of time. A light impulse enters the grid perpendicular to one of its sides, and initially passes through the midpoint of the side of a square. In each instant when the light impulse hits the side of a square of the grid, the mirrors are rotated by 90 degrees.

The first line of the input file (``Bemenet'' in the example) contains the number of rows and columns. The second line contains the incoming direction (b, j, f, l, meaning ``from left/right/top/bottom'') and position of the light impulse (the square positions are counted from top to bottom and from left to right). Then each of the following \(\displaystyle M\) lines contains exactly \(\displaystyle N\) characters: the space character (o in the example) denotes a square without a mirror, while the \ and / characters denote the initial state of the mirrors.

The first line of the output file (``Kimenet'' in the example) should contain the time needed for the impulse to leave the grid. The second line of the file should contain the exit position (using the same format as in the second input line). If the light is trapped within the grid, the first output line should contain a -1 value, and the second line should remain empty.

The first and second command line arguments of your program are the name of the input and output files, respectively.

The source code (i367.pas, i367.cpp, ...) of your program with a short documentation (i367.pdf) of your program and solution, also describing which developer environment to use for compiling the source, should be submitted in a compressed file i367.zip.

(10 pont)

solution, statistics


I. 368. In this task we create a database containing and comparing several CPU features from different catalogues to help our friend make his decision about buying a new computer.

Create a new database with name i368. In the file ixyz.zip (downloadable from our web page) you will find the UTF-8 encoded and semicolon-separated text files cpu.csv, ceg.csv and arlista.csv. The first line of each file contains the field names according to the following description. You should import the files and create the tables cpu, ceg and arlista, then set the appropriate types and keys.

Tables:

The table arlista connects the processor data with the store data: each product appears only once in each store, and has the same price in a given store.

When solving the following tasks, save the queries, tables and reports by using the names in parentheses. Only the required fields and given names should be used.

Based on the 3 benchmark tests we want to know which processors are the fastest. Instead of averaging the averages of these three quantities (falling into different ranges), we do the following. For each of the 3 speed data series we select the maximum, then compare every value to their corresponding maximum.

1. To perform the comparison, first create a query that determines the maximum speed values with names MBM1, MBM2 and MBM3 in the corresponding categories. (1maxbm)

2. Then make a query that contains the id's of the processors, the 3 speed values divided by the corresponding maximum values and named SBM1, SBM2, SBM3, and a performance field, being the average of the previous three quantities. (2teljes)

3. Create a query to give the processor and socket types and the performances, sorted according to decreasing performance. (3sorban)

By decreasing the processor feature size, the energy consumption generally decreases. At the same time, the energy consumption of more complex CPUs with more cores or operating at higher clock rates or with integrated graphics processing units is higher than that of simpler CPUs. Verify to what extent the above general statements are true by examining the given data.

4. Add a new logical field GP to the table cpu, and create a query modifier to determine whether there is an integrated graphics processing unit in the processor. (4gp)

5. By grouping according to the number of cores, threads and the feature size, give the number of processors without integrated graphics units and their average energy consumption in each of the above groups by using a query. (5fogyaszt)

6. Make a query to give the processor type, performance and energy consumption for CPUs having at least 0.5 GHz difference between their maximum achievable and average clock rates. (6turbo)

7. Let us consider the CPUs with performance at least 60%. Make a query to give the type of the first 3 processors with minimum energy consumption, together with the stores where one can buy them. (7kisfogy)

After receiving the above information, our friend wants to buy an AMD processor with 8 cores, and he would like to know the prices of these CPUs in the stores located in the 4th and 13th districts.

8. Make a query to list the processor types, performances and prices based on the above criteria, together with the store names, postal code and address. (8amd8)

Now our friend would like to extend his search by considering not only the two districts listed above, but also any web stores.

9. By using a query, give the name of the store where one of the chosen devices has the lowest price among the chosen processors. Also give the CPU type and price. (9web)

Finally, our friend thinks it would be worth investigating other CPUs as well, having a similar price: what if one finds a much better CPU only for a little more money?

10. Create a report to display, for the CPUs within the price range HUF 30000-40000, all the CPU types, performances, the type of graphics units, prices, and the store names where these processors are available. The report should be grouped according to processor types, and, within this, sorted according to increasing price. The report title should be ``Some more CPUs for HUF 30000-40000''. The heading above the data should contain the words ``Type, Price, Store name, Performance, Graphics''. The report size should be A4 with portrait orientation. All fields and values should be completely visible. If needed, make a query to collect the necessary data. (10többi)

Source: the processor data were taken from the January 2015 issue of the CHIP Magazine.

The database containing your solution or the text file containing the SQL queries (i368.odb, i368.accdb, i368.sql) should be submitted in a compressed file (i368.zip), also containing a short documentation (i368.txt, i368.pdf) and specifying the name and version number of the database application.

Downloadable file: ixyz.zip

(10 pont)

solution, statistics


I. 369. Create a program to display the given figure (consisting of \(\displaystyle -\), X and line break characters) on the standard output. Your program cannot read from and write to any file. Your source code should contain the least number of characters, and should reproduce the given figure exactly.

Scoring. You can obtain 1 point for a brief and proper documentation clearly describing your solution. The shortest source code (containing the least number of characters) will get 9 further points. Longer solutions will get proportionally less points.

The source code (i396.pas, i396.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (i396.txt, i396.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file i396.zip.

(10 pont)

solution, statistics


Problems with sign 'S'

Deadline expired on March 10, 2015.


S. 96. A beam of length \(\displaystyle D\) (\(\displaystyle 1\le D\le 10^{15}\)) should be cut into \(\displaystyle N\) pieces (\(\displaystyle 1\le N \le 500\;000\)). The length of the \(\displaystyle i\)th piece should be \(\displaystyle r_i\) (\(\displaystyle 1\le r_i\le 10^{15}\)), and the sum of these \(\displaystyle r_i\) numbers is \(\displaystyle D\). The cost of cutting any beam of length \(\displaystyle L\) into two arbitrary pieces is \(\displaystyle L\) units of money. We always cut one piece into two smaller pieces at a time. Your task is to cut the original beam of length \(\displaystyle D\) into smaller pieces with length \(\displaystyle r_i\) so that the total cost is minimal.

Your program reads the values of \(\displaystyle N\) and \(\displaystyle D\) from the first line of the standard input, then the \(\displaystyle r_i\) integers from the following \(\displaystyle N\) lines. The first line of the standard output should contain the minimum sum necessary to complete the cutting process.

In the ``Példa bemenet'' sample input the \(\displaystyle r_i\) integers are listed in one line, and the minimum cost is given in the ``Példa kimenet'' sample output.

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

The source code (s96.pas, s96.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s96.txt, s96.pdf, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file s96.zip.

(10 pont)

solution, statistics


$Var(Body)

Upload your solutions above