Дават пари

1500 лв. от PC Magazine.

За мен задачата е много лесна.

кое и е лесното.
Аз я гледах преди една седмица нямам никаква идея

И от тото дават
при 1:13000000

Бих казал 1:14'000'000. 13'983'816 ако не ме лъже паметта. Всъщност има 3 тегления и сметката не е точно такава. Освен това 1'500 лв се печелят с 5-ца, а там шансът е значително по-висок.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

За мен задачата е много лесна.

Famous last words

Сигнатура!

Интересно как така ти се е видяла лесна тази задача, след като стотици учени десетки години се опитват да намерят оптимално решение, без да се налага да се изчислява 1 милион години (задачата е NP пълна)... При твоето решение можеш ли да определиш колко близо си до оптималното решение?

Чакам отговор.
Поздрави на всички: Дарки

Ако беше НП-пълна може би нямаше да я дадат с конкурса и тя наистина не е.
Помисли още малко. Явно говориш за прост път в произволен граф. Има още информация в условието която може да се използва.
Нали не искаш да ти кажа как съм я решил :)

Малка поправка:

...най-дълъг прост път в произволен граф...

Абе то скоро тука един друг гений беше решил НП пълна задача с динамично програмиране...

Колкото до условието - забележи, че класирането ще е по дължината на намериния низ, което е идеално като за НП пълна задача - кой колкото успее.

Е- може наистина да не е НП пълна - не съм я мислил - само коментирам :)

Сигнатура!

. Не. не искам да ми кажеш как си я решил. При максимални стойности на входните данни за колко време намираш решението?

А - и точно тези момци преди време дадоха на финала една задача дето даже не можеше да се нарече задача - там за търговия с курсови разлики.... така че правете си изводите

Сигнатура!

[линк]

около 6-7 сек. на 800МХз и 256 РАМ.

Колкото до класирането - задачата може да се реши и по грубия начин което налага някакво приближение.

v tototo davat ne pri 1:13000000, a to4no pri:13983816

Няма никакво значение колко е точно. Важното е, че достатъчно голямо число, което не пречи хиляди българи да си трошат парите. За 5 е около 1:54000.
Ако в БГ има 150 милионера(а те със сигурност са повече), то всеки един от нас на 54000 е милионер, без да е играл 6 от 49.
Като обобщение - има много по-лесни начини да изкараш 1500 лв, отколкото да участваш в конкурси на списания, игри и други подобни. А колкото до решаването на задачите - може да си правиш и безплатно.

Иначе на ентусиастите им пожелавам успех