Problem I. 313. (February 2013)

I. 313. Tree rings (or annual rings) are formed in trees living in temperate zones due to the change of seasons. Tree growth is different during the winter and summer, and, for example, adequate moisture or a drought season can both affect the growth and hence the width of a ring, making it possible to study changes in the climate. Dendrochronology is a preferred method by archaeologists to date a particular event. If two trees in the same zone were born even at different times, but they were experiencing the same climate for some period in their lives, then the structure of their rings in that period is similar. By matching several such ring structures, archaeologists can obtain a very precise chronology even after thousands of years.

We are given the ring structure of N trees, that is, the width of their rings within a tolerance of one millimeter. (The techniques on how to make a cross section or how to evaluate these statistically are omitted now.) Since trees can be of different species or ages, when matching the samples, we compare the sequence of ratios of successive ring widths. For example, if the measured ring widths are 6, 4, 2, 8, 5 millimeters in a sample, then the corresponding sequence of ratios is 0.66, 0.50, 4.00, 0.62.

A match between 2 such sequences is considered acceptable, if there are at least 10 successive elements in both sequences such that the corresponding elements differ by at most 1%, moreover, the corresponding remaining elements (until the shorter sequence terminates) are the same. (Notice that you still have a certain freedom in the exact interpretation of this definition.) You should take into account that there can be an acceptable match between several sequences as well. (The input file will contain the ring structure of the oldest tree in its first row.)

Given N ring structure samples, your program i313 should display the maximal number of years (``Lefedett evek szama'' in the sample output) spanned by the appropriate ring structures forming an acceptable match and starting from the oldest tree. Your program should also display the order of these compatible samples (``Mintak sorrendje'' in the sample output).

The command line argument to your program is the name of the input file describing the ring structure data. The first line of this file contains the number of tree samples N (2N50). Then each of the following N lines describes the ring structure of a particular tree: the first value in each row is H (10H500), giving the number of rings of the tree, then H integers follow, describing the width of each successive ring.

The table contains a sample input ``Példa a bemenetre'' and the corresponding output ``Kimenet a képernyőre''.

The source code (i313.pas, i313.cpp, ...) together with a short documentation (i313.txt, i313.pdf, ...) - also describing which developer environment to use for compiling, further a brief description of your solution - should be submitted.

(10 pont)

Deadline expired on March 11, 2013.

Sorry, the solution is available only in Hungarian. Google translation

Megoldásokról:

Minden versenyző észrevette, hogy a feladat kitűzésében szereplő példán a lefedett évek száma téves. Nem 49, hanem 80 év a minták együttes hossza.

Mintamegoldás:

Varga Erik 12. évfolyamos tanuló (Budapest, Berzsenyi Dániel Gimnázium) programját mutatjuk be: i313.cpp

Tesztállományok: teszt.zip

Statistics:

6 students sent a solution.
10 points:	Fehér Balázs, Fényes Balázs, Gema Barnabás, Tegzes Tamás, Varga 256 Erik.
9 points:	Qian Lívia.

Problems in Information Technology of KöMaL, February 2013