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



Joined: 17/10/2016 12:24:37
Messages: 3
Offline

Пробувам да ја решам задачата спот од МОИ, ама работи само на 2/20 тестови (останатите се со погрешен резултат). Од секое поле пуштам рекурзија за да наоѓа уште можни начини. Еве го кодот:



Идеја?
MOI



Joined: 07/07/2010 16:31:48
Messages: 447
Offline

Тео wrote:Пробувам да ја решам задачата спот од МОИ, ама работи само на 2/20 тестови (останатите се со погрешен резултат). Од секое поле пуштам рекурзија за да наоѓа уште можни начини.


Незнам што сакаш да направиш во функцијата rek(), таму имаш грешка. Веројатно сакаш да направиш нешто вака (види поправен код долу):


Сега веќе не дава "Погрешен одговор", и поминува на повеќе тест случаи. Но, постојат многу начини кои твојата рекурзија треба да ги испита.
Идеја: Што ако користиме динамичко програмирање, или со помош на битови како 0001010100..11010 (каде битот означува посетеност vis) се обидеме да не пресметуваме одредени патишта повеќе пати?
Тео



Joined: 17/10/2016 12:24:37
Messages: 3
Offline

Фала многу, тоа е отприлика истото што го замислував, лошо сум го имплементирал. Инаку сакав прво да направам brute force алгоритам за после да го додадам динамичкото. Сега ќе пробам да го оптимизирам. Фала многу!
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

Probav dinamicko ama dobiva Runtime Error na povekje testovi (izgleda bara premnogu memorija?): https://pastebin.com/S4TG5782
Isto taka probav Meet In The Middle, sto e pobrzo ama dobiva Runtime Error na istite testovi: https://pastebin.com/34V0q9GH
Moze da mi pomogne nekoj?
petarsor



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

VlatkoSh wrote:Probav dinamicko ama dobiva Runtime Error na povekje testovi (izgleda bara premnogu memorija?): https://pastebin.com/S4TG5782
Isto taka probav Meet In The Middle, sto e pobrzo ama dobiva Runtime Error na istite testovi: https://pastebin.com/34V0q9GH
Moze da mi pomogne nekoj?

Мислам дека си во право, дека со твојот код ќе имаш проблем со меморија.
Ова е лесно и да го провериш (пробав јас кај мене, стварно користи доста повеќе од 64 мегабајти на пример на 5-тиот пример). Само додади едно system("pause") на крајот и отвори Task Manager (претпоставувам користиш Windows), ќе видиш колку меморија се користи.

This message was edited 1 time. Last update was at 16/12/2018 00:31:02

VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

Da, najverojatno toa e. Dali ima nekoj drug nacin da se implementira dinamicko? (deka toa go rece MOI) Ili dali moze da se resi na drug nacin? Nemam ideja vekje.
petarsor



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

VlatkoSh wrote:Da, najverojatno toa e. Dali ima nekoj drug nacin da se implementira dinamicko? (deka toa go rece MOI) Ili dali moze da se resi na drug nacin? Nemam ideja vekje.

Па така е некако, ама е доста сложена задачата. Чисто околу меморија, јас имам само три низи до [1 << 21], и тоа е, така да може да се реши.
Сега незнам дали да објаснувам оти не сакам скроз да ја решам тука, ама ќе видам деновиве - можеби ќе пратам повеќе идеи/објаснување.
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team