KöMaL Problems in Informatics, October 2005

Problems with sign 'I' Deadline expired on November 15, 2005.

I. 112. Some unknown real numbers (at most 10) are denoted by the first few letters of the alphabet. The greater member of certain pairs of numbers is given. You should order the variables such that all given inequalities are satisfied. If there is no such ordering, print ``No solution''.

Your program should read the given relations from the standard input. Each line will contain a single inequality, without spaces between the variables and inequality sign.

The output should contain a possible ordering of the numbers in the same format as in the example.

C<A<B<D

The source code of the program (i112.pas, i112.c, ...) should be submitted.

(10 pont)

statistics

I. 113. A cardioid is obtained as the locus of a point P on the rim of a circle l that rolls without skidding along the circumference of another circle k with the same radius. (See Figure.)

Construct a cardioid using the ``trace'' feature of the program Euklides. The final worksheet in Euklides's own file format (I113.euk) is to be submitted.

(10 pont)

statistics

I. 114. There are foxes and rabbits living on an island. The reproductive rabbit population increases by m percent in each month. However, foxes prey on the rabbits: one fox eats p percent of the total rabbit population in each month -- provided that there are enough rabbits. The fox population increases proportionally to the available food: in every month each rabbit accounts for n percent of them giving birth to a baby fox, but q percent of the total fox population dies.

Make an Excel sheet into which the values of n, m, p, q and the population sizes in the first month can be entered, then it computes the population sizes in the following 60 months. If meanwhile any (or both) species became extinct, the program should mark the name of that species red. You should also make two plots, the first one representing the sizes of the two populations as a function of time, while the second one graphing the ratio of the populations.

The sheet (i114.xls) should be submitted.

(10 pont)

solution, statistics

Problems with sign 'S' Deadline expired on November 15, 2005.

S. 11. We often categorize things according to various properties and look for relations among them. Write a program to make logical deductions among properties.

The program should read the input from the keyboard (or standard input): each line will contain a proposition or a question. The program should answer them in the next line on the screen (or standard output).

Propositions or questions refer to various properties. An elementary property consists of a single word, e.g., small or red. Every word is considered as an elementary property, except for the following ones: NOT EXIST, EXIST, AND, OR, NOT, IF and THEN.

Negation of an elementary property is formed by attaching the prefix NOT, e.g., the negation of red is NOT RED.

Compound properties are formed by joining some elementary properties or negations of elementary properties using the words AND or OR, e.g., small AND NOT red. However, mixing these conjunctive words, as in big AND red OR blue, is not allowed.

Three types of propositions are allowed with the following syntax:

   EXIST (property)

   NOT EXIST (property)

   IF (property) THEN (property)

A question is formed by putting a question mark at the end of a proposition.

The program should give any of the following answers to a given proposition:

   UNDERSTOOD if the proposition corresponds to a new piece of information

   I KNOW if the proposition is a consequence of earlier ones

   CONTRADICTION (the program should ignore these propositions)

   I DO NOT UNDERSTAND if the input is syntactically incorrect

The program should reply to a question with

   YES, or NOT EXIST if the question referred to a true proposition

   NO, or BUT EXIST if the question referred to a false proposition

   I DO NOT KNOW if the answer might be true or false

The program runs until the user aborts it. You may assume that the number of elementary properties is at most 8 and the input consists of at most lines. Upper and lower case letters should be considered equal. Every character which is not a letter or question mark should be considered as ``space''.

Example (answers of the computer are in italics):

The source code (s11.pas, s11.c, ...) of the program should be submitted.

(10 pont)

solution (in Hungarian), statistics