KöMaL Problems in Informatics, May 2005
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'
Deadline expired on June 15, 2005.
I. 106. Write a program to represent graphs using modifiable diagrams. Upon pressing the left mouse button, the program should display the current point under the cursor, while if one presses the right button, the point under the cursor should be displayed together with the line segment connecting the actual point and the previous one (so one can draw an edge, paths or cycles). A menu should appear on the right part of the screen consisting of squares of equal size (i.e. command buttons) with the following functions:
- an END button at the lower part of the screen
- 3 buttons at the top, in one group, each containing a disc, representing low, medium and high precision of mouse clicks: when adding vertices to the graph, two points will be considered the same if their distance is less than the radius of the currently selected disc (The default precision at the start of the program should be ``medium''.)
- 2 buttons in the middle, in one group, one for DRAWING MODE (being the default one, when the program works as described above), and the other for MODIFICATION (this time one can drag a vertex of the graph to a new location by holding down the left mouse button, and meanwhile the program continuously redraws the adjoining edges of this ``rubber-edged'' graph)
- an UNDO button.
Your executable program (i106.exe) and its (Pascal or C) source code (i106.pas, ...) are to be submitted.
I. 107. Suppose that there is an array with m+n elements in the memory (m and n are positive integers). Your task is to interchange the first n elements of the array with the last m elements - without using up any more memory. (The usage of some auxiliary variables is, however, allowed.) Neither the ordering of the first n elements, nor that of the last m elements should change during the process.
The precise and detailed description of your algorithm is to be submitted (i107.txt, together with the spreadsheet computing typical values of the auxiliary variables (i107.xls).
I. 108. Banking accounts of customers are uniquely represented by natural numbers. Every banking account has a balance, being an integer. Daily transactions of customers are stored in an ordered sequential file, where the monotone increasing ordering corresponds to the accounts' identification numbers. Possible transactions include: recording of a new customer with a given starting balance, deleting a customer, or changing the balance of a customer with a given amount.
Determine the new bookkeeping of the banking accounts at the end of the day. Your program should be submitted (i108.pas, ...).
Problems with sign 'S'
Deadline expired on June 15, 2005.
S. 9. Nowadays one can easily download DNA samples from the Internet. Such a sample consists of combinations of letters A, C, T and G, that is, the abbreviations of the four nucleotide bases adenine, cytosine, guanine and thymine.
Your task is to locate a given sequence (a ``gene'') in the given sample of letters A, C, T or G. The sample and the sequence are given in two text files. The first row of each file contains the number of letters, then the sample (or the sequence) itself of letters A, C, T, G follows. For the sake of readability, the lines are wrapped to have at most 100 characters.
Your program gets the necessary file names from the command line: first the name of the sample file, then the name of the file containing the desired sequence will be given. Your program should send a 0 to the standard output, if the sample does not contain the sequence, otherwise the output should be i, if the first occurrence of the sequence in the sample begins at the ith position. (Positions are numbered from 1.)
It can be assumed that the sample has at most 50 million characters, while the sequence consists of at most 1 million characters.
Upload your solutions above