|
|
|
|
|
|
|
| 21 Черков Виталий Викторович, 18 января 2014 г. 20:08:03 |
Подскажите, как выглядят входные данные, если только одна лошадь?
1 1
1
0
так?
или так:
1 1
1 0
0
и что нужно вывести?
Вот так:
1 1
0
Вывести нужно Yes.
|
|
|
| 22 Провоторов Никита Владимирович, 12 января 2014 г. 14:31:30 |
Обычный BFS на орграфе(представлен списком смежности). Сдал с 1 раза.
Подсказка : если вы реализовали BFS абсолютно правильно (без багов и прочего), то определить, является ли лошадь самой быстрой очень просто: если length(graph[K])=N-1, то самая быстрая, иначе (если <N-1) нет.
|
|
|
| 23 Абдрахманов Алдияр Маулынгазынович, 06 января 2014 г. 17:49:10 |
| Я не знаю как вы, но я решил Динамикой
|
|
|
| 24 Провоторов Никита Владимирович, 02 января 2014 г. 17:03:23 |
Какой ответ в таком случае?
3 2
2 1
3 1
|
|
|
| 25 Кардаш Олександр Олександрович, 21 марта 2012 г. 17:33:18 |
можно проще чем dfs
нельзя сказать, что dfs - это сложно, но для понимания возможно кому то через bfs это проще решать.
|
|
|
| 26 Залуцкий Александр Андреевич, 23 января 2012 г. 20:12:11 |
| Там как будто цикл в dfs, но он не цикл...... Надо просто не идти в помеченные вершины и TLE нет)
|
|
|
| 27 Четин Михаил Михайлович, 08 июня 2011 г. 20:16:08 |
Здравствуйте, администратор.
Тесты для этой задачи не совсем полные.
Если Вы посмотрите на моё решение, то увидите всю его абсурдность - стоит пройтись по всем парам лошадей 2 раза, не используя поиск в глубину, и задача будет зачтена. Также это отражается в контрпримере для моей программы:
6 6
6 5
3 2
4 3
5 4
6 1
0
Правильный ответ Yes, моя программа выдает No
Здесь таким способом нужно пройтись хотя бы 3 раза.
Все это весьма странно, если учесть что минимум в одном из тестов больше 1000 пар лошадей.
Пожалуйста, исправте тесты, чтобы можно было проверить правильное решение. Заранее спасибо!
|
|
|
| 28 Балакший Андрей Владимирович, 11 марта 2011 г. 16:48:17 |
| ориентированный граф + dfs = чудо
|
|
|
| 29 Роман Верчиков, 27 августа 2010 г. 12:39:43 |
Все-таки циклы были, после добавления проверок все прошло. Циклы, судя по всему, начинаются с 12го теста. Касательно задачи, ИМХО, подциклы некорректны, т.к. лошади не могут быть одновременно быстрее и медленнее самих себя... Если я не прав, прошу пример, для которого циклы возможны. Спасибо.
Циклов быть не может, Вы возможно путаете с циклами нечто, похожее на такой тест: 4 1 1 2 1 3 2 4 3 4 0 Если рисовать, то замкнутость есть, но цикла нет, ведь у нас орграф.
|
|
|
| 30 Мушет Дмитрий Валентин, 10 мая 2010 г. 13:00:31 |
А как может быть N=1?? Это не логично. И ищо, какие будет входные данные в этом случае ??
1 1
1 1
0
Тоесть первая лощадь быстрее первой ?? Опять не логично )) Это как сказать что я больше меня ))
Нет, при N=1 может быть только такой тест:
1 1
0
Т.е. есть только одна лошадь и она самая быстрая, поэтому надо выводить Yes. Так что все логично. А некорректный тест вы сами придумали и зря накручиваете тут.
|
|
|
| 31 AC-SKYDOS, 02 февраля 2010 г. 17:59:38 |
| Решил короче самым обычным поиском в ширину: пускаем поиск в ширину с вершины k, в конце поиска, если не все вершины были использованы - выводим No иначе Yes
|
|
|
| 32 Антон Cross Афанасьев, 27 января 2010 г. 12:06:50 |
Уважаемый администратор, где вы брали тесты?)
Конечно, вы говорили уже, что числа во всех строчках распологаются не в нужном попядке,
но я подозреваю что тестов наподобие
4 1
3 4
2 3
1 2
0
У вас нет, поэтому проходит без сортировки=)
|
|
|
| 33 Dimash, 17 октября 2009 г. 19:22:14 |
Может ли быть такой тест
5 4
1 4
2 3
4 2
4 1
0
Не может быть 1я лошадь быстрее 4й и 4я быстрее первой одновременно.
|
|
|
| 34 Мехрдод ТРГИ[9"А" team], 01 августа 2009 г. 2:35:54 |
| Какие графы??? Бегаешь по массиву и все!
|
|
|
| 35 Doszhan Damir KARKTL, 25 марта 2009 г. 9:31:25 |
Здраствуйте админ а должны ли веденые числа быть возрастающем Например 5 1 1 2 2 3 3 4 4 5 может быть что было бы так 5 1 2 3 1 2 4 5 3 4
Разумеется, порядок пар может быть любым, не обязательно по возрастанию. Из 3го примера это не видно разве?
|
|
|
| 36 С.С.М., 11 марта 2009 г. 16:21:58 |
Можете сказать что будет в таком тесте: 5 1: 1 2, 2 3, 3 4, 4 5, 5 1? И существуют ли такие?
Такого теста быть не может. Тут у нас выполняется свойство транзитивности, т.к. в условии задачи сказано: "У всех лошадей разные скорости", это как раз для определенности. Хотя если были бы подобные циклы, то выводить следовало бы No.
|
|
|
| 37 Демиденко Виталий, 10 февраля 2009 г. 18:35:59 |
-> 1 3 1 2 1 4 2 3 3 4 4 2
Такие данные являются корректными? Т.е. зацикливание может попасться?
Подобных тестов быть не может. Предполагается, что свойство транзитивности должно выполняться. В вашем примере получается что одна лошадь быстрее и медленнее другой одновременно.
|
|
|
| 38 Михаил Григорьевич, 29 января 2009 г. 19:27:36 |
Если программа не прошла тест, реально ли взять где то этот тест, чтоб самому все проверить?
Реально придумать контрпример самостоятельно, на котором ваша программа работает неверно.
|
|
|
| 39 Мехрдод ТРГИ [Я сам себе team], 02 января 2009 г. 18:08:08 |
Скажите пожалуйста вот если 1 победила 2, а 2 победила 3 это автоматически означает что 1 победила 3?
Разумеется, свойство транзитивности здесь выполняется.
|
|
|
| 40 Бормотов Виталий Борисович, 27 ноября 2008 г. 20:04:05 |
1-й тест совпадает с примером?
да
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
