[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: addictus
Forum Index » Profile for addictus » Messages posted by addictus
Author Message
darko bundoski wrote:може ли да ми ажете каде имам грешка?
пробувам да најдам каде сум згрешил ама немозхам...
задачава ја решив со дводимензионална низа, можно ли да ми дава грешка заради кодот?


N и M можат да идат до 1 милион, додека тебе матрицата ти е 1000х1000. Исто така за поголеми вредности на N и M овој код не би завршил за 1 секунда. Барај решение со помалку циклуси и по можност без матрица.
Прво пробај да откриеш во кои случаи треба да се печати -1. Кога го откриеш тоа можеш да елиминираш голем дел од просторот за пребарување и да ја намалиш сложеноста на задачата.

Хинт: преостанатиот простор за пребарување го претставуваш како граф.
Немаш дефинирано почетна вредност на променливата i во фор циклусот, така да резултатот на твојата програма е непредвидлив.

На влезот ти е дадено колку работни денови подоцна започнало полугодието. Доколку инпутот е 36, значи веќе поминале 7 седмици, додека твојот код би забележал дека поминале 5 седмици.

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

За крај, примерот си го разбрал обратно. На пример 7 се внесува 16 а output-от е 1, што е точно.
freetree66 wrote:Go postiram kodot dokolku mu pomogne na nekogo da prilozi odgovor



Ova se test slucaevite :

1. Za v {0}; Expected result: 0 ; Your result: 0
2. Za v {1}; Expected result: 0 ; Your result: 0
3. Za v {-1840512878, -2147418112}; Expected result: 307036306 ; Your result: "NULL" ; Description: Mismatch -> OverflowException;


Како што ти одговорија погоре, не можеш да користиш int тука. Конкретно за твојот случај, (-1840512878 ) + (-2147418112) = -3987930990, што е повеќе од тоа што може да собере во int променлива. Така да не мора да се врати вредност од типот int.
Што би се случило доколку се внесат 1,000,000 играчи, сите од различни групи? Тогаш твојот код ќе функционира приближно како да имаш 2 вгнездени for циклуса кои идат до N (вкупно N * N операции), што е премногу за да се изврши во 3 секунди. Потребно ти е линеарно решение (без вгнездување на циклуси).

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

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

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

Сложеност : O(E * N) каде што E е бројот што треба да го добиеш а N е бројот на палиндроми што постојат (1,097 вкупно).
Доколку имаш некоја идеја, зошто не пробаш? Доколку мислиш за оваа задача, не гледам како weighted interval scheduling би помогнало тука (без разлика дали оптимизираш со RSQ). Имаш попросто решение со линеарно изминување (нешто налик на задачата со светилки од последниот училишен натпревар).
Dist матрицата која ја користиш зафаќа 382MB меморија, дозволено е само 64MB.

Дадени се највеќе 100,000 познати растојанија. Да кажеме дека сакаш дупло да ги запишуваш (a->b и b->a растојанија во посебни променливи, иако се исти), тоа се 200,000 променливи. Ти за таа намена користиш 100,200,000 променливи. Барај пооптимален начин за запишување на графот.
Бидејќи променливата i е од тип int, пресметките во 19-тиот ред (20*i и 10*i) исто така се вршат во тип int. Но бидејќи овој циклус иде до големи броеви(како 166,666,670 за тест примерот што го даде), при множење на овој број со 20 ти го надминуваш ограничувањето на int (кое е 2,147,483,647). Можеш пресметките во 19тиот и 21виот ред да ги кастираш во long long, или пак променливата i да ја направиш long long, со што ќе се реши овој проблем.

Но сепак со такви големи броеви, и да имаш точен резултат, ќе го надминеш временскиот лимит. Пробај да ја оптимизираш задачата (можеби некое решение кое не користи циклуси?).
andre112 wrote:Ne najdov odgovor na ovie prasanja na stranata , dali ke mozete da me linkirate ?


Линк до официјалните правила

Иначе како одговор на твоите прашања:
- Нема задачи кои бараат објективно програмирање со класи (сите задачи можат и без класи да се решат, но вие може да употребите класи доколку сакате).
- Немате пристап до интернет, освен сајтот на мендо и STL документацијата.
- Има повеќе од една задача (вообичаено 4-5, зависи од натпреварот).
- Единственото нешто што се бодува е точноста на програмата (дали го дава точниот резултат) со дадените ограничувања (временско и мемориско ограничување). Без разлика дали ја решите за 5 минути или 3 часа, исто се бодува.
- Кодот се праќа на Мендо, или со копирање на кодот или со прикачување на изворниот фајл.
- Се користи Free Pascal 2.6.2 и Code::Blocks 13.12 (ова според правилата, но според искуство сум сретнувал постари верзии на codeblocks).
- Мислам дека не може да се учествува на натпреварот со свој лаптоп (но не сум 100% сигурен)

Овие одговори се според тоа како се одржувал натпреварот изминатите години и што имам запаметено. Сепак би ти препорачал да ги прочиташ официјалните правила кои се ставени на линкот горе.
stevo wrote:Некој хинт, како да ја подобрам брзината на оваа задача имам. На 6 тест случаи надминат лимит, друго се во ред..


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

Доколку ептен заглавиш, го имам решението објаснето тука
Каква помош поточно бараш? Што се обиде до сега, каде заглави, што не ти е јасно? Биди поспецифичен, па ќе пробаме да ја разјасниме задачава. Доколку бараш готово решение на задача, нема да добиеш тука.

Во задачата имаш некој артефакт со N фрлени магии, и N волшебници кои можат да ги тргнат тие магии. Секој волшебник може да тргне M магии + неговата, M е дадено за секој волшебник.

Да го разгледаме тест примерот:

5 - број на фрлени магии - N
3 - број на магии што ќе ги отстрани првиот волшебник - M1
2 - број на магии што ќе ги отстрани вториот волшебник - M2
1 - број на магии што ќе ги отстрани третиот волшебник - M3
1 - број на магии што ќе ги отстрани четвртиот волшебник - M4
0 - број на магии што ќе ги отстрани петтиот волшебник - M5

Првиот волшебник ќе отстрани 3 магии, + уште една (негова), вкупно 4. Што значи дека ќе остане уште 1 магија.
Вториот волшебник може да отстрани 2 магии + уште една (негова), вкупно 3. Ќе ја тргне таа 1 магија.

Потребни се вкупно 2 волшебника, печатиме 2.
nightCoder wrote: уше деветиов заебава, не ми е јасно више се изврзав..



Повторно користиш циклус кој не постигнува ништо(се повторува N пати без причина и на крајот дава -1). Тука имаш некои лекции за циклуси, не би било лошо да ги повториш. Секогаш кога можеш завршувај ги циклусите со дефиниран услов во нив (на пример while(услов)) наместо да ги прекинуваш со break. Условот за 2 кршења не ти е добар, и во претходниот пост ти реков дека за тој тест пример нема да работи задачата и ти препорачав начин за решавање (кој сеуште го немаш пробано).
nightCoder wrote:' pomosh tuka.. se vrzav vishe

Како прво, не ја гледам причината зошто го користиш тој for циклус. Во никој од првите 4 услови не го користиш бројачот i, а петтиот услов го користиш за да го прекинеш циклусот за што нема потреба (за овој случај поточно циклусот ќе се извршува за i од 0 до kocki, потоа i<=kocki условот веќе не важи и сам се прекинува). Всушност само ги повторуваш истите 4 споредувања повеќе пати.

Следниот проблем е што користиш int. Може да добиеш проблеми со redovi*koloni за некои поголеми вредности, така да наместо int користи long long.

Без циклусот и со поголеми променливи кодот ти проаѓа на 19/20 примери. Единствениот пример каде што програмот ти паѓа е

каде што може да се добие бараниот број на коцки со чоколадо 21379х88289 додека твојот код дава -1.


Малку поголема помош (ќе оставам на тебе да си го искуцаш кодот) :
Пробај да ги најдеш сите можни начини да добиеш N број на коцки (пример за 12 коцки можеш со 1х12, 2х6, 3х4). Види дали можеш да стигнеш до некој од тие начини со едно кршење, доколку не можеш, види дали можеш да стигнеш до некој од тие начини со две кршења, доколку не можеш печати -1. (нормално, печатиш 0 доколку веќе е решена задачата).
nightCoder wrote:лелее искинав живци на третиов случај како пример шо е.. ајде помагајте куку леле е работава
http://mendo.mk/Task.do?id=476
ако може и решение цело


Да го ставеше твоето решение па да ти кажеме каде грешиш?

Инаку конкретно за третиот пример

Единствениот начин за да добиеш чоколадо со 811 коцки е тоа чоколадо да е 811х1 (бидејќи бројот 811 нема други делители). Со даденото чоколадо (810х753) не постои начин да добиеш 811х1 чоколадо.
 
Forum Index » Profile for addictus » Messages posted by addictus
Go to:   
Powered by JForum 2.1.8 © JForum Team