Отправляет 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 
Продолжаем публикацию материалов прошлой олимпиады.

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




Задача второго тура.


Ремонт стиральной машины

У  Васи  сломалась  стиральная  машина.  Анализ  поломки  показал, что
требуется   заменить   командоаппарат  (командоаппарат  -  устройство,
которое   обеспечивает   электрические   соединения  различных  блоков
стиральной   машины   в   заданных   последовательностях  с  заданными
временными  задержками).  Вася  купил новый командоаппарат, отсоединил
старый,  но  тут  обнаружилось,  что он не помнит, какие электрические
разъемы    стиральной    машины   к   каким   электрическим   разъемам
командоаппарата  следует  присоединить.  К  счастью,  Вася  знает, как
должна  работать  стиральная  машина,  то  есть  что  с  чем и в какой
последовательности  в  ней  должно  быть соединено. Знает Вася также и
электрические  схемы  стиральной  машины  и командоаппарата, а также -
циклограмму    командоаппарата   (циклограмма   -   последовательность
соединений  внутренних контактов командоаппарата во времени). Помогите
Васе  правильно  присоединить  командоаппарат,  так  как  неправильное
соединение  может  привести  к  коротким  замыканиям  и поломке других
блоков  машины.  Ваша  задача  состоит в написании программы, выдающей
инструкцию  по  присоединению  командоаппарата  по электрической схеме
машины,  схеме  и  циклограмме  командоаппарата,  а  также  по  схемам
электрических соединений, которые командоаппарат должен обеспечивать.

Исходные данные содержатся в файле input.txt в следующем виде:

N - число разъемов командоаппарата,

M  -  число  точек  соединения в электрической схеме машины, включая N
разъемов  которые следует присоединить к командоаппарату, M=N+R, где R
-   число   блоков   стиральной   машины,  которые  следует  соединять
командоаппаратом,

K  -  число  точек  соединения  в электрической схеме командоаппарата,
включая  N внешних разъемов, к которым следует присоединить стиральную
машину,  K=N+2Q, где Q - число контактных пар командоаппарата, которые
соединяются и разъединяются в соответствии с его циклограммой,

L - число внутренних соединений в стиральной машине,

X_1,  Y_1,  ...  X_L,  Y_L - внутренние соединения в стиральной машине
(числа  в диапазоне от 1 до M, каждое i-е соединение соединяет точку с
номером  X_i  с  точкой с номером Y_i в электрической схеме стиральной
машины),

P - число внутренних соединений в командоаппарате,

Z_1,  U_1,  ...,  Z_P,  U_P  - внутренние соединения в командоаппарате
(числа  в диапазоне от 1 до K, каждое i-е соединение соединяет точку с
номером   Z_i   с   точкой   с   номером  U_i  в  электрический  схеме
командоаппарата),

T - длина циклограммы командоаппарата (число моментов времени в ней),

С_{1,1}, ..., C_{1,Q},

 .....................

C_{T,1}, ..., C_{T,Q}

-  циклограмма  командоаппарата  (С_{i,j} равно 0 или 1, "0" означает,
что в момент времени номер i контактная пара номер j [точки с номерами
N+2j-1  и  N+2j  в электрической схеме командоаппарата] разомкнута [то
есть эти точки соединены], "1" означает, что она замкнута).

Далее  заданы  T  электрических  схем,  которые эта циклограмма должна
должна обеспечивать. Каждая схема задается в следующем виде:

R_i - число соединений,

V_1,  W_1,  ..., V_{R_i}, W_{R_i} - соединения (числа в диапазоне от 1
до R, каждое j-е соединение соединяет блок стиральной машины номер V_j
с  блоком номер W_j [то есть точку номер N+V_j с точкой номер N+W_j на
электрической  схеме  стиральной  машины],  направление  соединения не
играет  роли,  если  две  точки  соединены  с третей, то они считаются
соединенными  между собой, и т.д., точки, не соединяемые по этой схеме
должны  быть  не соединены и командоаппаратом в соответствующий момент
времени,  все  соединяемые  по  этой  схеме точки должны быть каким-то
способом   соединены   и  командоаппаратом  в  соответствующий  момент
времени).

Выходные  данные  записываются в файл output.txt в следующем виде S_1,
 ...,  S_N,  где S_i - номер разъема стиральной машины, который следует
соединить с i-м разъемом командоаппарата (S_i - числа в диапазоне от 1
до N). Если задача не имеет решения, выводится пустой файл output.txt.

Технические  ограничения:  числа  M,  K  и  T  в  файле  input.txt  не
превосходят 200; L, P, R_i не превосходят 30000. Все числа в input.txt
и   output.txt  разделяются  пробелами  или  переводами  строк,  после
последнего  числа - конец файла. Время решения ограничено 20 секундами
процессорного  времени  (для  тактовой  частоты  процессора  200 МГц).
Вспомогательные  файлы использовать запрещается. Доступная оперативная
память - 16M.

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

Здесь  N=2,  M=4,  K=4,  L=2,  X_1=1, Y_1=3, X_2=2, Y_2=4, P=2, Z_1=1,
U_1=3,  Z_2=2,  Z_2=4,  T=2,  Q=1, C_{1,1}=0, C_{2,1}=1, R_1=0, R_1=1,
V_1=1, W_1=2.

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

Этот  файл  задает такой способ присоединения командоаппарата, который
обеспечивает  разъединение  блоков  с  номерами  1 и 2 в первый момент
времени по циклограмме и соединение их во второй момент времени.




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



Последний день решения задачи - 13 мая 2002 года.

Последний день задавать вопросы по условию задачи - 3 мая 2002 года.

Внимание! Второй тур не командный, а индивидуальный. Но если кто-то из
членов  команды  не  будет  участвовать в нём, то можно потерять часть
командных баллов.






                                 До свидания.

                                 Жюри школьного конкурса Марк
                                 olymp_mark@uni.udm.ru
                                 http://olymp.udm.ru
                                 18.04.02
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное