|
Adventurer #09
30 апреля 1999 |
|
Exchange of experience - SerzhSoft'a report on the regional Olympiad in Informatics in 1998.
(C) SerzhSoft
OLYMPICS-98
Human nature
oshivayutsya.
Something we absolutely have stopped working
over yourself! : -) All the assembler, so the assembler. How
much can you! It is time to remember the dear BASIC ...
In late March, Perm
held a regional competition on science and mathematics for
PED-VUZ'ov Urals and Western Siberia. Been there, and
author of this article ...
I think many readers will be helpful to look at puzzles
that have offered at the Olympics and remember programming
techniques to spektrumskom BASIC. Not all the time in the codes
poking around, it is necessary that in my head oil was!
So here's a job in computer science and
examples of their solutions on our "native"
BASIC 'e:
---------------------------------------
1. The exact value of the expression.
Make the program calculate the exact znyacheniya n ^ n +
n! (1 <= n <= 100). Restriction on the time of payment - 30.
For example, for n = 13 we get 302881333613053.
(20 points)
10 REM --- BEGIN -
20 INPUT "N ="; N
30 REM --- F $ = N! -
35 LET A $ = "1"
40 FOR I = 2 TO N
50 LET B $ = STR $ I
60 GO SUB 1000
70 NEXT I
1980 LET F $ = A $
90 REM --- N $ = N ^ N - 100 LET A $ = STR $ N: LET B $ = A $
110 FOR I = 2 TO N
120 GO SUB 1000
130 NEXT I
140 LET N $ = A $
150 REM --- C $ = F $ + N $ - 160 LET C $ = F $
170 LET D $ = N $
180 GO SUB 2000
190 PRINT C $
200 STOP
999 REM --- END - 1000 REM --- A $ = A $ * B $ - 1010 LET M $
= A $: LET N $ = B $ 1020 IF LEN A $ <LEN B $ THEN LET M $ = B
$: LET N $ = A $
1025 LET C $ = ""
1030 FOR J = 1 TO LEN N $
1033 LET C $ = C $ + "0"
1035 LET L1 = 0: LET D $ = ""
1040 FOR L = LEN M $ TO 1 STEP -1
1050 LET L1 = L1 + (CODE N $ (J) -48) * (CODE M $ (L)
-48)
1060 LET L2 = INT (L1/10)
1070 LET D $ = CHR $ (L1-L2 * 10 +48) + D $
1080 LET L1 = L2
1090 NEXT L
1095 IF L1> 0 THEN LET D $ = CHR $ (L1 +48) + D $
1100 GO SUB 2000
1110 NEXT J
1120 LET A $ = C $
1999 RETURN
2000 REM --- C $ = C $ + D $ - 2010 LET E $ = D $
2020 IF LEN C $ <LEN D $ THEN LET E $ = C $: LET
C $ = D $
2021 LET C $ = "0" + C $
2025 LET LC = LEN C $: LET LE = LEN E $
2030 LET K = 0: LET K1 = 0
2040 LET K1 = K1 + CODE C $ (LC-K) + CODE E $ (LE-K)
-96
2050 LET K2 = INT (K1/10)
2060 LET C $ (LC-K) = CHR $ (K1-K2 * 10 +48)
2070 LET K1 = K2
2080 LET K = K +1: IF K <LE THEN GO TO 2040
2090 IF K1 = 0 THEN GO TO 2120
2100 LET K1 = K1 + CODE C $ (LC-K) -48
2110 GO TO 2050
2120 IF C $ (1) = "0" THEN LET C $ = C $ (2 TO)
2999 RETURN
----------------------------------------
2. Select the file in Norton Commander.
Panel Norton Commander entirely filled file names (3 to 17
column files in each). Initially, the file is marked in the
column C1 and the line L1. You must move the pointer to the
column line C2 and L2, uspolzuya cursor keys UP (U), down (D),
LEFT (L) and RIGHT (R), as well as BEGIN (B) and END (E),
setting a pointer to first and last files, respectively.
Write a program that introduced
C1, L1, C2, L2 determines what the minimum number of keys you
must press to perform the required movement. Deduce the
sequence of pressing keys in the above-letter
notation. For the convenience of checking in
the sequence of keystrokes
first place team of L and R, then U
and D.
(25 points)
5 REM --- BEGIN -
10 INPUT "C1 ="; C1; ", L1 ="; L1; "; C2 ="; C2;
", L2 ="; L2
20 LET A $="": GO SUB 1000
30 LET B $ = A $
1940 LET C1 = 1: LET L1 = 1: LET A $ = "B": GO SU
B 1000
50 LET C $ = A $
1960 LET C1 = 3: LET L1 = 17: LET A $ = "E": GO S
UB 1000
1970 IF LEN C $ <LEN A $ THEN LET A $ = C $
1980 IF LEN B $ <LEN A $ THEN LET A $ = B $
90 PRINT LEN A $; ":"; A $
99 STOP
999 REM --- END - 1000 REM --- WALKER - 1010 LET I = (C2-C1) *
17 + L2-L1 1020 IF I <-9 THEN LET I = I +17: LET A $ = A $ + "L
": GO TO 1020
1030 IF I> 9 THEN LET I = I-17: LET A $ = A $ + "R"
: GO TO 1030
1040 IF I <0 THEN LET I = I +1: LET A $ = A $ + "U":
GO TO 1040
1050 IF I> 0 THEN LET I = I-1: LET A $ = A $ + "D":
GO TO 1050
1060 RETURN
Tests:
N / N C1 L1 C2 L2 Result
1 1 9 2 13 5: R D D D D
2 3 1 2 4 4: L D D D
3 3 1 1 5 5: B D D D D
4 1 11 2 15 4: E L U U
5 3 17 3 1 2: L D
6 1 1 1 17 2: R U
----------------------------------------
3. The highest amount in the triangle.
The picture shows a triangle
numbers. Write a program that calculates the highest sum of
numbers located on the road, starting at the top of the
triangle and ending at the base of the triangle.
7
March 8
8 1 0
2 7 4 4
4 5 2 6 5
* Every step along the path may be down diagonally to the
left or down diagonally to the right.
* Number of rows in the triangle more
1 and no more than 100.
* The triangle is composed of integers from 0 to 99.
* Time limit for execution
Programme - 30 seconds.
Input. The first number is the number of rows in the
triangle. Initial data are entered in the form of a triangular
matrix, for example:
7
March 8
8 1 0
2 7 4 4
4 5 2 6 5
(25 points)
10 REM --- BEGIN -
15 DIM A (30,30): DIM B (30,30)
20 INPUT "N ="; N
21 FOR I = 1 TO N: FOR J = 1 TO N
22 LET A (I, J) = 0: LET B (I, J) = 0
23 NEXT J: NEXT I
30 FOR I = 1 TO N
35 LET A (I, 1) = 0
40 FOR J = 1 TO I
50 INPUT A (I, J)
60 PRINT A (I, J); "";
70 NEXT J
80 PRINT
90 NEXT I
100 LET B (1,1) = A (1,1)
110 FOR I = 2 TO N
120 FOR J = 1 TO I
130 LET B (I, J) = B (I-1, J) + A (I, J)
140 IF J> 1 THEN IF B (I-1, J-1)> B (I-1, J) TH
EN LET B (I, J) = B (I-1, J-1) + A (I, J)
160 NEXT J
170 NEXT I
180 LET S = 0
190 FOR J = 1 TO N
200 IF B (N, J)> S THEN LET S = B (N, J)
210 NEXT J
220 PRINT "SUM ="; S
999 REM --- END -
Tests:
A) N = 1
5
SUM = 5
2) N = 7
3
February 1
5 3 7
1 2 4 8
9 8 7 6 5
1 2 3 4 5 6
5 6 7 3 8 4 9
SUM = 1939
3) N = 9
1
March 2
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45
SUM = 165
----------------------------------------
4. The numbers in the binary system.
Make a program that prints all binary numbers in the
record which contains exactly M zeros and N units. Numbers
contained in its records insignificant zeros, print is not
required. For example, for M = 2 and N = 3 we get:
11100
11010
11001
10110
10101
10011
(20 points)
10 REM --- BEGIN -
20 INPUT "N ="; N; ", M ="; M
30 LET A $ = ""
40 FOR I = 1 TO N: LET A $ = A $ + "1": NEXT I
50 FOR I = 1 TO M: LET A $ = A $ + "0": NEXT I
60 IF N = 0 OR M = 0 THEN PRINT A $: GO TO 190
80 REM --- LOOP -
90 PRINT A $
100 FOR I = N + M TO 2 STEP -1
110 IF A $ (I) = "1" THEN NEXT I
120 LET K = N + M-I
130 FOR I = I TO 2 STEP -1
140 IF A $ (I) = "0" THEN NEXT I
150 LET A $ (I) = "0"
160 FOR I = I +1 TO I +1 + K: LET A $ (I) = "1": NE
XT I
170 FOR I = I TO N + M: LET A $ (I) = "0": NEXT I
180 IF K +1 <N THEN GO TO 80
190 REM --- END -
Tests:
n = 1 m = 3
1000
n = 2 m = 8 n = 3 m = 3, n = 3 m = 5, n = 4, m = 3
1100000000 111000 11100000 1111000
1010000000 110100 11010000 1110100
1001000000 110010 11001000 1110010
1000100000 110001 11000100 1110001
1000010000 101100 11000010 1101100
1000001000 101010 11000001 1101010
1000000100 101001 10110000 1101001
1000000010 100110 10101000 1100110
1000000001 100101 10100100 1100101
100011 10100010 1100011
n = 2 m = 20 10,100,001 1,011,100
1100000000000000000000 10011000 1011010
1010000000000000000000 10010100 1011001
1001000000000000000000 10010010 1010110
1000100000000000000000 10010001 1010101
1000010000000000000000 10001100 1010011
1000001000000000000000 10001010 1001110
1000000100000000000000 10001001 1001101
1000000010000000000000 10000110 1001011
1000000001000000000000 10000101 1000111
1000000000100000000000 10000011
1000000000010000000000
1000000000001000000000
1000000000000100000000
1000000000000010000000
1000000000000001000000
1000000000000000100000
1000000000000000010000
1000000000000000001000
1000000000000000000100
1000000000000000000010
1000000000000000000001
----------------------------------------
5. Filling the matrix primes by a certain rule
Fill in the matrix of order N (N <= 21)
prime numbers, as indicated in the example.
Filling starts from the bottom
angle and then diagonally to the main
diagonal inclusive. Above the main diagonal are recorded zeros.
Procedure for filling:
16 0 0 0 0 0
15 17 0 0 0 0
7 14 18 0 0 0
6 8 13 19 0 0
2 5 9 12 20 0
1 3 4 10 11 21
For example, for matrices of order N = 10
we have:
199 0 0 0 0 0 0 0 0 0
197 211 0 0 0 0 0 0 0 0
109 193 223 0 0 0 0 0 0 0
107 113 191 227 0 0 0 0 0 0
53 103 127 181 229 0 0 0 0 0
47 59 101 131 179 233 0 0 0 0
17 43 61 97 137 173 239 0 0 0
13 19 41 67 89 139 167 241 0 0
3 11 23 37 71 83 149 163 251 0
2 5 7 29 31 73 79 151 157 257
(10 points)
10 REM --- BEGIN -
20 DIM A (21,21)
30 INPUT N
40 FOR I = 1 TO N
50 FOR J = 1 TO N
60 LET A (I, J) = 0
70 NEXT J
80 NEXT I
90 LET P = 2
100 FOR I = 1 TO N
110 FOR J = 1 TO I
113 IF INT (I / 2) * 2 = I THEN LET A (N-I + J, J) =
P: GO TO 120
115 LET A (N-J +1, I-J +1) = P
120 LET P = P +1
130 LET K = 1
140 LET K = K +1
150 IF INT (P / K) * K = P THEN GO TO 120
160 IF K * K <= P THEN GO TO 140
220 NEXT J
230 NEXT I
240 FOR I = 1 TO N
250 FOR J = 1 TO N
260 PRINT AT I-1, (J-1) * 4; A (I, J)
270 NEXT J
280 NEXT I
999 REM --- END -
Tests:
N = 7
107 0 0 0 0 0 0
53 103 0 0 0 0 0
47 59 101 0 0 0 0
17 43 61 97 0 0 0
13 19 41 67 89 0 0
3 11 23 37 71 83 0
2 5 7 29 31 73 79
----------------------------------------
Well, how? Do not weak, if we consider that
to address all the tasks were given only 4
hours! But in each task should have been
another guess - where there is a "dog rummaged" ...
For example, the fourth task is
nicely solved by using recursion. Here
Example Pascal:
var n, m: byte;
procedure Binary (s: string; n, m: integer);
begin
if n> 0 then Binary (s + '1 ', n-1, m);
if m> 0 then Binary (s + '0 ', n, m-1);
if n + m = 0 then writeln (s);
end;
begin
writeln ('n, m =?'); readln (n, m);
Binary ('1 ', n-1, m);
end.
In the Spectrum - BASIC no procedures
parameters, so we have to use a bloated algorithm ...
The annex to the magazine you can
find all of the above-listed BASIC-program ...
Perhaps you are wondering who won
first place at the Olympics? What a
naive question - of course people from
Perm. Ha, this was to be expected ...
I am not in life can not believe that all problems
"Born" the day before the Olympics. Surely teachers in devising
brainteasers gave their students poreshat
Trial versions, or similar problems.
Another point: the gap from first place
take 100 points is hoo!
After the second place (not Permiakov) - somewhere
about 87 points. And there are already lots of people with
"Off-scale" for 80 points. That is
visible face of an exemplary human capabilities. And the guy
who all of their program has already passed through two and a
half hours (according to witnesses) after
Started (and all toiled four full!) is too painful to some
suspicion. Incidentally, I later made his way to Department and
copied all the decisions of participants. Now I will give a
couple of "quotes" from the source "winner":
First, the file file_id. diz:
"It contains the solution of problems
Nort_'a Browser_'a (EV Bryzgalov) of
PGPU. All tasks are provided with funky comments, which include
the initiation and promotion of the 123 girls and 136 groups.
And yes everyone will be rewarded according to merit
it ...
And the rise of the fallen,
For the righteous was his work,
And grace will descend on him,
So that he could complete They started ...
(_Nort Browser, 2587_) "
Further, some typical statements
of the solutions to that "friend":
task1.pas:
"(C) Nort Browser 'Co.
Duke Nukem Must Die!!!
Blessed memory stealth arithmetic and AP
Shestakova dedicated ... And you know what
136 group is studying a wonderful girl
Olya Chistyakova ... "
task2.pas:
"(C) Nort Browser 'Co.
Duke Nukem Must Die!!!
Validations there!
Blessed memory grasshopper Executive is dedicated to ... Did
you know that in the 123 group learns a wonderful girl - Olga
Pepelyayev ... "
Very wary the next line: "writeln ('As you can easily see,
just click', length (p1), ' Time (s) and do not spoil the rat!
') "
task3.pas:
"(C) Nort Browser 'Co.
Duke Nukem Must Die!!!
Blessed memory, and problem book MaksUeya Semakina dedicated
... And you know that in 123 group learns a wonderful girl -
Lena Kuzmina ... "
task4.pas:
"(C) Nort Browser 'Co.
Duke Nukem Must Die!!!
Blessed memory of last year's Olympic Games and
SSC is dedicated to ... SWV - Konstantin Volkov - friend and
colleague of the author solutions ... "
task5.pas:
"(C) Nort Browser 'Co.
Duke Nukem Must Die!!!
Ulam spiral of blessed memory is dedicated to .. Did you know
that in 136 the group learns wonderful girl - Light Voloshin
... "
Next: "write ('Enter N
(If you do not flagellant, then do not enter
21) '); "
Few comments ... I think you
agree that in a tense situation
Olympics, when the time might not be enough
even to perform tasks, very few people in sharahnet head off so
perverted (if generally someone will come!). For such
"Literary arrivals" should have a bunch of
free time. It seems people uzhastno mayalsya, not knowing what
would be done hence the conclusion that the
decision had already been prepared in advance,
or proreshany inside out eve ... Still,
necessary to have a great impertinence to
write such perversions, knowing that later
they will be reviewed by the commission ...
It follows that the boy was all
100% sure that its programs are working
properly beforehand what to say no other party could not!
By the way, the Mathematical Olympiad
This "writer" took 2 nd place! Probably
the jury decided that the first two places - it's
so it will be too blatantly and obviously ... : -)
We can not, of course, completely exclude
the possibility that the guy is a super-genius ... But
something to believe in it, gently speaking - hard to!
With best wishes,
Serzh.
Other articles:
Similar articles:
В этот день... 21 November