[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Палиндроми  XML
Forum Index » Задачи од национални натпревари
Author Message
despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

Здраво,
Имам прашање за задачата Палиндроми http://mendo.mk/Task.do?id=477
Успеав да најдам две "алчни" решенија, но не добивам точни одговори за сите случаи. Може само некој да ми помогне во која насока да размислувам за динамично решение?
Фала однапред
addictus


[Avatar]

Joined: 08/10/2010 11:22:51
Messages: 23
Location: Куманово
Offline

Greedy не поминува за оваа задача. За динамичко, може задачава да се претстави како варијација на knapsack проблемот, но со посебен услов (на бројот S не смееш да додадеш палиндром поголем или еднаков на S).

Станува збор за еднодимензионална низа каде:
DP [x] - најмал број на палиндроми што треба да се додадат на S за да го добиеш бројот x.
DP [S] = 0

За ова ќе ти е потребно претходно да ги имаш генерирано сите палиндроми од 2 до 99,999.

Сложеност : O(E * N) каде што E е бројот што треба да го добиеш а N е бројот на палиндроми што постојат (1,097 вкупно).

Решенија на задачи - aandevski.wordpress.com
[WWW]
filipdimitrovski



Joined: 04/09/2015 21:57:38
Messages: 2
Offline

@addictus
@despotovski

Не ми се јасни примерите кај „Палиндром“, како може ова да е најкраток пат од 7 до 53:



Според мене, ова е пократок:


EDIT:
нвм, требало секој палиндром да е помал од S, a не E.

This message was edited 1 time. Last update was at 05/09/2015 00:09:57

MODDI



Joined: 27/12/2017 18:17:00
Messages: 39
Offline


Ја решавав задачава со Дијкстра, кодов ми вади 3 точни тест примери, 3 погрешни, а останатите Runtime Error, кај ми е грешката ја неможев да ја пронајдам
petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

MODDI wrote:Ја решавав задачава со Дијкстра, кодов ми вади 3 точни тест примери, 3 погрешни, а останатите Runtime Error, кај ми е грешката ја неможев да ја пронајдам


Кога користиме Dijkstra, сакаме да ги посетуваме темињата според растојание (најпрвин оние кои се најблиску до почетокот / најмалку операции на пример), па затоа и користиме priority_queue. Ти не ги споредуваш по растојание, па потоа чуваш повеќе решенија за до последниот број, итн.

Вака треба да се поправи (спореди го со твојот код, има само неколку промени).
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team