Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

KöMaL Problems in Informatics, November 2005

Please read the rules of the competition.

Show/hide problems of signs:

Problems with sign 'I'

Deadline expired on December 15, 2005.

I. 115. It is well-known that every rational number x can uniquely be represented as a finite continued fraction:

x=a_0+ \frac1{a_1+ \frac1{a_2+\dots+\frac{1}{a_n}}}\,,

where a0 is an integer, and a1,...,an are positive integers, further an>1. The terms of the continued fraction are obtained by a simple greedy algorithm. Number a0 can only be the integer part of x. If x is an integer, then we are ready. Otherwise, if x is not an integer, we have x=a_0+\frac 1y, with y=\frac 1{\{x\}}, and now we have to find a representation only for y.

Write a program that converts ordinary fractions into their continued fraction form.

The program should read the ordinary fractions from the standard input (i.e. from the keyboard). Every line will contain a fraction of the form a/b, where a and b are integers with at most 4 digits. Your program should display the continued fraction representation of these numbers on the standard output (i.e. on the monitor), using parentheses as in the example. Your program should stop if the standard input can not be read (``end of file''), or the input is an empty line.

See the example.

The source code of your program (i115.pas, i115.c, ...) should be submitted.

(10 pont)

statistics

I. 116. Regular triangular or hexagonal tiling of surfaces is a characteristic feature of Arabic ornaments.

Using the program Comenius Logo, PC Logo or NetLogo, prepare a tiling of a rectangle with two-coloured tiles seen in the figure. The size of the rectangle is specified by the number of tiles in the first row, and the number of rows. (Every second row contains one less tile!) Further parameters of the program are the two colours and the circumradius of the hexagonal base tile.

The final Logo project (i116.lgp) should be submitted containing a procedure tiling. Its 5 parameters, in order, are the radius, the first and second colour, and the number of columns and rows.

(10 pont)

solution (in Hungarian), statistics

I. 117. Four teams compete in a football tournament. Each team plays two matches with every other team. Prepare a sheet, as in the figure, to determine the standing of the tournament.

A winning team is awarded 3 points, while one point is awarded in case of a draw. No points will be awarded for a lost match. You should compute for every team the number of played, won, drawn and lost matches, respectively, further, the total points awarded and the goal rate.

Example:

You can use formulae and spreadsheet functions to compute values in the coloured cells.

The sheet (i117.xls, i117.sxc, ...) should be submitted.

(10 pont)

solution (in Hungarian), statistics

Problems with sign 'S'

Deadline expired on December 15, 2005.

S. 12. A typical mistyping occurs when we hit two adjacent keys on the keyboard instead of the required one. Write a program to automatically correct these errors using a dictionary and a keyboard-layout.

The text will consist of lower-case letters of the English alphabet, with maximal length of 1 000 000 words. Words are separated by spaces, but there is no line break. The maximal length of a word is 30 characters (without mistypings), and each word can contain at most 5 mistypings. The order of the correct and unwanted letters in a mistyped word is not specified, all we know is that these letters are adjacent. Spaces are not mistyped. If a word can be corrected in more than one way, your program should choose that version which requires deleting the least number of letters. (If there is still more than one possibility, choose the first appropriate word in the alphabet.)

The dictionary and the keyboard layout are contained in a single file. The first part of the file contains the keyboard layout: the first letter in each row is followed by its neighbouring letters on the keyboard, separated by a space. The layout ends in an empty line. Next comes the dictionary, having a single word in each row in alphabetical order. The maximal number of words is 1 000 000.

Names of the input files will be given in the command line, first the file name containing the actual text, then the dictionary. The output of your program should be written to a file whose name is the given third parameter.

Example:

(10 pont)

solution (in Hungarian), statistics

$Var(Body)

Upload your solutions above