Author |
Message |
|
Perez wrote:a kaj mene sho e problemov ? nesto ne sum ja sfatil zadacava ubavo ili ?
Да, задачата кажува дека имаш два стека, така да мора елементите да ги вадиш од врвот на стекот (како што пишува и во задачата). Твоето решение ги сортира сите елементи, што не се усогласува со начинот на кој работи стекот, а притоа и твојот greedy пристап не би продуцирал оптимално решение и да беше задачата таква како што си ја сфатил (размисли за гранични случаи кога имаш многу мали наспроти големи броеви).
|
|
|
Јас успеав да ја решам задачата со динамичко програмирање. Бидејќи се работи за огромни броеви, субпроблемите ќе ги чуваме во хеш мапа. Имено, проблемот за наоѓање на минимален број операции од [a,b] можеме да го редуцираме до наоѓање на решението за [a, b / 2] и да додадеме 1 и за [a, (b-2) / 2] + 2, па го наоѓаме минималниот од нив. Ако b e непарен, тогаш решаваме: [a, (b-1) / 2] + 2 и [a, (b-3) / 2] + 3. Броевите комотно влегуваат во unsigned long long, така да не треба да работиме со стрингови.
|
|
|
Решението со мемоизација со матрица ќе го надмине меморискиот лимит. Во најлош случај, ќе имаме 1*10^8 полиња, ако работиме со int матрица секое поле зафаќа 4 бајти меморија, па добиваме вкупна потрошена меморија од над ~381.5 мегабајти. Исто така се приметува дека за празна подматрица (односно подматрица во која нема погодувања) е многу лесно да се најдат сите можни комбинации, тоа може да се заврши во O(1) време со едноставна формула. Според ова, мојата идеја е да се подели матрицата на разделени интервали и да се најдат посебно за нив сите можни комбинации, па да се соберат. Секако, нема да ја чуваме во меморија целата N*M матрица, туку одвоените интервали. Останува уште да се напише кодот.
|
|
|
OverflowException добиваш кога на променлива од даден тип ќе добие вредност надвор од опсегот, како што е со твојот случај. Кога ќе се пресмета сумата, се добива вредност надвор од опсегот на int (-2,147,483,648 до 2,147,483,647). Смени го int со long и ќе немаш проблем.
|
|
|
Здраво,
Имам прашање за задачата Палиндроми http://mendo.mk/Task.do?id=477
Успеав да најдам две "алчни" решенија, но не добивам точни одговори за сите случаи. Може само некој да ми помогне во која насока да размислувам за динамично решение?
Фала однапред
|
|
|
Здраво, да ве прашам, дали при пријавување за натпреварот треба да кажеме во која натпреварувачка група се натпреваруваме како лани или не?
Поздрав.
|
|
|
Имам проблеми со задачава Пораки http://mendo.mk/Task.do?id=4 . Моето решение работи секогаш освен кога во низата ќе се појави знакот v. Тоа го испробав со задавање на вредност на двете низи v. Иако низите беа идентични, програмата сепак ми врати НЕ. Еве скриншот: http://i.imgur.com/I82xxt1.png Навистина не сваќам каде ми е грешката и ве замолувам да ми помогнете. Еве го мојот код:
|
|
|