Отправляет email-рассылки с помощью сервиса Sendsay

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Февраль 2003   →
 1
 2
 3
 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
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Конкурсы и Олимпиады по Машинному программированию (КОМП)


Информационный Канал Subscribe.Ru 
Продолжаем публиковать материалы прошлой олимпиады.

---------------
Весенний школьный конкурс корпорации "МАРК" и Удмуртского государственного
университета 2002 года в области программирования на соискание стипендии.
Четвёртый тур.

Задачи очного тура


ЗАДАЧА 1. Забор яблоневого сада

Для решения этой задачи Вы можете получить своё решение задачи третьего тура.

У одного фермера есть квадратный участок земли 10000 метров в длину и 10000 метров
в высоту. Это поле мысленно разлиновано на клетки с шагом в 1 метр. Линии
пронумерованы от 0 до 10000. Таким образом, получилась координатная сетка.

Фермер посадил яблони точно в узлах (точках пересечения линий) сетки. Ни одна
яблоня не посажена на краю участка. Теперь он решил поставить вокруг забор.
Забор нужно поставить так, чтобы выполнялись следующие условия:

1) должен состоять из четырёх прямых пролётов одинаковой длины;
2) должен быть непрерывным;
3) углы должны находится точно в узлах сетки;
4) все яблони должны быть внутри области огороженной забором.

Техническое задание
Расположение узла с деревом задаётся двумя числами, номерами линий,
при пересечении которых получается этот узел. Расположение всех яблонь задается
в файле orchard.txt следующим образом. В первой строке записано одно число -
количество яблонь (не менее одной). Начиная со второй, строки записаны пары
чисел - расположение узлов. Пар столько же, сколько и яблонь. Числа разделены
пробелами. Некоторые яблони могут быть указаны несколько раз. В файле fence.txt
записаны пары чисел - узлы, где должны быть углы забора в произвольном порядке.
Нужно написать программу, которая читает файлы orchard.txt и fence.txt.
Результатом работы программы не позже чем через 10 секунд должен быть
квадрат длины одного пролёта забора. Если в fence.txt записаны
сведения нарушающие условия 1-4, но нужно выдать число 0.
Ответ выдавать на экран.

ПРИМЕР 1.
 В orchard.txt     в fence.txt
  4                 0   0
  1   1             14  17
  5   6             30  30
 30  30             17  14
  5   6

 Ответ: 0

ПРИМЕР 2.
 В orchard.txt     в fence.txt
 3                   0   0
  1   1             14  17
  5   6             17  14
 30  30             31  31
  5   6

 Ответ: 485




Автор задачи: В.В.Пупышев

ЗАДАЧА 2. Цветная линия
Для игры в цветную линию используются шарики семи цветов.

Несколько шариков выстраиваются в линию. Если рядом оказались шарики
одинакового цвета, они убираются (все сколько есть). Оставшиеся шарики
сдвигаются так, чтобы не осталось пустого места. Если после сдвига опять
окажется, что есть рядом одинаковые шарики, то операция повторяется. После
того как не осталось одинаковых шариков рядом, выполняется ход. Можно
переставлять любой шарик из линии в её конец. Шарики сдвигаются. После чего всё
продолжается с получившейся линии.

Цель игры
Оставить как можно меньше шариков за минимум ходов.

Техническое задание
В файле line.txt записаны две строки. Первая число - длина исходной линии
(не более 80). Вторая - последовательность цветов шариков в этой линии.
Цвета будет обозначать буквами: B (синий), G (зелёный), C (голубой),
R (красный), M (малиновый), Y (жёлтый), W (белый). Задача. Написать программу,
которая по заданной начальной линии запишет в файл moves.txt последовательность
ходов для получения короткой линии шариков. Последовательность должна
содержать не более 100 чисел. Файл moves.txt устроен следующим образом.
В каждой строке записано одно число - номер шарика от начала,
который нужно переставить в конец.

Оценка задачи
Между программами будут устроены соревнования. В первую очередь будет
оцениваться длина оставшейся линии, и при равных длинах - количество ходов.

ПРИМЕР.
В line.txt

  10
  BGCRCMYWWY


В moves.txt

  3
  4


Сама игра
BGCRCMYWWY
Перед ходом
BGRCMС
Ход 1
BGRCMС
Ход 2
BGRMСС
Результат:
BGRM
Итого: за два хода удалось получить длину 4.




Автор задачи: В.В.Пупышев

ЗАДАЧА 3. Отремонтирована ли стиральная машина?
Вася починил свою стиральную машину. Но он боится, что он ее неправильно собрал.
В случае ошибки может произойти короткое замыкание и некоторые из блоков
могут снова выйти из строя. К счастью, Вася знает, какие соединения блоков
стиральной машины ведут к аварии, то есть что с чем не должно быть соединено
одновременно. Вася знает электрическую схему, которую он получил при сборке
стиральной машины. Помогите Васе проверить, не приведет ли его сборка к аварии.
Ваша задача состоит в написании программы, определяющей по схеме сборки машины
и
ее программе приводит ли эта сборка к аварии, а если приводит, то на каком
шагу работы программы.

Исходные данные содержатся в файле input.txt в следующем виде: t - длина
программы машины (число моментов времени в ней), c[1] - число соединений
в момент времени 1,
x[1,1] y[1,1] ... x[1,c[1]] y[1,c[1]] - информация о соединениях в момент
времени 1 (точка номер x[1,1] соединена с точкой номер y[1,1], ..., точка
номер x[1,c[1]] соединена с точкой номер y[1,c[1]]),
 ...
c[t] - число соединений в момент времени t,
x[t,1] y[t,1] ... x[t,c[t]] y[t,c[t]] - информация о соединениях в момент
времени t,
k - число запрещенных сочетаний соединений,
b[1] - число соединений в запрещенном сочетании номер 1,
z[1,1] u[1,1] ... z[1,b[1]] u[1,b[1]] - информация о соединениях
в запрещенном сочетании номер 1 (нельзя одновременно соединить
точку z[1,1] с точкой u[1,1], ... и точку z[1,b[1]] c точкой u[1,b[1]]),
 ...
b[k] - число соединений в запрещенном сочетании номер k,
z[k,1] u[k,1] ... z[k,b[k]] u[k,b[k]] - информация о соединениях в
запрещенном сочетании номер k.

Замечание: если две точки соединены с третей, то они считаются соединенными
между собой.

Выходные данные записываются в файл output.txt в следующем виде: 0, если аварии
не происходит, иначе файл содержит номер момента времени, в который авария
происходит ВПЕРВЫЕ.

Технические ограничения: номера точек для соединения могут принимать значения
от 1 до 200, числа соединений - не более 40000, число моментов времени и
число k - не более 10000. Все числа в input.txt разделяются пробелами
и/или переводами строк, после последнего числа - конец файла с
возможными предшествующими пробелами и/или переводами строк. Время
решения ограничено 20 секундами. Вспомогательные файлы использовать запрещается.
Доступная оперативная память - 16M.

Пример правильного содержимого input.txt:

1
1
1 2
1
1
1 2

Здесь t=1, c[1]=1, x[1,1]=1, y[1,1]=2, k=1, b[1]=1, z[1,1]=1, u[1,1]=2.

Пример соответствующего содержимого output.txt:

1





Автор задачи: А.П.Бельтюков

---------------
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное