Äèíàìè÷åñêîå ïðîãðàììèðîâàíèå; ðàçáîð çàäà÷ Îòêðûòîé îëèìïèàäû
Íà÷èíàåì ðàçáîð çàäà÷ VII Îòêðûòîé îëèìïèàäû øêîëüíèêîâ ïî ïðîãðàììèðîâàíèþ, 2012/13 ó÷åáíûé ãîä
- Óñëîâèÿ ïðèìåíåíèÿ ìåòîäîâ äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ
- Ðàçáîð ïðîñòîé çàäà÷è (?ïëàòíàÿ ëåñòíèöà?)
Ðàçáîð óæå ðåøåííûõ çàäà÷: ?ïîñëåäíÿÿ öèôà ÷èñëà Ôèáîíà÷÷è?, ?Ïîêóïêà áèëåòîâ?
Ðàçáîð çàäà÷è 1-B oolym-2013-1-bN.py
Äîìàøíåå çàäàíèå
Ïðî÷èòàòü ïðî äèíàìè÷åñêîé ïîäõîä íà ñàéòå MCCME (ññûëêè ?Òåîðåòè÷åñêèé ìàòåðèàë? íà ñòðàíèöå çàäà÷ ïî äèíàìè÷åñêîìó ïðîãíðàììèðîâàíèþ) - Çàïðîãðàììèðîâàòü ãåíåðàòîð âõîäíûõ äàííûõ è ðåøåíèå çàäà÷è ?ïëàòíàÿ ëåñòíèöà?:
- Ìàëü÷èê ïîäîøåë ê ïëàòíîé ëåñòíèöå. ×òîáû íàñòóïèòü íà ëþáóþ ñòóïåíüêó, íóæíî çàïëàòèòü óêàçàííóþ íà íåé ñóììó. Ìàëü÷èê óìååò ïåðåøàãèâàòü íà ñëåäóþùóþ ñòóïåíüêó, ëèáî ïåðåïðûãèâàòü ÷åðåç ñòóïåíüêó. Òðåáóåòñÿ óçíàòü, êàêàÿ íàèìåíüøàÿ ñóììà ïîíàäîáèòñÿ ìàëü÷èêó, ÷òîáû äîáðàòüñÿ äî âåðõíåé ñòóïåíüêè.
 ðåøåíèè çàäà÷è 1-B ïðèñóòñòâóåò îøèáêà: ðàññìàòðèâàþòñÿ âàðèàíòû, â êîòîðûõ ÷èñëî ïåðåä vi ìîæåò ñîñòîÿòü èç îäíèõ òîëüêî íóëåé. Èñïðàâèòü åå.
?Ìàðøðóò ÷åðåïàøêè? (MCCME).  ëåâîì âåðõíåì óãëó ïðÿìîóãîëüíîé òàáëèöû ðàçìåðîì N?M íàõîäèòñÿ ÷åðåïàøêà.  êàæäîé êëåòêå òàáëèöû çàïèñàíî íåêîòîðîå ÷èñëî. ×åðåïàøêà ìîæåò ïåðåìåùàòüñÿ âïðàâî èëè âíèç, ïðè ýòîì ìàðøðóò ÷åðåïàøêè çàêàí÷èâàåòñÿ â ïðàâîì íèæíåì óãëó òàáëèöû. Ïîäñ÷èòàåì ñóììó ÷èñåë, çàïèñàííûõ â êëåòêàõ, ÷åðåç êîòîðóþ ïðîïîëçëà ÷åðåïàøêà (âêëþ÷àÿ íà÷àëüíóþ è êîíå÷íóþ êëåòêó). Íàéäèòå íàèáîëüøåå âîçìîæíîå çíà÷åíèå ýòîé ñóììû è ìàðøðóò, íà êîòîðîì äîñòèãàåòñÿ ýòà ñóììà.
Ôîðìàò âõîäíûõ äàííûõ.  ïåðâîé ñòðîêå âõîäíûõ äàííûõ çàïèñàíû äâà íàòóðàëüíûõ ÷èñëà N è M, íå ïðåâîñõîäÿùèõ 100 ? ðàçìåðû òàáëèöû. Äàëåå èäåò N ñòðîê, êàæäàÿ èç êîòîðûõ ñîäåðæèò M ÷èñåë, ðàçäåëåííûõ ïðîáåëàìè ? îïèñàíèå òàáëèöû. Âñå ÷èñëà â êëåòêàõ òàáëèöû öåëûå è ìîãóò ïðèíèìàòü çíà÷åíèÿ îò 0 äî 100.
Ôîðìàò âûõîäíûõ äàííûõ. Ïåðâàÿ ñòðîêà âûõîäíûõ äàííûõ ñîäåðæèò ìàêñèìàëüíóþ âîçìîæíóþ ñóììó, âòîðàÿ ? ìàðøðóò, íà êîòîðîì äîñòèãàåòñÿ ýòà ñóììà. Ìàðøðóò âûâîäèòñÿ â âèäå ïîñëåäîâàòåëüíîñòè, êîòîðàÿ äîëæíà ñîäåðæàòü N-1 áóêâó D, îçíà÷àþùóþ ïåðåäâèæåíèå âíèç è M-1 áóêâó R, îçíà÷àþùóþ ïåðåäâèæåíèå íàïðàâî. Åñëè òàêèõ ïîñëåäîâàòåëüíîñòåé íåñêîëüêî, íåîáõîäèìî âûâåñòè ðîâíî îäíó (ëþáóþ) èç íèõ.
Ðåøèòü çàäà÷ó ?Ðàñïèë áðóñüåâ?. Âàì íóæíî ðàñïèëèòü äåðåâÿííûé áðóñ íà íåñêîëüêî êóñêîâ â çàäàííûõ ìåñòàõ. Ðàñïèëî÷íàÿ êîìïàíèÿ áåðåò k ðóáëåé çà ðàñïèë îäíîãî áðóñêà äëèíîé k ìåòðîâ íà äâå ÷àñòè â ëþáîì ìåñòå. Îïðåäåëèòå ìèíèìàëüíóþ ñòîèìîñòü ðàñïèëà áðóñà íà çàäàííûå ÷àñòè.
Ôîðìàò âõîäíûõ äàííûõ. Ïåðâàÿ ñòðîêà âõîäíûõ äàííûõ ñîäåðæèò öåëîå ÷èñëî L (2˜L˜106) - äëèíó áðóñà è öåëîå ÷èñëî N (1˜N˜100) - êîëè÷åñòâî ðàñïèëîâ. Âî âòîðîé ñòðîêå çàïèñàíî N öåëûõ ÷èñåë Ñi (0<Ci<L) â ñòðîãî âîçðàñòàþùåì ïîðÿäêå - ìåñòà, â êîòîðûõ íóæíî ñäåëàòü ðàñïèëû.
Ôîðìàò âûõîäíûõ äàííûõ. Âûâåäèòå îäíî íàòóðàëüíîå ÷èñëî - ìèíèìàëüíóþ ñòîèìîñòü ðàñïèëà.
Ïîïðîáîâàòü ïîðåøàòü çàäà÷è ïåðâîãî òóðà Îòêðûòîé îëèìïèàäû
Óñëîâíûå îáîçíà÷åíèÿ
? òåìà ïî Linux - ?? òåìà ïîâûøåííîé ñëîæíîñòè
- ? òåîðåòè÷åñêîå çàäàíèå
? òåìà äëÿ ñàìîñòîÿòåëüíîãî èçó÷åíèÿ