KöMaL - Középiskolai Matematikai és Fizikai Lapok
 Magyar
Information
Contest
Journal
Articles
Contest Rules
Entry Form
Problems
Results
Previous years

 

Exercises and problems in Informatics
May 2004

Please read The Conditions of the Problem Solving Competition.

I. 79. A Pierce sequence of order N is the monotonic increasing sequence of nonnegative fractions such that each denominator is at most N. (Fractions having the same value in the list are placed in order of decreasing denominators.) Write a program (i79.pas, ...) that computes a Pierce sequence of order N with terms not exceeding M (1\(\displaystyle \le\)M \(\displaystyle \le\)100, 1\(\displaystyle \le\)N \(\displaystyle \le\)100 with integer N).

Example: if N=2 and M=3, then the corresponding Pierce sequence is

\(\displaystyle \frac{0}{2},\ \frac{0}{1},\ \frac{1}{2},\ \frac{2}{2},\ \frac{1}{1},\ \frac{3}{2},\ \frac{4}{2},\ \frac{2}{1},\ \frac{5}{2},\ \frac{6}{2},\ \frac{3}{1}. \)

(10 points)

I. 80. Write a program (i80.pas, ...) that reads the coordinates of N vertices of a polygon (3\(\displaystyle \le\)N\(\displaystyle \le\)100 and all coordinates are integers between 0 and 500), then displays a triangulation of the polygon (using any method), see the example with N=12.

(10 points)

I. 81. Prepare a worksheet (i81.xls) that displays Eulerian numbers E(n,k) of the second kind in n+1 rows, if the value of n is written into cell A1.

E(n,k) can be computed in the following way. First take all permutations of the sequence {1,1,2,2,...,n,n} with the property that between the two occurrences of any number m there are no numbers below m. Then E(n,k) is the number of the permutations above containing exactly k increasing subsequences.

n\k 0123456 7 8 910
01          
110         
2120        
31860       
412258240      
51523284441200     
611141452440037087200    
71240561032120581403398450400   

(10 points)


Send your solutions to the following e-mail address:

Deadline: 13 June 2004

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley