[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Messages posted by: petarsor
Forum Index » Profile for petarsor » Messages posted by petarsor
Author Message
SmokiB wrote:Пола од тест случаевите работат... Може некој да ми каже што ми е грешно. Пробувам да ја решам со динамичко програмирање...


Не ти е грешен алгоритамот, меѓутоа треба да знаеш дека int (и long long) имаат ограничен опсег на броеви кои што може да се чуваат во нив. Повеќе можеш да прочиташ тука http://mendo.mk/Lecture.do?id=21

Поради тоа, во вакви задачи, ќе правиш (%MOD) на секој чекор, а не само на крајот (бидејќи тогаш е доцна, веќе во променливата чуваш погрешна/преголема вредност).


Па добро, твојов код користи рекурзија колку да се каже. Самиов кодот можеш да го прекуцаш и без рекурзија.
Поентата кога користиме backtracking е што кога ќе направиме некој потег, продолжуваме натака со рекурзијата како да е тоа правилен потег, меѓутоа после кога се враќаме назад, правиме друг потег во тој чекор.

На пример, замисли три кутии, и сакаме да разгледаме разни ситуации (каде или може да ставиме некое топче во кутија, или да не ставиме).
Со backtracking, во рекурзијата, прво ја гледаме првата кутија и викаме 1) стави топче во првата кутија, и продолжи рекурзивно да ги разгледаш другите кутии.
Потоа, кога рекурзијата ќе се врати назад (кога ќе заврши разгледувањето на другите две кутии), потоа викаме 2) не ставај топче во првата кутија, и продолжи рекурзивно да ги разгледаш другите кутии.
На тој начин разгледуваме разни состојби. Оваа техника е опишана во предавањето за рекурзија/backtracking, но може да се најдат разни примери со пребарување на Google.


Ти не го правиш ова. Може лесно и да се примети од твојот код, бидејќи го зголемуваш "time++" на неколку места и продолжуваш натаму (значи правиш потези), но никаде не ги поништуваш тие потези (да пробаш со нешто друго во тој чекор од рекурзијата).
BATIR wrote:Слични?

Па да, опишаните техники во предавањата за рекурзија (backtracking) - повикување на истата функција за да се разгледаат разни состојби, функцијата да прима соодветни параметри кои ја опишуваат тековната состојба и од таму создавање на други состојби и слично. Ако сме решиле доста задачи со таа техника, другите задачи делуваат слично бидејќи само треба да откриеме кои параметри се потребни за определување на состојба (во новата задача), кои следни состојби се доволни да ги правиме/разгледуваме, итн.
BATIR wrote:Koga kje se znaat regionite kade shto kje se odrzuva ovogodinesniot regionalen natprevar ?

Претпоставувам на почетокот на наредната недела, бидејќи на http://cs.org.mk/index.php/natprevari/srednoobrazovanie/regionalennatprevar/18-rezultati/373 пишува оти пријавувањето било до вчера вечер (па веројатно треба време да се разгледа тоа).
Инаку, не верувам дека ќе бидат објавени такви информации на МЕНДО, туку директно до наставниците кои пријавиле ученици за натпреварот.
Krenkov wrote:Ова задача спаѓа во Ad-hoc проблеми?


Ако сакаш со твојов код, можеш да продолжиш да се обидуваш (сега ја има задачата во тренинг делот на МЕНДО).
Ама, ако сакаш хинт како се решава: (рекурзија) [Има и предавање во делот за алгоритми за користење на рекурзија при решавање на слични задачи]
BATIR wrote:Moze malku podetalno da mi objasnis shto pravis vo 25 red i 26?
Inaku fala mnogu


Ако i=5, наместо да гледаме само растојание до 6-тата точка, може да гледаме до 6, 7, 8, 9, 10, ... итн (ако n е помало, можеме да продолжиме од 0, 1, 2, 3, ... тоа е j%n)
Идејата ми е да се искористи фактот што временскиот лимит ни дозволува да разгледаме повеќе точки.
BATIR wrote:Ajde nekoj pomos, ili hint at least

Не мора само една (следна) точка, можеш да разгледаш повеќе блиски. Вака нешто.

BATIR wrote:Dali voopshto kje ima ucilisen, ili kje se odi direktno na regionalen?


http://cs.org.mk/index.php/natprevari/srednoobrazovanie/regionalennatprevar
BATIR wrote:Nekoja ideja za ovaa zadaca?

Претпоставувам дека зборуваш за задачата од ЈБОИ 2009.
Незнам колку многу помош сакаш, па за да не пишувам, можеш да видиш тука: http://cs.org.mk/jboi2009/tasks.html (sample solutions)
Има и решение (код), и објаснување, така да ќе си најдеш што сакаш.
Стојанов wrote:Напиши програма кој пресметува и печати НЗД на два влезни броја m и н.


Имаш дел за Најголем заеднички делител тука: http://mendo.mk/Lecture.do?id=34
Инаку, ова може да се реши на повеќе начини. Еве два (првиот е поедноставен за разбирање; вториот бара да знаеш што се тоа функции и Евклидов алгоритам)





MODDI wrote:Користам два бфс, еден за одредување на делечината на секое поле до секој затвореник, а другиот за пронаоѓање на максималниот пат до излезот, на пр. прво пробуваме со 3ка, и со бфс одиме на сите полиња кај што има далечина 3ка, ако небива тогаш пробуваме со 3ка и 2ка, и тогаш ако небива пробуваме со 1. Ако може малце помош, не сакам цело решение само што да сменам.


Ќе пробам до некаде да ти помогнам, оти не сакаш цело решение.
Прво, имаш некои проблеми. На пример, во последниот for циклус користиш for(int i=pom;i>0;i--), ама па потоа внатре користиш pom (што не се менува бидејќи ти всушност го менуваш i, па треба тоа да користиш). Ова би го заменил со for(; pom>0 && big == 0; pom--)

Слично, q.push() и memset треба да ги ставиш внатре во тој циклус. И не би проверувал дали (MAT1[next_x][next_y]==pom) туку дали е поголемо или еднакво. Вака нешто (сменет е само последниот дел)



Сега ти поминува наместо на 0/20 случаи на 15/20 случаи. Другото оставам на тебе, да не ја средувам до крај, особено бидејќи несакаш и има напишано решение погоре и можеш да симнеш некој од тие тест случаи.
MODDI wrote:Ако може малку помош ми работи на 7 тест случаеви од можни десет, незнам каде му е грешката , помош!!!

Кај првата овца/волк, кога почнуваш со BFS-то.

Додади кај првото BFS (одма после q.push(at1)) само


и кај второто BFS (одма после q.push(at1)) само


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], и тоа е, така да може да се реши.
Сега незнам дали да објаснувам оти не сакам скроз да ја решам тука, ама ќе видам деновиве - можеби ќе пратам повеќе идеи/објаснување.
BATIR wrote:Da, no neli ako pri trganje na sekoja baricka, da barame dali ima pat pomegju niv kje pominuva na vreme. Zatoa jas go resiv vaka, samo baram popravka . Mislam deka sum blisku


Имаше повеќе грешки. (curr.first+dj[i]==ej) наместо (curr.second+dj[i]==ej), не треба +1 кај maxR и слично.

Еве поправен код.
boolTrue wrote:Фала сега работи, меѓутоа нели го правам истото во горниот код? Сакав да скратам неколку редови код.

Не баш, разгледуваш една позиција (i, j) а печатиш одлуки за друга (m - j, n-i).
 
Forum Index » Profile for petarsor » Messages posted by petarsor
Go to:   
Powered by JForum 2.1.8 © JForum Team