Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2013-01-04 15:06:55

Kostya_135
Новий користувач
Зареєстрований: 2012-10-29
Повідомлень: 9

Pigulia

"Любые  два города могут соединять несколько дорог" Значит ли это, что такой ввод данных возможен:
3 4
1 3 0
1 3 1000
1 2 1
2 3 2    ?

Відредаговано Kostya_135 (2013-01-04 15:07:41)

Поза форумом

 

#2 2013-01-04 15:24:18

Жюри_Непомнящий
Журі
Зареєстрований: 2005-11-03
Повідомлень: 151

Re: Pigulia

Такой вариант возможен

Поза форумом

 

#3 2013-01-04 22:15:23

Alex_Bulany
Новий користувач
Зареєстрований: 2009-01-26
Повідомлень: 17

Re: Pigulia

Прохання уточнити умову задачі відносно обмеження на «небезпеку» дороги:
1) "Пигульська адміністрація президента визначила небезпеку кожної дороги у вигляді числа від 0 (безпечна) до 1000  (дуже небезпечна)."
2) "та С –  «небезпеку» дороги (0≤ С ≤ 10000)."
Щиро вдячний за відповідь.

Поза форумом

 

#4 2013-01-06 06:54:28

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Pigulia

Alex_Bulany написав:

1)...від 0 (безпечна) до 1000  (дуже небезпечна)....
2)...0≤ С ≤ 10000

Наверное, опечатка. В русском варианте: 0≤ С ≤ 1000


Вік живи - вік навчайся.

Поза форумом

 

#5 2013-01-06 20:14:39

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Pigulia

Опечатка. Исправил. Спасибо.

Поза форумом

 

#6 2013-01-07 22:24:51

Kostya_135
Новий користувач
Зареєстрований: 2012-10-29
Повідомлень: 9

Re: Pigulia

"В государстве Пигулии имеется N городов, некоторые из них соединены двухсторонними дорогами. Проехать можно из любого города в любой...." Из первого предложения следует, что если из 1 города можно проехать во второй, то необязательно из второго можно проехать в первый! Во втором предложении утверждается, что из любого города можно проехать в любой! Получаем, что эти два условия противоречат друг другу. И в связи с этим вопрос:"Какое из этих двух утверждений неверно, то есть,если вводится 1 3 10 это значит, что и 3 с 1 соединены ?"

Поза форумом

 

#7 2013-01-08 06:42:18

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Pigulia

Kostya_135 написав:

"В государстве Пигулии имеется N городов, некоторые из них соединены двухсторонними дорогами. Проехать можно из любого города в любой...."

Дороги двусторонние! Проехать можно как "туда", так и "обратно". smile


Вік живи - вік навчайся.

Поза форумом

 

#8 2013-01-08 14:10:43

shoa169
Новий користувач
Зареєстрований: 2010-11-10
Повідомлень: 56

Re: Pigulia

Kostya_135 написав:

"В государстве Пигулии имеется N городов, некоторые из них соединены двухсторонними дорогами. Проехать можно из любого города в любой...."

Всегда нужно стараться как можно точнее "перевести" условие задачи на "алгоритмическо-програмистский" язык.

1) "В государстве Пигулии имеется N городов" -> "Есть граф, содержащий N вершин".
  Пока про этот граф ничего не знаем.

2) "некоторые из них соединены двухсторонними дорогами" -> "Граф - неориентированный"
  Сколько ребер в графе - пока неясно: от нуля, что спорно, до любого числа.

3) "Проехать можно из любого города в любой" -> "Граф содержит одну компоненту связности". 
  Теперь уже ясно, что ноль рёбер возможно только для графа из 1-ой вершины. Граф может варьироватсья от дерева до полного графа и даже больше(wink).

4) "администрация президента определила опасность каждой дороги в виде числа от 0 (безопасная) до 1000" -> "Граф взвешенный".

5) "Любые  два города могут соединять несколько дорог" -> "Возможны кратные рёбра".
   Это обсуждалось выше в теме. Алгоритмы для простых графов уже не годятся.

*) и так далее. После перевода становится ясно, что за задача. Неточный "перевод" любой задачи приводит к тому, что участник решает не ту задачу!

Надеюсь, это сообщение подтолкнёт некоторых участников к изучению теории графов, а  жюри не усмотрит в нём подсказки. smile

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt