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

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


Информационный Канал Subscribe.Ru


Школьный КОМП

Весенняя олимпиада школьников 2003 года.
Задача первого тура


 
Даже самый хороший человек на 90 процентов состоит из воды
Братья Марио


Водопровод

Водопроводная сеть состоит из труб разной пропускной способности. Вода по любой трубе может течь в любую сторону. Все места соединения труб учтены и пронумерованы целыми числами от 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> <напор>

Пример

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

Оценка задачи

Задача оценивается соревновательно. Максимальное количество баллов получают решения с максимальным количеством воды поступающей в узел (приток) 0. Из решений с одинаковым притоком считается лучшим то, где будет присутствовать больше труб с нулевым напором. Максимальное количество баллов за задачу: 100.

Командный вариант

Эту задачу можно решать не только одному. Вы можете собрать команду до 4 человек. Команда более чем из одного человека получит поощрительные очки: 2 человека -- 10 баллов, 3 человека -- 15 баллов, 4 человека -- 20 баллов. Баллы набранные командой не делятся, а каждый участник команды получает все баллы заработанные командой.




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



Последний день присылать решения задачи -- 20 марта 2003 года.

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

Вопросы и решения присылайте по адресу: olymp_mark@uni.udm.ru


Copyright © КОМП  

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

В избранное