[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Некоја насока за решавање на задачата Дедо Мраз од училишен 2019?  XML
Forum Index » Задачи од национални натпревари
Author Message
Scratcher



Joined: 21/01/2013 16:53:12
Messages: 14
Offline

http://mendo.mk/Task.do?id=850

Немам никаква друга идеја за решавање на оваа задача освен со рекурзија(backtracking)
каде пробувам секој број од едната низа да го сведам во број од другата низа, а потоа рекурзивно решавам за следната состојба

Поконкретно, паѓа на овој тест пример

9
1 14 22 11 6 11 14 1 24
5
34 37 20 8 5

каде:

очекувано: 8
добиено: INT_MAX(не наоѓа решение)

Еве го кодот


Забелешка: На МЕНДО 9/20 се точни а останатите се погрешен резултат или надминат временски лимит
longhi



Joined: 16/01/2019 22:52:02
Messages: 18
Offline

Scratcher wrote:Немам никаква друга идеја за решавање на оваа задача освен со рекурзија(backtracking)


Втората акција што може да ја направи роботот (две вреќи да се спојат во една) е многу поедноставна од првата (бидејќи таму треба да одлучуваме колку подароци да префрлиме).
Ова може да го средиме така што првата операција воопшто нема да ја правиме, туку ќе ја правиме само втората - но во две насоки, т.е. почнувајќи и од почетната состојба (како што се ќесите спакувани на почеток) и од крајната состојба (како што треба да бидат спакувани). Ова има логика бидејќи едната акција на роботот е слична на втората - само обратно - наместо да спојуваме две вреќи во една, делиме една вреќа на две.

Значи, можеме да напишеме програма која што ќе користи неколку идеи
1) Да пресметаме со колку акции може да се стигне од една состојба до сите други со спојување на вреќи (за тоа може да се искористи queue - слична идеја како кај алгоритамот BFS)
2) Ако од почетната состојба можеме да дојдеме до некоја состојба X, и од крајната состојба може да дојдеме до истата таа состојба X - тогаш може да се стигне од почетната состојба до крајната состојба. Притоа, ако требаат A чекори за да се стигне од почетната состојба до X, и B чекори за да се стигне од крајната состојба до X, тогаш за доаѓање од почетната до крајната состојба преку X требаат вкупно (A+B) чекори.

Ако е уште нејасно, еве решение
Scratcher



Joined: 21/01/2013 16:53:12
Messages: 14
Offline

Благодарам за идејата, еве ја мојата имплементација

This message was edited 1 time. Last update was at 09/06/2019 23:41:35

 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team