KöMaL Problems in Informatics, October 2013
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on November 11, 2013.
I. 328. During a criminal investigation a detective is interviewing some witnesses. Your task is to reveal if there is any logical contradiction in the statements made by the witnesses. To this end, you should create a program to process (not sentences but) expressions consisting of logical operations (the ``not'', ``and'', ``or'' and ``implies'' operations, denoted by the !, &, |, and > symbols, respectively) and the first 10 letters of the English alphabet. The operator precedence is the usual one in mathematics or in computer programming; the precedence can be modified by parentheses.
Each line of the input file contains an expression; each such expression is a true statement made by a witness. The first line of the output file should contain the line number of the input file such that its corresponding statement contradicts the earlier ones. If there is no contradiction, the first line of the output file should be ``0''. In the example, ``Bemenet'' is an input, while ``Kimenet'' is the corresponding output. The first command line argument to your program is the name of the input file, while the second parameter is the name of the output file.
The source code (i328.pas, i328.cpp, ...) together with a short documentation (i328.txt, i328.pdf, ...) - describing your solution and the developer environment to use for compiling your source code - should be submitted.
I. 329. In a certain section of a city, a truck transfers products between some stores. The city is Manhattan-like, because it consists of streets that are perpendicular to each other. The store addresses and a sample daily path of the truck are contained in the file szallitolevel.txt, downloadable from our homepage. The address list contains for each store its number (``Üzlet sorszáma''), its name (``Üzlet neve'') and its coordinates on the map expressed in meters (``x (m)'' and ``y (m)''). The daily path contains the number of stores to be visited in the given order (``Napi sorrend''). The truck can visit a particular store more than once a day, or it can return to the company premises (``Telephely'') several times. By using a spreadsheet application, you should solve the following tasks showing some statistics about the daily transfers.
During the solution, you should take into account the following.
- Auxiliary computations can be performed only to the right of column M.
- If possible, use formulae, functions and links.
1. Load the UTF-8 encoded and tabulator separated text file szallitolevel.txt into the sheet beginning with cell A1. Save your work as i329 in the default file format of the application.
The range A1:D34 contains the store address list. Cells below cell F2 can contain the store numbers to be visited by the truck in the given order during the actual day. This list can change daily. The number of stores to be visited each day is at most 30.
2. To help the truck driver, you should determine the store names (``Nevek'') from the address list in the range G2:G31, and the distances (``Táv (m)'') between consecutive stores in the range H2:H30. The distance between two stores with coordinates (x1,y1) and (x2,y2) is the Manhattan distance |x1-x2|+|y1-y2|. If there are empty cells in the F column under ``Napi sorrend'' (because the number of stores to be visited is less than 30 that day), then the corresponding cells in ``Nevek'' and ``Táv (m)'' should also remain empty.
3. In cell K2, compute the total distance covered by the truck during the actual day (``Napi úthossz''). This distance measured in km should be rounded up to the nearest integer, and a ``km'' unit should be displayed.
4. In cell K3, you should determine the distance between the two most distant stores (``Legnagyobb táv''), rounded up in km. Cells K4 and L4 should contain the name of these two stores (``Üzletek között'').
5. Cell K5 should contain the number of the longest path between the above two stores in the daily plan (``Hányadik'').
6. Format the spreadsheet cells according to the sample.
7. The daily path of the truck should be visualized in an XY diagram such that the turning points should also be visible. The path of the truck between two stores always begins with a horizontal segment (i.e., it starts in the x direction), then a left or right turn follows, and ends in a vertical segment. As a preparation for displaying the diagram, you should perform auxiliary computations or introduce auxiliary coordinates.
8. The above XY diagram should be placed on a separate sheet. The points representing stores and the turning points should be joined. Some other requirements are described below.
- No legend should be displayed in the diagram.
- The title of the diagram should be ``Daily path'' (``Napi útvonal'').
- The horizontal and vertical values on the axes should be displayed in the range between -11000 and +11000 m.
- Locate the point on the diagram representing the company premises and change its color to one different from the others.
The spreadsheet (i329.xls, i329.ods, ...) together with a short documentation (i329.txt, i329.pdf, ...) - also containing the name and version number of the spreadsheet application - should be submitted.
Scoring: proper solution of the first 6 tasks is worth 7 points, while solution of the last two problems (exceeding the difficulty level of a secondary school final exam) is worth 3 points.
Downloadable file: szallito.txt
I. 330. Infographics are combination of images, figures and text, but an infographic is more complex than a simple image or figure, and conveys more information than a piece of text.
The aim of infographics is to present information in a concise and clear way. The following link for example contains several nicely designed and attractive infographics: http://www.1stwebdesigner.com/inspiration/beautiful-infographics/.
Besides various education regulations, the local pedagogical program of a school describes, among others, the number of lessons for each subject and each class.
Your task is to visualize the pedagogical program describing the educational system of a school by using an infographic. You can omit some details of the pedagogical program, for example, you may focus only on a specific class type, or on a specific grade, or you can highlight subjects with extra hours beyond regular curriculum - it is your decision which aspects to emphasize on a visually appealing infographic.
The final infographic together with a short documentation (i330.txt, i330.pdf, ...) - also containing the software tools used and the URL of the pedagogical program of your school - should be submitted in a compressed file (i330.zip).
Problems with sign 'S'
Deadline expired on November 11, 2013.
S. 83. A chocolate bar having N rows, M columns and consisting of identical smaller squares is to be distributed among NM children in a way that everybody gets exactly one square: the chocolate bar lying on the table should be broken into pieces. After we break the bar along a row or a column, the pieces are put back into their original position. However, there is a cost for each breaking: the cost for breaking the chocolate between column i and column i+1 is oi, while the cost for breaking between row j and row j+1 is sj. This rule applies to each individual piece on the table; breaking other separate pieces later (even along the same row or column) will again have the appropriate cost. During the breaking process, every piece stays at their original position, they should not be moved away so that the cost would be less, or should not be stacked on top of each other so that they would be broken simultaneously. Each breaking should take place parallel to the sides of the chocolate bar.
Your program should give the minimal cost for breaking the chocolate into 1x1 squares according to the above rules.
Your program should read the values of M and N (M,N500.000) from the first line of the standard input, then the oi integers from the next M-1 lines, finally, the si integers from the last N-1 lines. The minimal cost should appear in the first (and only) line of the standard output.
The example shows a sample input (``Példa bemenet'') and the corresponding output (``Példa kimenet''). Explanation: breaking the chocolate bar first along the rows then along the columns, the cost would be s1+s2+s3+4.(o1+o2+o3+o4+o5)=7+4.11=51, but this is not optimal.
Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution; 9 further points can be obtained provided that your program solves any arbitrary valid input within 1 second of running time.
Partial points can be obtained according to the following:
- your program yields a solution for M,N5,
- your program yields a solution for M,N50,
- your program yields a solution for M,N500,
- your program yields a solution for M,N1000.
The source code (s83.pas, s83.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s83.txt, s83.pdf, ...) - also describing which developer environment to use for compiling the source - should be submitted in a compressed file s83.zip.
Upload your solutions above