Эта тема будет местом обсуждения курса “Алгоритмы на графах” для 3 курса ПМИ. Задавайте вопросы по курсу, задачам и пр.
Страница с материалами курса.
Тестирующая система ejudge.
1 лайк
Организационный момент. Занятия по курсу по выбору 11 и 18 сентября будут проходить по следующему расписанию: 08:20 - 9:20 Штейнберг Р.Б. ауд 312 09:30 - 10:30 Прозоров О.А. ауд 312 10:40 -11:40 Лапина П.А. ауд 312 За эти два занятия студенты должны сделать выбор на какой курс будут ходить. Затем занятия начнутся по стандартному расписанию.
1 лайк
Роман Борисович, не могли бы Вы задачки выложить?
1 лайк
Я говорил об этом. Задачи еще не все проработаны. И потом, у вас будет фиксированный срок выполнения, а значит заранее выкладывать не логично.
Но я наверное, выложу список алгоритмов, которые вы будете осваивать в течение семестра.
Я про те задачи на графы, которые Вы нам на дом на лекции дали
1 лайк
Спасибо, за напоминание. Только вот я не помню в точности какие именно задачи задал 
Пристегиваю, если что, пишите.
SimpleProblems.txt (972 Байта)
1 лайк
на всякий случай напоминаю, что очень жду (и думаю, что не одна) публикации 16-го теста)
Тесты для третьей задачи изменены.
Для новых тестов плавающее ограничение: MD <= 10^8 заменено на фиксированное M <= 3*10^5, D <= 100.
В условие также будут внесены правки.
TL, вероятно, теперь снова будет 1 сек.
Выложил описание решения задачи 3 на странице курса. Если есть затруднения с этой задачей, то почитайте.
Здравствуйте, а можно ли получить входные данные для любого из (19, 21,56…59,63…63) теста? У меня там bad_alloc, я не могу понять, где.
Скажите, пожалуйста, корректен ли этот тест? Ведь магистрали 1-0 не существует, почему следует выводить 500000000000000000?
====== Test #52 =======
--- Input: size 245 ---
10 9 100 2
0 9
0 1 1000000000000000000
1 2 1000000000000000000
2 3 1000000000000000000
3 4 1000000000000000000
4 5 1000000000000000000
5 6 1000000000000000000
6 7 1000000000000000000
7 8 1000000000000000000
8 9 1000000000000000000
1 1 0
100 0 1
--- Output: size 4 ---
0
0
--- Correct: size 21 ---
500000000000000000
0Тут накладка вышла с моей стороны. В условии д.б. сказано, что x,y - номера узлов, а не начало и конец. Т.е. запрос надо, вообще говоря, как запрос о двух дугах рассматривать.
Скажите, а разве в этом тесте на третий день симуляции магистраль 9-7 будет иметь тот размер, что указан в сообщении об ошибке?
День 1: диверсия по 9-7-5 (capacity = 588001319581652115)
День 2: диверсия по 9-4-5 (capacity = 320613046409404996)
День 3: диверсия по 9-8-7-5 (capacity = 294000660000000000)
Разве 9-7 должна была уменьшится в 4 раза, а не в 2?
====== Test #25 =======
--- Input: size 822 ---
10 30 5 20
9 5
4 7 74928506950349922
9 1 373925908984776917
9 8 972250890526501809
8 0 423999170667188518
2 1 306205715340643447
9 4 417098971970506678
3 7 381339307753772831
8 5 101807494972750026
4 0 370999761453784420
9 0 20601576973684692
8 1 499792017551267180
3 6 327097203372232340
9 7 868469419965169287
3 2 157038191708994110
8 2 992617477589100728
7 1 43268545412731319
4 5 320613046409404996
6 0 693061152091990781
7 5 588001319581652115
3 9 568717610694300459
8 7 488655298096618831
4 2 598043820763296289
9 6 233928550520803794
3 5 942090495914546416
0 1 872557931923501382
7 0 242006832077227460
9 2 687110155190910873
3 8 519962453658382641
3 4 205520315039065959
0 2 818189304521702602
4 8 1
1 8 7
5 3 8
3 9 7
2 8 2
4 9 4
5 4 5
5 7 5
2 8 7
1 3 9
5 3 5
3 9 8
2 3 8
2 9 0
2 9 0
3 3 9
5 4 7
3 4 7
3 0 1
5 3 5
--- Output: size 374 ---
499792017551267180
488655298096618831
519962453658382641
434234709982584643
992617477589100728
104274742992626669
80153261602351249
73500164947706514
488655298096618831
568717610694300459
942090495914546416
486125445263250904
519962453658382641
20601576973684692
20601576973684692
568717610694300459
74928506950349922
74928506950349922
872557931923501382
942090495914546416
--- Correct: size 374 ---
499792017551267180
488655298096618831
519962453658382641
217117354991292321
992617477589100728
104274742992626669
80153261602351249
73500164947706514
488655298096618831
568717610694300459
942090495914546416
972250890526501809
519962453658382641
20601576973684692
20601576973684692
568717610694300459
74928506950349922
74928506950349922
872557931923501382
942090495914546416
--- Stderr: size 24 ---
sh: 1: pause: not found
--- Checker output: size 94 ---
wrong answer 4th numbers differ - expected: '217117354991292321', found: '434234709982584643'Почему в 3й день такая диверсия? 9-7-5 с той же пропускной способностью, но лексикографически меньше.
такие диверсии будут
9 7 5
9 4 5
9 7 5
9 4 5
9 7 5Последний тест не проходит по TL. Нет мапов. Нет сетов. Всё, что можно, отсортировано и найдено двоичным поиском.
У меня все прекрасно компилится, но ejudge выдает error. В чем проблема? http://ipic.su/img/img7/fs/Bezymyannyj.1446643000.png
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021