| 1 Фетих Мехмет, 25 ноября 2016 г. 7:43:51 | |
|
подскажите пожайлуста как можно решить эту задачу, кроме bfs ничего в голову не приходит, но не проходит.
|
|
|
| 2 Демиденко Виталий, 02 ноября 2009 г. 12:38:56 | |
|
Алексей, http://ikit.institute.sfu-kras.ru/shk2009
|
|
|
| 3 Субач Алексей Дмитриевич, 02 ноября 2009 г. 8:51:31 | |
|
Александр, ссылочку на сайт плз
|
|
|
| 4 Снетков Александр Сергеевич, 02 ноября 2009 г. 8:41:15 | |
|
Кстати все тесты можно найти на сайте ИКИТ СФУ, в разделе Олимпиада школьников, 09/10 Год.
|
|
|
| 5 Снетков Александр Сергеевич, 02 ноября 2009 г. 8:40:09 | |
Тест №9:
20 20
33 95 11 66
XXXXXXXXXXXXXXXXXXXX
X.......X..........X
X.......G..........X
XS......X..........X
XXXXBXXRXXXRXXXX...X
X.......X......X...X
X.......R......R...X
X.......XXXXXXXXXYXX
XXRXRXXXX.....X....X
X.......R.....G....X
XXXRXXXXBXXXYXXXXRXX
X....X....X....X...X
X....X....X....X...X
X....X....X....X...X
XXXRXXXXRXXXRXXXXRXX
X....X........X....X
X....X........X...EX
X....X........Y....X
X....X........X....X
XXXXXXXXXXXXXXXXXXXX
Ответ:
99
|
|
|
| 6 Мехрдоди Одил(ТРГИ), 01 ноября 2009 г. 21:28:31 | |
|
Богдан, не только задач с базы но и задач с neerc, сегодня ваще все круто было бы вот если бы не подвела система...
|
|
|
| 7 Прищенко Богдан Олегович, 01 ноября 2009 г. 20:24:35 | |
Снетков Александр Сергеевич, можно, я так тоже предлогал. Меня интересует именно то, что такого особенного в 9ом тесте - хочу знать на будущее, что надо было учесть или изменить. Как решать задачу - у меня и у самого есть вариантов 5:) В этот раз на олимпиаде не было ни одной сложной задачи, так что обсуждать алгоритмы нету смысла.
З.Ы. Огромный респект Сергею Николаевичу и автору этих задач за первую за последнее время "чистую" олимпиаду (без задач с базы).
|
|
|
| 8 Демиденко Виталий, 01 ноября 2009 г. 19:23:23 | |
|
В данном случае ещё проще dfs, чем волна
|
|
|
| 9 Снетков Александр Сергеевич, 01 ноября 2009 г. 18:14:58 | |
|
Можно решить волной. Смысл вот в чем. Перебираем все возможные комбинации прохождения через двери то есть прошол через R или не прошел, через G прошол или не прошел и тд. В итоге 16 вариантов. В итоге 16 волн.
|
|
|
| 10 Cihad OGE, 01 ноября 2009 г. 17:29:25 | |
|
Я написал дфс и я ее решил.
|
|
|
| 11 Cihad OGE, 01 ноября 2009 г. 17:29:01 | |
|
Я написал дфс и я ее решил. ;)
|
|
|
| 12 Прищенко Богдан Олегович, 01 ноября 2009 г. 17:04:54 | |
|
Мы были в одной команде - Виталий сначала написал Дейкстрой (каждой двери присваивать вес, равный ее цене, в конце отнять веса тех дверей, которые использовались больше одного раза) - ВА9, потом ДФС (ТЛ 5). Потом за эту задачу взялся я, написал ее БФС-ом, то, что успел сотворить к концу олимпиады - тоже ВА9.
|
|
|
| 13 Нагин Сергей Юрьевич, 01 ноября 2009 г. 15:49:17 | |
|
Нам надо проверить достижимость! А это либо поиск в ширину(волна) либо в грубину(дфс) !
|
|
|
| 14 Нагин Сергей Юрьевич, 01 ноября 2009 г. 15:48:40 | |
|
А при чем тут дейкстра?
|
|
|
| 15 Герасимів Віталій Ігорович, 01 ноября 2009 г. 15:40:31 | |
|
Алгоритмом Дейсктры.
|
|
|
| 16 Нагин Сергей Юрьевич, 01 ноября 2009 г. 15:39:11 | |
|
Ты как решал?
|
|
|
