ZX Club #06 31 декабря 1997

Тусовка

News - Barnaul Olympiad in Informatics 1997.

         Olympiad in Informatics



   In November 1997, as every year,
held Olympiad in Informatics.
Took part in almost all schools. Despite
that the targets were all the same,
scores were set by each team the Jury
in different ways! Me ERASER'a, was surprised when
101 per school all the tasks set by one score !?!?!? Results of 
this Olympiad appropriate. But we go from sad to more 
enjoyable. For those who are interested poreshat or just watch 
the Olympiad problem, given such an opportunity:



     Problem I tour kravevoy Olympics



   1.If a person standing in line in front
You were taller than a man standing after
the man who stood in front of you
it was a man standing in front of you
above you?


   2.Tekst encrypted using the table:
each figure corresponds one of the three
letters located underneath the table, and
sign "*" space or one of the letters "w", "me."


      Transcribe the following text:

5343934 * 150413 * 6 * 8156215044414 305041080 **


0 1 2 3 4 5 6 7 8 9 *

and r and d m n t s w s w

The map is given by p y p u b I

in e and l for c = h b e



   3.Chetyre turtles, which are in
vertices of a square with sides  pixels
begin to move simultaneously with a constant speed on delichine 
<v>, with the first turtle is heading to the second, second - 
the third, the third - the fourth, fourth - the first one. Draw 
path the movement of turtles at different ratios

between  and <v>. Display the trajectory of turtles.


   4.Pust A - 2n-zanchnoe number (first
figure is not 0). We call the number A - particularly if it is 
itself a perfect square and number, formed its first n-digits

and its last n-digits are also
perfect square (the second number
may begin with the digit 0, but should not
be zero). Such a number, for example,
yavlvetsya number 49.


   a) Find all two-digit and four-digit special numbers;

   b) Show that there exists at least
dvadtsatizanchnoe one particular number.


   5.Na algorithmic language written in a arithmetic 
expression. Create a program that displays a message on the 
availability of syntactic errors in record of this expression. 
For example, the expression 23 + 76 is not correct. 


   (1) To write arithmetic expressions
uses only the signs of arithmetic
operations and numbers.

   (2) Restrictions on the use kakihlibo arifmeticheksih 
characters missing. 


   6.Sobralsya Ivan Tsarevich to fight with
Serpent, Dragon, and the three-headed trehhvostym.
"Here's your sword kladenets - says he
Baba-Yaga. - At a stroke, you can cut down
Snake or a head or two heads,
or a tail or two tails. Remember:
cut their heads - a new grow, cut
Tail - Two new grow, cut two
tail - head to grow, cut two heads - nothing will grow. 
"Compose prorammu simulation battle Ivan Tsarevich. 


   Find a solution in which:

   (1) Ivan Tsarevich wins Serpent Horyn
   cha.

   (2) Serpent Dragon defeats Ivan King
   vich.

   (3) What is the optimal model of the battlefield (for

   What is the least number of strokes

   Ivan Tsarevich can cut down all of the Snake
   lovy and all the tails).


   7.Na competitions in the billiard room
participants were required to expand the balls in a pyramid, 
from the heaviest to the smallest weight. Prize was awarded to 
one participant who completed the task faster. He used a method 
called heapsort. Perform this task, using this algorithm.


Algorithm:
Suppose we are given an array of S (1), S (2 ),..., S (n) (1)
Pyramid is called a non-empty sequence of elements (1)
form S (p), S (p +1 ),..., S (p) (1 <= p <= q <= n)
for which one of the following
conditions.
1) 2p> q
2) 2p = q and S (p)> = S (q)
3) 2p <q, and

           S (j)> = S (2j) (p <= j <= q / 2)

           S (j)> = S (2j +1) (p <= j <= (q-1) / 2)
From the definition statement:
1.For any sequence (1) subsequence

       S (n2 +1), S (n2 +2 ),..., S (n)
is a pyramid. Sign denotes
integer division.
2.If the sequence (1)-pyramid, the

       S (1)> = max S (j)

              1 <= j <= n
3.If the sequence (1)-pyramid, the
the value of any node is not less than the value of its left 
and right descendants. Example: Sequence 90,70,11,8,3,9,

7,5,6,1,2 - is a pyramid.


       90 Explanation:

      / 90 has no children: 70 and 11

     70 11 70 has no children: 8 and 3

     / / 11 has no children: 9 and 7

    / 9 7 8, no children: 5 and 6

   8 3 3, has descendants: 1 and 2

  / /
 5 6 1 2

Algorithm for constructing heapsort:
Stage I. The construction of the pyramid. In (1) "tail"
ie subsequence

        S (n2 +1), S (n2 +2 ),... S (n) (4)
As we have noted, is a pyramid.
Will increase (4), by adding thereto the remaining elements of 
(1). Let S (j +1), S (j +2 ),..., S (n)-pyramid. We ascribe to 
it left element of S (j):


       S (j), S (j +1 ),..., S (n)
and transform (5) again in a pyramid. For
This "proseem" S (j) of the corresponding
twig. Here's how. Consider S (j)
and his two offspring S (2j) and S (2j +1). If
S (j) no fewer offspring, then the computation
stop, since (5) is a pyramid. Otherwise, the value of trades S 
(j) and max (S (2j), S (2j +1)) in their respective positions 
and "delete" elements continue sift in the same way. At the end 
of ends of the transformed sequence

(5) becomes a pyramid.

   Continuing the build-up (5), turn
the entire array (1) in a pyramid. If it turns out that 
inequality (3). 

   Obyavlvem residency pyramid of the current S
and proceed to the next stage.
Phase II. Sort of a pyramid. In the current
Pyramid S first element is not less than the others. Proceed 
with the case. Swap the values ​​of the terminal elements of S 
and shorten S right at 1. The resulting sequence

already may not be a pyramid. Apply to
her process of "screening" for the element
S (1), as described in phase I. The transformed sequence S is a 
pyramid. Repeating Stage II (n-1) times, sort S in increasing 
order. 


   8.Ne allowing the gap ('not otvyvaya ka
   randasha from the paper ') and not passing twice

   one draw the line n-pyatikonech
   GOVERNMENTAL stars. Display.


       _ / __ / __ / __ / __ / __ / __ / _

         / / / / / / /

        / / / / / / /


   9.Sostavit recursive algorithm for drawing circles to the 
following: a central circle of radius R, on this circle are 4 
symmetrical circle of radius R / 2 each. On each of the these 4 
circles are under construction 4 - the same way. Etc. Drawing 
be terminated if the radius of the last circle becomes smaller 
than a certain number of <k>. 


                                    ERASER