Exercises and problems in Informatics September 2002

Please read The Conditions of the Problem Solving Competition.

I. 28. It is well known that every permutation can be decomposed into independent cycles, where, as usual, the cycle (i₁,...,i_k) means that the i₁^th element should be moved into the i₂^th, the i₂^th element to the i₃^th,..., the i_k-1^th element to the i_k^th position, finally the i_k^th element to the i₁^th position to sort those elements in the canonical order. For example, the permutation (4,3,2,7,5,1,6) of the numbers (1,2,3,4,5,6,7) can be decomposed into 3 cycles: (1,4,7,6), (2,3), (5), meaning that in order to recover the original canonical order, the first element should be moved to the fourth position, the fourth element to the seventh position, and so on. Your program (I28.pas, ...) should read a number N and a permutation of the first N positive integers, then list the independent cycles which sort that permutation into ascending order. (10 points)

I. 29. A disc is given by its centre and its radius. We cut out parts from the disc either by removing a sector (beginning at ALPHA degrees relative to the north direction clockwise and with angle BETA degrees), or by removing a ring (with inner radius B and outer radius K). Your program (I29.pas, ...) should apply a given number of these operations to a disc, and draw the remaining figures in each step. The example in the figure shows the stepwise results of the operations. (10 points)

Disc(150,150,100)	Sector(0,30)	Ring(10,20)	Sector(120,45)	Ring(50,75)

I. 30. Binomial coefficients can be arranged in the usual Pascal's triangle pattern (see the figure), in which every element -- with the exception of the outermost ones -- is the sum of its upper and upper-left neighbours. Prepare your Excel sheet (I30.xls) which gives the first 50 rows of Pascal's triangle. It is important that the size of the table should be 50x50 cells, every cell should contain the result of the same formula, and the first element should be placed in cell B2.

Note that this problem is quite similar to the last year's one I. 9., but the requirements are now different, so the solution of that problem will not be accepted. (10 points)

Send your solutions to the following e-mail address:

infotech@komal.elte.hu.

Deadline: 13 October 2002