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 2014

Please read the rules of the competition.


Show/hide problems of signs:


Problems with sign 'I'

Deadline expired on March 10, 2014.


I. 340. A group of friends had an online meeting in a closed chat room during a weekend afternoon. The chat room was opened at 13:00, and each conversation took place between two people, but a member could simultaneously participate in more conversations. The list of participants was stored in the chat program in advance. Then, after the room opened and for each conversation, the name of the person initiating the conversation, their partner's name, and the time when the conversation started and ended were recorded. These data can be downloaded from our web page and found in the file cseveges.txt.

The first line of the file contains the number of participants N (2\leN\le20). The next N lines contain the list of participants (individual names do not contain space characters). The following line contains the number of conversations M (2\leM\le1000). Then each of the following M lines contains two numbers (BEBV) and two names (B1, B2). The first number, BE (0\leBE\le720) describes the number of minutes from the room opening until the start of the actual conversation, while the second number, BV (BE\leBV\le720) is the number of minutes from the room opening until the end of the conversation. The first name (B1) is the name of the person initiating the conversation, and B2 is the partner's name.

Example.

Your program i340 should solve the following tasks.

The number of the actual task (e.g., Task #3:) should be displayed before the result whenever there is output to the screen. If user input is expected, a message briefly describing the input should also be displayed first (e.g., Enter the name of participants:). Diacritical marks in the output may be omitted.

1. Load and store the data from the file cseveges.txt in a form suitable to solve the following tasks.

2. Display on the screen the average duration of the conversations rounded to 2 decimal digits of precision.

3. Prompt the user to enter the name of a participant, then display his or her total conversation time.

4. Count the number of occurrences of the event that a person called a friend, and after the conversation was over, the original caller again initiated a conversation with the same friend but without chatting to anyone else in the meantime.

5. Collect and display on the screen all the people who did not make any conversation.

6. Display the starting and ending time of the longest interval during which no conversation occurred.

7. For each hour after the opening of the chat room, determine the number of different people having a conversation during that hour. (A conversation can belong to several such blocks of length of 1 hour.)

8. Determine the time instant (or a time instant, if there were more) when the number of participants in different conversations was maximal.

9. List the people having the longest conversation with each other.

The source code (i340.pas, i340.cpp, ...) of your program and its brief documentation (i340.txt, i340.pdf, ...) should be submitted, also specifying the name of the developer environment to use for compiling your source.

Downloadable file: cseveges.txt

(10 pont)

solution (in Hungarian), statistics


I. 341. Most large cities have extensive public transportation networks. Many vehicles have been converted to use electricity because of environmental protection. However, a vehicle operating on a dedicated track can sometimes be disadvantageous because, for example, a malfunctioning tram can disrupt the traffic, or one vehicle cannot overtake the other.

Your task is to simulate a tram transportation system.

Since there can be large fluctuations in the traffic or in the number of travellers even during one day, our model is restricted to a simpler homogeneous time period.

The file megallo.txt obtained from the city transportation company contains data for each station such as

\bullet the travel time between consecutive stations (t_{\rm{meg\'all\'o}}), provided that the traffic is smooth;

\bullet the maximal extra time needed to cover the distance between two consecutive stations due to traffic lights or heavy traffic, during the corresponding time period in the last year (tplusz);

\bullet the average number of passengers arriving at the actual station in every minute to get on the vehicles (fel);

\bullet the percentage of the passengers getting off at the actual station (lesz).

Besides the above, we know the starting time of the first vehicle (for example, 8:00), the time difference between consecutive vehicles (for example, 0:10), finally, the time for a passenger to get on or off a vehicle (for example, 0:00:01). Other factors that would modify the schedule are neglected in this task.

Create a sheet to investigate 5 consecutive vehicles in the following way:

\bullet a station sheet should contain the data from the file megallo.txt;

\bullet a test sheet should compute the following data for each vehicle and each station: the arrival time, the number of people getting off the vehicle, the number of people getting on the vehicle, the total time to get off and on, and the departure time;

o the number of people getting on the first vehicle should be based on the time difference between consecutive vehicles, while the number of people getting on the later vehicles should be based on the time elapsed since the arrival of the last vehicle;

o the extra time between the stations can be any random number between 0 and the given maximal extra time;

o the number of people getting off and on can randomly deviate from the given values by at most 20 percent (calculations with non-integer number of passengers are also allowed);

o take into consideration (when dealing with the arrival times) that a vehicle cannot overtake another vehicle;

\bullet create a diagram to display the time difference between consecutive vehicles for each station with respect to the initial time difference;

\bullet your solution should recompute the appropriate data if changes are made in the starting times, in the time differences, in the passenger exchange rates, or in other station properties.

After creating your sheet, try and determine the modification of which parameter (or parameters) the system is the most sensitive to.

Your sheet (i341.xls, i341.ods, ...) containing the solution should be submitted containing a short documentation (i341.txt, i341.pdf, ...) together with a description about parameter dependence and sensitivity, and the name and version number of the spreadsheet application used.

Downloadable file: megallo.txt

(10 pont)

solution (in Hungarian), statistics


I. 342. The international project ChronoZoom (http://www.chronozoom.com) dynamically visualizes various events on different time scales. The page is based on the HTML5 language. Collections such as images, videos or articles can be attached to the events of the time scales. An interesting feature is that these scales can be dynamically zoomed in and out to overview different eras of time. Time scales can be embedded into other ones iteratively.

Create your own timeline to illustrate the history of a scientific discipline belonging to the profile of our journal KöMaL. Your work should contain several sub-timelines, even if collections are not necessarily attached to them. Your completed collections should contain various documents together with their (electronic or paper-based) sources if possible.

You will find information about the basic editing processes on the video sharing sites. As for the content, we recommend, for example, the book A fizika kultúrtörténete by Károly Simonyi.

Your document (i342.txt, i342.pdf, ...) should be submitted, containing a link to your timeline and listing the sources used for creating the content and the corresponding dates of the discipline.

(10 pont)

solution (in Hungarian), statistics


Problems with sign 'S'

Deadline expired on March 10, 2014.


S. 87. A group called Reformers of Mathematics made a huge discovery and created a new definition. The New Greatest Common Divisor, henceforth abbreviated as ngcd, of a finite sequence of natural numbers is defined as the number of elements of the sequence multiplied by the old-fashioned gcd of the sequence. The Reformers of Mathematics immediately give you the following task.

You are given a sequence of positive integers (a1,...,aN) with 1 \le N \le
100\;000. Determine the maximal possible ngcd over all subsequences formed by any consecutive elements of the original sequence.

Your program should read the value of N from the first line of the standard input, then the numbers ai (1\leai\le1011) from the next line. The first and only line of the standard output should contain the maximal positive integer that represents the ngcd of a connected subsequence of the given sequence.

In the example, ``Példa bemenet'' and ``Példa kimenet'' denote a sample input and output, respectively.

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. Partial points can be obtained if your program yields a solution for N\le200, or for N\le5000.

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

(10 pont)

solution (in Hungarian), statistics


$Var(Body)

Upload your solutions above