Текст районной/городской олимпиады по информатике

2005–2006 уч. года

15 декабря 2005 года

1. «Мишень» (10 баллов).

Мишень представляет собой 10 концентрических кругов. Радиус меньшего – 5, радиус каждого следующего на 5 больше предыдущего. Попадание пули задается в системе координат (см. рисунок) вещественными числами x и y, каждое из которых по модулю не превосходит 100. Количество выбитых очков зависит от того, в какую зону попала п, …, 2, 1, 0.

Ваша программа должна

Ø  запросить координаты попадания;

Ø  найти и сообщить количество выбитых очков.

Пример: Исходные данные –8, 13 Ответ 7

Примечание. В случае попадания в границу круга может быть выведено любое из значений, соответствующих задетым кругам. Например, если исходные данные 3 и 4, то допустимы ответы и 10 и 9.

2. «Числа» (20 баллов).

Дано натуральное n-значное число (n£79), запись которого не содержит цифры 0. Из него отбрасывается несколько подряд идущих цифр с начала и несколько цифр (также подряд идущих) с конца (может быть не одной). Программа должна сообщить количество разных чисел, которое может при этом может получиться.

Пример.

Исходное число 1323

Ответ 9

Примечание. Имеются в виду числа 1323, 323, 132, 23, 32, 13, 3, 2, 1

3. «Многотомник» (30 баллов).

Многотомное собрание сочинений (не более 6 томов) поставлено в произвольном порядке на полке. Необходимо упорядочить тома. Для этого разрешается брать вторую с начала книгу и перекладывать ее либо на первое, либо на последнее место. Составить программу, которая сообщает наименьшее число перестановок необходимое для этого. Программа должна также вывести последовательно получающиеся состояния многотомника.

Пример: Число томов 4 Начальная последовательность 4, 2, 3, 1

Число шагов 4

0 шаг: 4, 2, 3, 1 1 шаг: 4, 3, 1, 2 2 шаг: 4, 1, 2, 3 3 шаг: 1, 4, 2, 3 4 шаг: 1, 2, 3, 4

4. «Многоугольник» (40 баллов).

Часть поверхности прямоугольного стола покрыта одинаковыми листами бумаги. Стороны листов параллельны краю стола и одинаково ориентированы (см. рисунок).

Известно, что

Ø  всего листов n (n£6);

Ø  размер каждого листа 30 см на 20 см

Ø  целочисленные координаты (0£x£160, 30£y£90) левых верхних углов каждого листа в системе координат, связанной с левым нижним углом поверхности стола;

Ø  ни один из листов не выходит за край стола;

Ø  всеми листами покрыт многоугольник.

Написать программу, которая сообщает координаты вершин покрытого многоугольника в порядке обхода.

Исходные данные либо вводятся с клавиатуры, либо читаются из файла input.dat, который в первой строке содержит натуральное число (n)– количество разложенных листов. Последующие n строк – пары координат (x, y) левого верхнего угла листа.

Пример: Число листов 2 1 лист 30, 60 2 лист 40, 50

Ответ (30, , 30)

Тесты и рекомендации по оценке

Задание 1. «Мишень».

Тест

Исходные данные

Ожидаемый результат

1

3, –2

10

2

–25.2, 17.3

4

3

30, 40

1 или 0

4

–22, –32

3

1 тест — 1 балл, 2 теста — 3 балла, 3 теста — 7 баллов, все тесты — 10 баллов.

Задание 2. «Числа».

Тест

Исходные данные

Ожидаемый результат

1

222222

6

2

12345

15

3

112123

17

4

915

1 тест — 3 балла, 2 теста — 7 баллов, 3 теста — 13 баллов, все тесты — 20 баллов

Задание 3. «Многотомник».

Тест

Исходные длины

Ожидаемый результат

1

n=3: 3, 2, 1

3

3: 1, 2, 3

0: 3, 2, 1

1: 2, 3, 1

2: 2, 1, 3

2

n=4: 3, 2, 1, 4

4

0: 3, 2, 1, 4

3: 1, 4, 2, 3

1: 3, 1, 4, 2

4: 1, 2, 3, 4

2: 1, 3, 4, 2

3

n=5: 5, 4, 3, 2, 1

8

3: 3, 2, 1, 4, 5

7: 1, 5, 3, 3, 4

0: 5, 4, 3, 2, 1

4: 3, 1, 4, 5, 2

8: 1, 2, 3, 4, 5

1: 5, 3, 2, 1, 4

5: 1, 3, 4, 5, 2

2: 3, 5, 2, 1, 4

6: 1, 4, 5, 2, 3

4

n=6: 1, 2, 6, 5, 4, 3

17

3: 6, 5, 4, 3, 2, 1

7: 3, 2, 1, 5, 4, 6

11: 5, 4, 6, 2, 1, 3

15: 2, 6, 1, 3, 4, 5

0: 1, 2, 6, 5, 4, 3

4: 6, 4, 3, 2, 1, 5

8: 3, 1, 5, 4, 6, 2

12: 5, 6, 2, 1, 3, 4

16: 2, 1, 3, 4, 5, 6

1: 1, 6, 5, 4, 3, 2

5: 6, 3, 2, 1, 5, 4

9: 3, 5, 4, 6, 2, 1

13: 6, 5, 2, 1, 3, 4

17: 1, 2, 3, 4, 5, 6

2: 6, 1, 5, 4, 3, 2

6: 3, 6, 2, 1, 5, 4

10: 5, 3, 4, 6, 2, 1

14: 6, 2, 1, 3, 4, 5

1 тест — 4 балла, 2 теста —10баллов, 3 теста — 20 баллов, все тесты — 30 баллов

Задание 4. «Многоугольник».

Тест

Исходные данные

Ожидаемый результат

1

n=2 (10, 40); (20, 40)

(10, 40); (40, 40); (40, 10); (10,10)

2

n=3

(30, 40); (10, 70); (20, 60)

(10, 70); (30, 70); (30, 60); (40,60); (40, 40); (50, 40);

(50, 10); (30,10); (30, 30); (20, 30); (20, 40); (10,40)

3

n=3

(50, 70); (65, 50); (80, 60)

(50, 70); (70, 70); (70, 50); (80, 50); (80, 60); (100, 60);

(100, 30); (85,30); (85, 20); (65, 20); (65, 40); (50,40)

4

n=5

(30, 40); (55, 65); (20, 60); (40, 90); (30, 80)

(40, 90); (60, 90); (60, 65); (75, 65); (75, 35); (55, 35); (55,60); (50, 60); (50, 50); (40, 50); (40,40);(50, 40);

(50,10); (30, 10); (30, 30); (20, 30); (20,60); (30, 60); (30,80); (40, 80)

1 тест — 5 баллов, 2 теста — 12 баллов, 3 теста — 27 баллов, все тесты — 40 баллов.

НЕ нашли? Не то? Что вы ищете?

Рекомендуется для всех программ использовать ограничение по времени прохождения одного теста:

— 1 минута.

Варианты решений заданий

Задание 1.

CLS

INPUT "Координаты попадания"; x, y

r = SQR(x * x + y * y)

PRINT "Расстояние до центра мишени "; r

k = 10

WHILE r > 5

r = r - 5

k = k - 1

WEND

IF k < 0 THEN k = 0

PRINT "Число очков "; k

END

Задание 2.

CLS

DEFSTR X

DEFINT I, N

DIM x(81)

INPUT "Исходное число"; x

x(0) = x

n = LEN(x)

k = 1

FOR i = 1 TO n - 1

ii = 0

FOR iii = 1 TO n + 1 - i

ii = ii + 1

x(ii) = MID$(x, iii, i)

NEXT

FOR iii = 1 TO ii - 1

FOR j = 1 TO ii - iii

IF x(j) > x(j + 1) THEN SWAP x(j), x(j + 1)

NEXT

NEXT

FOR iii = 1 TO ii

IF iii = 1 OR x(iii) <> x(iii - 1) THEN k = k + 1

NEXT

NEXT

PRINT "Число чисел "; k

END

Задание 3.

CLS

DEFINT A-Z

DIM p(721, 8), x(6)

INPUT "Число томов "; n

PRINT "Введите их порядок"

FOR i = 1 TO n

PRINT i; ": ";

INPUT x(i)

p(1, i) = i

NEXT

un = 1

uk = 1

WHILE un <= uk

p(uk + 1, 1) = p(un, 2)

p(uk + 1, 2) = p(un, 1)

FOR i = 3 TO n

p(uk + 1, i) = p(un, i)

NEXT

f = 1

k = 1

WHILE f = 1 AND k <= uk

f = 0

FOR i = 1 TO n

IF p(uk + 1, i) <> p(k, i) THEN f = 1

NEXT

k = k + 1

WEND

IF f = 1 THEN

uk = uk + 1

p(uk, 7) = p(un, 7) + 1

p(uk, 8) = un

END IF

p(uk + 1, 1) = p(un, 1)

p(uk + 1, 2) = p(un, n)

FOR i = 3 TO n

p(uk + 1, i) = p(un, i - 1)

NEXT

f = 1

k = 1

WHILE f = 1 AND k <= uk

f = 0

FOR i = 1 TO n

IF p(uk + 1, i) <> p(k, i) THEN f = 1

NEXT

k = k + 1

WEND

IF f = 1 THEN

uk = uk + 1

p(uk, 7) = p(un, 7) + 1

p(uk, 8) = un

END IF

un = un + 1

WEND

h = 0

FOR i = 1 TO uk

f = 1

FOR j = 1 TO n

IF p(i, j) <> x(j) THEN f = 0

NEXT

IF f = 1 THEN

h = p(i, 7)

ii = i

END IF

NEXT

PRINT "------"

PRINT "Число шагов "; h

PRINT "Последняя "; ii

i = 0

FOR i = 0 TO h

PRINT i; ":";

FOR j = 1 TO n

PRINT p(ii, j);

NEXT

PRINT

ii = p(ii, 8)

NEXT

END

Задание 4.

CLS

DEFINT A-Z

DIM x(11), y(11), xs(24), ys(24), xotr(80), yotr(80), pn(88), pp(88), t(24, 24), xv(44), yv(44)

INPUT "Введите число листов"; n

PRINT "Вводите координаты левых верхних углов"

FOR i = 1 TO n

PRINT i; ": ";

INPUT x(i), y(i)

xs(i * = x(i)

ys(i * = y(i)

xs(i * 2) = x(i) + 20

ys(i * 2) = y(i) - 30

NEXT

xs(2 * n + 1) = -10

xs(2 * n + 2) = 200

ys(2 * n + 1) = -10

ys(2 * n + 2) = 100

FOR i = 1 TO 2 * n + 1

FOR j = 1 TO 2 * n + 2 - i

IF xs(j) > xs(j + 1) THEN SWAP xs(j), xs(j + 1)

NEXT

NEXT

FOR i = 1 TO 2 * n + 1

FOR j = 1 TO 2 * n + 2 - i

IF ys(j) > ys(j + 1) THEN SWAP ys(j), ys(j + 1)

NEXT

NEXT

ux = 1

FOR i = 2 TO 2 * n + 2

IF xs(i) <> xs(ux) THEN

ux = ux + 1

xs(ux) = xs(i)

END IF

NEXT

uy = 1

FOR i = 2 TO 2 * n + 2

IF ys(i) <> ys(uy) THEN

uy = uy + 1

ys(uy) = ys(i)

END IF

NEXT

kstr = uy - 1

kstl = ux - 1

FOR i = 1 TO kstr

FOR j = 1 TO kstl

t(i, j) = 0

FOR k = 1 TO n

IF xs(j) >= x(k) AND xs(j + 1) <= x(k) + 20 AND ys(i) >= y(kAND ys(i + 1) <= y(k) THEN t(i, j) = 1

NEXT

NEXT

NEXT

kotr = 0

FOR i = 1 TO kstr - 1

FOR j = 1 TO kstl - 1

s = t(i, j) + t(i, j + 1) + t(i + 1, j) + t(i + 1, j + 1)

IF s = 1 OR s = 3 THEN

kotr = kotr + 1

xotr(kotr) = xs(j + 1)

yotr(kotr) = ys(i + 1)

pn(kotr) = 1

pp(kotr) = 1

END IF

NEXT

NEXT

FOR j = 1 TO kstl - 1

FOR i = 1 TO kstr - 1

s = t(i, j) + t(i, j + 1) + t(i + 1, j) + t(i + 1, j + 1)

IF s = 1 OR s = 3 THEN

kotr = kotr + 1

xotr(kotr) = xs(j + 1)

yotr(kotr) = ys(i + 1)

pn(kotr) = 0

pp(kotr) = 1

END IF

NEXT

NEXT

xv(1) = xotr(1)

yv(1) = yotr(1)

pp(1) = 0

xv(2) = xotr(2)

yv(2) = yotr(2)

pp(2) = 0

g = 1

FOR i = 3 TO kotr / 2

nsl = 0

FOR j = 1 TO kotr

IF pp(j) = 1 AND xv(i - 1) = xotr(j) AND yv(i - 1) = yotr(j) AND g <> pn(j) THEN nsl = j

NEXT

g = 1 - g

pp(nsl) = 0

IF nsl MOD 2 = 0 THEN

nsl = nsl - 1

ELSE

nsl = nsl + 1

END IF

pp(nsl) = 0

xv(i) = xotr(nsl)

yv(i) = yotr(nsl)

NEXT

PRINT "Координаты вершин многоугольника:"

FOR i = 1 TO kotr / 2

PRINT xv(i); yv(i)

NEXT

END