Отправляет 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
29
30
Автор
ss77_ss77@mail.ru

Статистика

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

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


Информационный Канал Subscribe.Ru 
  Весенняя олимпиада школьников 2003 года.
  Задачи четвёртого тура


Все задачи оцениваются в 30 баллов.
Авторы могли получить исходные тексты своих решений задач предыдущих туров.

Задача 1. "Водопроводчик"
ФОРМУЛИРОВКА ЗАДАЧИ ПЕРВОГО ТУРА
Водопроводная сеть состоит из труб разной пропускной способности. Вода по любой
трубе может течь в любую сторону. Все места соединения труб учтены и пронумерованы
целыми числами от 0 до 10000. Особо выделены места с номерами 0 и 1. На самом
деле, 0 это не соединение труб, а место, в котором подаётся вода в трубы, а 1
-- место, откуда вода вытекает. У каждой трубы известна пропускная способность
-- максимальное количество воды, протекающей по трубе, за единицу времени, при
котором она ещё не лопнет.

ЗАДАЧА
Цель: добиться того, чтобы в узел 1 текло как можно больше воды. Определить,
каково необходимое количество воды, протекающей по каждой трубе (напор) для достижения
цели.

Превышать пропускную способность трубы нельзя, а то труба может лопнуть.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ
Поток воды в трубе должен быть целым числом. В файле pipes.txt находится описание
соединения. Ответ нужно записать в файл water.txt в указанном формате

ФОРМАТ pipes.txt
  <Номер трубы> <узел 1> <узел 2> <пропускная способность>
  <Номер трубы> <узел 1> <узел 2> <пропускная способность>
  ...
  <Номер трубы> <узел 1> <узел 2> <пропускная способность>

ФОРМАТ water.txt
  <Номер трубы> <узел 1> <узел 2> <напор>
  <Номер трубы> <узел 1> <узел 2> <напор>
  ...
  <Номер трубы> <узел 1> <узел 2> <напор>

<пропускная способность> -- натуральное число от 1 до 100.

Ограничены номера труб -- натуральное число от 1 до 1000.

ПРИМЕР
pipes.txt
 1 0 2 1
 3 3 2 10
 5 3 1 9
 2 0 3 10
 4 2 3 10
 6 3 1 9

water.txt
 1 0 2 0
 2 0 3 10
 3 2 3 1
 4 3 2 1
 5 3 1 9
 6 3 1 1

ЗАДАНИЕ ЭТОГО ТУРА
Написать программу, которая будет проверять ответы, полученные для входных данных
для первого тура, на правильность. Если ответ правильный, вычисляется приток
в 1 узел. Если ответ содержит ошибку, то указать, в каком узле или трубе и что
не верно. Формат файла water.txt будет верным, это можно не про верять.

Время работы программы 1 секунда.

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




Задача 2. "ТРИ КУЧКИ-2"
Двое игроков играют в следующую игру. Перед ними -- три кучки камней (в каждой
кучке -- не менее 2 камней). Каждый из игроков во время своего хода может удалить
любую кучку, а камни любой другой разложить в виде контура прямоугольника со
сторонами в M и N камней (M и N больше единицы), и заменить эту кучку на две:
первая -- из M камней, вторая -- из N камней. Игроки ходят по очереди. Проигрывает
тот, кто не может сделать указанное действие.

ТРЕБУЕТСЯ написать программу, которая делает очередной ход в игре.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ
Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда.

ФОРМАТ ВХОДНЫХ ДАННЫХ
Входной файл содержит три целое положительные числа -- начальную игровую позицию.
Каждое число не превышает 32767. Числа записаны в десятичной форме и разделены
пробелами.

ФОРМАТ ВЫХОДНЫХ ДАННЫХ
Выходной файл должен содержать в первой строке цифру 1, если ход возможен, или
цифру 2, если это не так. Если ход возможен, то во второй строке должны содержаться
три числа: номер удаляемой кучки, номер заменяемой кучки и число камней в первой
из заменяющих кучек.

ПРИМЕР ФАЙЛОВ ВХОДНЫХ И ВЫХОДНЫХ ДАННЫХ
input.txt
2 2 4

output.txt
1 1 3 2

ПРИМЕЧАНИЕ
Число набранных баллов определяется в результате турнира между программами участников
и жюри.

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




Задача 3. "Пейджинговый роуминг"
Известна проблема с роумингом для пейджеров. Нужно, чтобы абонент получал назначенное
для него сообщение, находясь рядом с любой антенной, но у пейджера нет обратной
связи, и определить, где он находится, невозможно, приходится передавать сообщение
по всем станциям и передавать его в эфир на каждой станции. Проблема состоит
в том, что две станции могут передавать сообщения одновременно третьей. И если
третья станция окажется на одинаковом расстоянии от этих двух, могут возникнуть
проблемы. Здесь предлагается подход для решения этой проблемы.

Давайте сразу строить станции так, чтобы не было двух, расположенных на одинаковом
расстоянии от третьей. Тогда такой ситуации не возникнет.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ
Наша задача -- поставить максимально возможное число станций на прямоугольной
территории. Все вычисления будем вести в целых метрах. Тогда любое место для
станции может иметь координаты -- целые числа X от 0 до N и Y от 0 до K (K, N<1000).

Программа считывает из файла map.txt два числа N и K. И записывает в файл antenna.txt
информацию и расположения станций в следующем виде:

  < S - количество станций >
  <Координата X первой станции> <Координата Y первой станции>
  ...
  <Координата X S-ой станции> <Координата Y S-ой станции>


Время работы программы 10 секунд.

ПРИМЕР
map.txt
 3 4

antenna.txt
 4
 0 0
 0 1
 0 3
 3 4

Задача соревновательная. Максимальное количество баллов получает программа, разместившая
максимальное количество станций.

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



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