Ако не можете да решите задачата в зададения й вид, опитайте да я решите да работи в случаите за изцяло ориентиран и неориентиран граф.
C/C++ - Visual Studio 2005
Java - 1.5
C#/CLI/Visual Basic/J# - Visual Studio 2005. Ако изберете някой от тези .NET езици, сложете Visual Studio 2003 или Visual Studio 2005 проекта в архива.
Задачата е порутващо трудна - чак неподходящо трудна. Имайте предвид. Не подценявайте условието. Затова ако решението работи в някои случаи - ще получите пропорционално точки за това. Т.е. различно от досегашните домашни, където искахме 100% успешни решения за да се получат точки.
Какво е поносимото време за работа на алгоритъма?
"Да се намери ойлеров цикъл в графът – т.е. път, който минава през всяко ребро по веднъж."
Значи е достатъчно да намерим само един цикъл, а не всички възможни, ако съм разбрал правилно.
Да речем, за дадения в условието пример, се приема за вярно извеждането само на един от трите възможни отговора.
Ще мога ли да кача новия си файл?
И още нещо. Нали всички знаете какво е мултиграф?
Дайте идея как бих могъл да си тествам алгоритъма с по-голям граф. Търсих в интернет за голям ойлеров граф, но не намерих. Ако някой е имал повече късмет(време) от мен и е намерил такъв, го моля да го сподели с мен и с останалите.
Е все пак не ми се случва често да пиша задачи свързани с графи.
Ако все пак е много наложително - важното е Visual Studio 2005 да го компилира. За C++ сорсовете аз ще компилирам директно с cl - т.е. ако ми дадете проект с разни опции на компилатора - няма да го използвам, а ще изполвам мои си опции.
Най-добрият начин според мен за това е да се съобразяваме със стандартите. Един такъв е C++ стандарта. Не ви препоръчвам да използвате нещата специфично за gcc, а също така и нещата специфично за Visual Studio, т.к. може да подам опция на компилатора да ги изключи.
gcc (GCC) 3.2.3 (mingw special 20030504-1)
Да знаеш, че е много бъгава версия. Не използвай long long.
Възможно ли е и моят код да бъде компилиран с minGW (GCC) ?
По някаква причина, когато компилирам с Visual Studio 2005, програмата забива (препълване на стека) . Знам, че проблема не е в кода, тъй като това се случва единствено при големи графи (максималния вход). За малки графи, програмата работи и във Visual Studio 2005.
Под minGW такъв проблем нямам, независимо от размера на входа.
С mingw ще компилирам само на хора, които по някаква причина, която не мога да fix-на не се компилират с Visual Studio 2005.
![замислен(а) замислен(а)](https://learn.fmi.uni-sofia.bg/pix/s/thoughtful.gif)
Решенията на java са получили половин секунда бонус.
Това, че няма максимум точки (постигантият максимум е 29) не значи, че никой няма да получи максимум точки от домашни - както казахме ще scale-нем точките от домашни така, че максимум бонус от домашни ще се получава например при поне 75 точки (или 60 или друг броя) събрани от всички домашни.
Забележете, че ако сте преписали или дали да препишат това домашно трябва да се запишете на https://learn.fmi.uni-sofia.bg/mod/forum/discuss.php?d=318 и да се откажете от всички бонус точки от домашни.
Тестовете са тук
А и още нещо: Как може един алгоритъм с сложност 2N да е оценен с 18 точки, а алгоритъм с полиномиално време да е оценен с 19 (в случая - моя :-D)
Като си заговорихме за добри алгоритми - хубав алгоритъм би трябвало да е базиран на Matching или Maximum Flow, а не на random неща. Но 20-30 точки също не е зле - Maximum Flow трябва доста да се оптимизира за да влезне в лимита за време.
Погледни няколко поста нагоре за тестовете
И между другото тестовете са ти 51, а не 50 ;-)
П.П. Ще има ли възможност за контестация, т.е. ако има бъг да го фиксна и да ти го пратя отново?
нулевият тест не се брои в точките :-)
Твоето random решение работи в над половината случаи, но не във всички. На колегата решението би трябвало да работи във всички, но вероятно поради бъг - това не е станало.
Задачата не е NP.
Сега се зачетох в линка на колегата. Изглежда наистина има полиномиално решение на задачата. Това, разбира се, не значи, че евристичното решение е по-лошо.
Вижда ми се странно, че нито едно от изпратените решения не работи за последните тестове. Сигурно ли е, че описаните в тях графи са ойлерови?
A imam 0/50.
Poneje nqkak si ne e chesno tolkova mnogo trud da ide na vqtura ?!
Promenen e samo izhoda.
Formata koito sum spazil e :
<vruh><sp><vruh><sp>...<vruh><sp> ,
kudeto <sp>/(' ') e <space>.
Ako i tova ne e verniq format, molq da go formalizirash po nqkakuv nachin.
Poneje ne sum razbral ot statiqta na zadanieto, propusnato e izrichnoto spomenavane na praznite mesta.
Reshenieto e kacheno na :
http://comtop.hit.bg/pranka/fn43745_oyler.rar
А при това положение остава ли идеята със "scale-ването" на точките от домашни?
точките от домашни се делят на 5. И ако са над 15 - стават 15. Така при 75 и повече събрани точки от домашни, получавате 15 точки. В момента няма човек събрал 75 точки, но има две домашни, които Мило трябва да провери. И от там само максимумът е 70 (теоретично де... не ми се струва възможно някой да победи на играта във всички случаи... не знам как е оценяването там)