|
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
Other articles:
Similar articles: