Íåñêîëüêî ââîäíûõ ñëîâ
Ïðåäñòàâëåííûå çäåñü çàäà÷è - ýòî ïîëóãîäîâîé êóðñ (ïî 2 ÷àñà â íåäåëþ) ïî èçó÷åíèþ ïðîãðàììèðîâàíèÿ íà ïàñêàëå ôàêòè÷åñêè ñ "íóëÿ" â 8 ìàòåìàòè÷åñêîì (äîñòàòî÷íî ñèëüíîì) êëàññå. Ìíå áû õîòåëîñü âûðàçèòü ïðèçíàòåëüíîñòü øêîëüíèêàì 8 êëàññà "Â" Ìîñêîâñêîé ãèìíàçèè 1543 (2003-2004 ó÷åáíûé ãîä) çà íàøó ñ íèìè ñîâìåñòíóþ ðàáîòó ïî "îáêàòêå" ýòèõ çàäà÷ :-) .
Ñþäà íå âîøëè 3 ïåðâûõ çàíÿòèÿ, ãäå øêîëüíèêè íå ïîëüçîâàëèñü òåñòèðóþùåé ñèñòåìîé. Óæå íà 4-ì çàíÿòèè ñ íèìè áûëà ïðîéäåíà òåìà "ôàéëû" (áûòü ìîæåò, ýòî íåñêîëüêî ðàíî, îäíàêî ýòî äèêòîâàëîñü íåîáõîäèìîñòüþ èñïîëüçîâàíèÿ ñèñòåìû àâòîìàòè÷åñêîé ïðîâåðêè - äîñòàòî÷íî áîëüøèå ãðóïïû ïðèâîäèëè ê òîìó, ÷òî ÿ íå óñïåâàë ïîäõîäèòü êî âñåì øêîëüíèêàì). Íà ïåðâûõ 3 çàíÿòèÿõ áûëè ïðîéäåíû ââîä è âûâîä äàííûõ (read, write), ïåðåìåííûå (öåëûå, âåùåñòâåííûå), óñëîâíûé îïåðàòîð, öèêëû.
Òåñòèðóþùàÿ ñèñòåìà, èñïîëüçîâàâøàÿñÿ íà çàíÿòèÿõ, áûëà óñòðîåíà òàê, ÷òî â ñëó÷àå îøèáêè (íåïðîõîæäåíèÿ êàêîãî-ëèáî òåñòà) ýòîò òåñò îêàçûâàëñÿ â ôàéëå input.txt â ðàáî÷åì êàòàëîãå øêîëüíèêà. Íà ïåðâûõ ïîðàõ èçó÷åíèÿ ïðîãðàììèðîâàíèÿ, íà ìîé âçãëÿä, ýòî äîñòàòî÷íî îñìûñëåííî, îäíàêî ïîñòåïåííî îò ýòîãî íóæíî óõîäèòü, ÷òîáû øêîëüíèêè ñàìè ó÷èëèñü àíàëèçèðîâàòü óñëîâèå è ïðèäóìûâàòü òåñòû.
Âñå ïðåäñòàâëåííûå çàäà÷è ïðåäñòàâëåíû â ôîðìàòå, ïðèíÿòîì íà ñàéòå www.olympiads.ru. Âíóòðè àðõèâà ñîäåðæàòñÿ óñëîâèå, òåñòû, ïðîâåðÿþùèå ïðîãðàììû. Òàì, ãäå èñïîëüçóþòñÿ äîïîëíèòåëüíûå ïðîãðàììû, îíè òàêæå åñòü âíóòðè àðõèâîâ. Îáðàòèòå âíèìàíèå, â html-âåðñèè ïðèñóòñòâóþò íåêîòîðûå êîììåíòàðèè äëÿ ïðåïîäàâàòåëåé, êîòîðûõ íåò âíóòðè àðõèâîâ! Òàê ñëîæèëîñü, ÷òî çàäà÷è íîìåð 114 â êóðñå íåò - ýòî íå îøèáêà ïðè âûêëàäûâàíèè çàäà÷.
Âû ìîæåòå ñêà÷àòü Âñå çàäà÷è â îäíîì àðõèâå (îêîëî 2,7 Ìá).
Íåñêîëüêî ñëîâ î êóðñå
Îñíîâíîé öåëüþ èçó÷åíèÿ ïðîãðàììèðîâàíèÿ íà ýòîì óðîâíå, íà ìîé âçãëÿä, ÿâëÿåòñÿ íàó÷èòü øêîëüíèêà, ïîíèìàÿ, êàê ðåøàåòñÿ çàäà÷à, èçëàãàòü ñâîè ìûñëè íà ÿçûêå ïðîãðàììèðîâàíèÿ (ïèñàòü ïðîãðàììó). Ýòî ó÷èò øêîëüíèêà ìûñëèòü áîëåå òî÷íî, ÷åòêî, ðàçáèâàòü çàäà÷ó íà ýòàïû.
Âñå ýòî äåëàåòñÿ (â îñíîâíîì) íà î÷åíü ïðîñòûõ è âðîäå áû ïîíÿòíûõ çàäà÷àõ. Ïîíÿòíûõ â òîì ñìûñëå, ÷òî åñëè ïîòðåáóåòñÿ êàêóþ-òî èç ýòèõ çàäà÷ ðåøèòü óñòíî (íå íà êîìïüþòåðå, à ïðîñòî ñ êîíêðåòíûìè âõîäíûìè äàííûìè íà áóìàæêå ïðîäåëàòü òî, ÷òî òðåáóåòñÿ â çàäà÷å), òî ó âîñüìèêëàññíèêà ýòî íå äîëæíî âûçâàòü çàòðóäíåíèé. Ýòî äàåò âîçìîæíîñòü ïðàêòè÷åñêè íà ïàëüöàõ îáñóæäàòü àëãîðèòìû ðåøåíèÿ çàäà÷ è ñîâåðøåííûå îøèáêè.
Ïðàêòè÷åñêè ñ íà÷àëà îáó÷åíèÿ ïðîãðàììèðîâàíèþ ÿ òðåáóþ îò øêîëüíèêîâ óìåíèÿ ïîëüçîâàòüñÿ îòëàä÷èêîì.  ýòîì ñìûñëå òåñòèðóþùàÿ ñèñòåìà, êîòîðàÿ îñòàâëÿåò íà êîìïüþòåðå âõîäíîé ôàéë, íà êîòîðîì ïðîãðàììà íå ðàáîòàåò, î÷åíü ýòî ñòèìóëèðóåò - àíàëèçèðîâàòü, êàê ðàáîòàåò ïðîãðàììà è ñðàâíèâàòü ñ òåì, êàê îíà äîëæíà ðàáîòàòü. Óìåíèå ñàìîñòîÿòåëüíî èñêàòü íåïðàâèëüíûé òåñò - ýòî, íà ìîé âçãëÿä, ñëåäóþùèé ýòàï îáó÷åíèÿ.
Ïî íàáîðó òåì: ñíà÷àëà èäóò çàäà÷è íà öèêëû, çàòåì - ìàññèâû, ñîðòèðîâêà, äâóõìåðíûå ìàññèâû. Äàëüøå ìû ïîäáèðàåìñÿ ê òåìå ãðàôû, îäíàêî óñïåâàåì ëèøü çàòðîíóòü íà÷àëî ýòîé òåìû. Ýòî ñîçäàåò íåêîòîðûé çàäåë íà áóäóùåå. Çàêàí÷èâàåòñÿ êóðñ òåìîé ïðîöåäóðû è íàïèñàíèåì áîëüøîé èãðîâîé ïðîãðàììû. Ïðè ýòîì ïðè ïðîõîæäåíèè âñåõ âûøåïåð÷èñëåííûõ òåì äåòÿì ïîêàçûâàþòñÿ (ïîäêèäûâàþòñÿ) ðàçíûå èäåéêè. Ïîêà ýòî íå åñòü öåëü èçó÷åíèÿ, íî âàæíî, ÷òîáû êîãäà ìû äîéäåì äî ñîîòâåòñòâóþùèõ òåì, äëÿ íèõ ýòè èäåè áûëè íå ñîâñåì íîâûìè, à ñìóòíî çíàêîìûìè. À êàêèå-òî èç èäåé òàê è îñòàíóòñÿ ëèøü èäåÿìè. Êðîìå òîãî, ïåðèîäè÷åñêîå ïîêàçûâàíèå êðàñèâûõ èäåé ñòèìóëèðóåò øêîëüíèêîâ ê ïîèñêó íåñòàíäàðòíûõ ïîäõîäîâ, îáõîäíûõ ïóòåé ñàìîñòîÿòåëüíî.
Âî âñåõ çàäà÷àõ âõîäíûå äàííûå ââîäÿòñÿ èç ôàéëà INPUT.TXT, âûõîäíûå äàííûå âûâîäÿòñÿ â ôàéë OUTPUT.TXT.
Êîììåíòàðèè. Öåëüþ ïåðâûõ çàíÿòèé ÿâëÿåòñÿ çíàêîìñòâî ñ òåìîé "ôàéëû" è ïðèâûêàíèå ê ðàáîòå ñ íèìè, à òàêæå ïðèâûêàíèå ê ðàáîòå ñ òåñòèðóþùåé ñèñòåìîé.
Çàäà÷à 101 (Ñêà÷àòü àðõèâ)
Ââîäèòñÿ äâà ÷èñëà.  âûõîäíîé ôàéë çàïèñàòü èõ ñóììó. Ïðèìåð âõîäíîãî ôàéëà 2 3 Ïðèìåð âûõîäíîãî ôàéëà 5
Çàäà÷à 102 (Ñêà÷àòü àðõèâ)
Äàíû êîîðäèíàòû äâóõ ïîëåé øàõìàòíîé äîñêè (êîîðäèíàòû êëåòêè - ýòî 2 ÷èñëà îò 1 äî 8: íîìåð ñòîëáöà è íîìåð ñòðîêè) Îäíî ëè öâåòà ýòè êëåòêè íà øàõìàòíîé äîñêå? Âûâåñòè â âûõîäíîé ôàéë ñîîáùåíèå YES, åñëè îíè îäíîãî öâåòà, è NO èíà÷å Ïðèìåð âõîäíîãî ôàéëà: 1 1 2 2 Ïðèìåð âûõîäíîãî ôàéëà YES Ïðèìåð âõîäíîãî ôàéëà: 1 1 1 4 Ïðèìåð âûõîäíîãî ôàéëà NO
Çàäà÷à 103 (Ñêà÷àòü àðõèâ)
Äàíà ïîñëåäîâàòåëüíîñòü ÷èñåë. Íàéòè â íåé íàèìåíüøåå ÷èñëî. Âõîäíûå äàííûå. Çàäàíî ñíà÷àëà ÷èñëî N (êîëè÷åñòâî ÷èñåë â ïîñëåäîâàòåëüíîñòè), à çàòåì N ÷èñåë. Âûõîäíûå äàííûå. Âûâåäèòå íàèìåíüøåå ÷èñëî. Ïðèìåð âõîäíîãî ôàéëà 7 4 2 5 -1 4 6 2 Ïðèìåð âûõîäíîãî ôàéëà -1
Êîììåíòàðèè. Çàìåòüòå, ÷òî ýòó (è íåêîòîðûå ñëåäóþùèå çàäà÷è ïðî ïîñëåäîâàòåëüíîñòè) ïðåäïîëàãàåòñÿ ðåøàòü áåç èñïîëüçîâàíèÿ ìàññèâà (ñ÷èòàåòñÿ, ÷òî øêîëüíèêè ê ýòîìó ìîìåíòó èõ åùå íå çíàþò). Ïðè ýòîì åñëè íàõîäÿòñÿ øêîëüíèêè, çíàêîìûå ñ ìàññèâàìè, êîòîðûå ïðè ðåøåíèè çàäà÷è èõ èñïîëüçóþò, íè÷åãî ïëîõîãî â ýòîì íåò.
Êîììåíòàðèè. Çàäà÷è 104-106 - çàäà÷è íà èñïîëüçîâàíèå öèêëà WHILE.
Çàäà÷à 104 (Ñêà÷àòü àðõèâ)
ßâëÿåòñÿ ëè ÷èñëî ñòåïåíüþ äâîéêè? Ââîäèòñÿ ÷èñëî. Íàïå÷àòàòü YES, åñëè îíî ÿâëÿåòñÿ ñòåïåíüþ äâîéêè, NO - èíà÷å Ïðèìåð âõîäíîãî ôàéëà 8 Ïðèìåð âûõîäíîãî ôàéëà YES Ïðèìåð âõîäíîãî ôàéëà 22 Ïðèìåð âûõîäíîãî ôàéëà NO
Çàäà÷à 105 (Ñêà÷àòü àðõèâ)
Ïîñ÷èòàòü ñóììó öèôð ÷èñëà Ââîäèòñÿ ÷èñëî. Âûâåñòè ñóììó åãî öèôð Ïðèìåð âõîäíîãî ôàéëà 157 Ïðèìåð âûõîäíîãî ôàéëà 13
Çàäà÷à 106 (Ñêà÷àòü àðõèâ)
Ââîäèòñÿ ïîñëåäîâàòåëüíîñòü ÷èñåë äî òåõ, ïîêà íå áóäåò ââåäåíî äâà ðàâíûõ ÷èñëà ïîäðÿä. Ïîñ÷èòàòü êîëè÷åñòâî ÷èñåë â ïîñëåäîâàòåëüíîñòè. Âûõîäíûå äàííûå Âûâåäèòå êîëè÷åñòâî ÷èñåë (âêëþ÷àÿ äâà ïîñëåäíèõ) Ïðèìåð âõîäà 3 5 24 4 3 5 3 5 3 5 5 Ïðèìåð âûâîäà 11
Êîììåíòàðèè. Çàäà÷è 107-109 ïðåäïîëàãàþò èñïîëüçîâàíèå âëîæåííûõ öèêëîâ.
Çàäà÷à 107 (Ñêà÷àòü àðõèâ)
Ââîäÿòñÿ äâà ÷èñëà N è K. Âûâåäèòå êîëè÷åñòâî ÷èñåë èç äèàïàçîíà îò 1 äî N âêëþ÷èòåëüíî òàêèõ, ÷òî èõ ñóììà öèôð äåëèòñÿ íà K. Ïðèìåð ââîäà 100 3 Ïðèìåð âûâîäà 33 Ïðèìåð ââîäà 22 4 Ïðèìåð âûâîäà 5
Çàäà÷à 108 (Ñêà÷àòü àðõèâ)
Íàïå÷àòàéòå â ôàéë â âîçðàñòàþùåì ïîðÿäêå âñå 3-õ çíà÷íûå ÷èñëà, ó êîòîðûõ âñå öèôðû ðàçëè÷íû
Çàäà÷à 109 (Ñêà÷àòü àðõèâ)
Äàíî ÷èñëî N. Íàéòè ÷èñëî èç äèàïàçîíà îò 1 äî N ñ ìàêñèìàëüíîé ñóììîé äåëèòåëåé (âêëþ÷àÿ íåïðîñòûå äåëèòåëè, 1 è ñàìî ÷èñëî). Åñëè òàêèõ ÷èñåë íåñêîëüêî, âûâåäèòå ëþáîå èç íèõ. Ïðèìåð ââîäà 5 Ïðèìåð âûâîäà 4
Çàäà÷à 110 (Ñêà÷àòü àðõèâ)
Äàíà ïîñëåäîâàòåëüíîñòü ÷èñåë. Âûÿñíèòü, ñêîëüêî ðàç â íåé âñòðå÷àåòñÿ ìàêñèìàëüíîå ÷èñëî Âõîäíûå äàííûå. Ââîäèòñÿ ñíà÷àëà ÷èñëî N - êîëè÷åñòâî ÷ëåíîâ ïîñëåäîâàòåëüíîñòè, à çàòåì N ÷èñåë - ÷ëåíû ïîñëåäîâàòåëüíîñòè Âûõîäíûå äàííûå Âûâåäèòå îäíî ÷èñëî - ñêîëüêî ðàç â ïîñëåäîâàòåëüíîñòè âñòðå÷àåòñÿ ìàêñèìàëüíîå ÷èñëî. Ïðèìåð âõîäíîãî ôàéëà 7 1 4 2 5 2 5 3 Ïðèìåð âûõîäíîãî ôàéëà 2
Êîììåíòàðèè. Íå î÷åíü ïðîñòàÿ çàäà÷à, åñëè ó÷åñòü, ÷òî òåìó ìàññèâû ìû ê ýòîìó ìîìåíòó åùå íå ïðîõîäèëè. Òåì íå ìåíåå, ìàññèâ, â îáùåì-òî, è íå íóæåí äëÿ åå ðåøåíèÿ.
Êîììåíòàðèè. Çàäà÷à 111 ãîòîâèò øêîëüíèêîâ ê ïîÿâëåíèþ ìàññèâîâ. Çäåñü óæå âñòðå÷àþòñÿ òàêèå ïîíÿòèÿ, êàê ñàì ýëåìåíò è åãî íîìåð. Çäåñü æå (âïðî÷åì, ýòî áûëî è â íåêîòîðûõ áîëåå ðàííèõ çàäà÷àõ) øêîëüíèêàì ïðåäëàãàåòñÿ ñïîñîá ââîäà, êîãäà ââîäèòñÿ ñíà÷àëà êîëè÷åñòâî ÷èñåë, à ïîòîì ñàìè ýëåìåíòû.
Çàäà÷à 111 (Ñêà÷àòü àðõèâ)
Ââîäèòñÿ ïîñëåäîâàòåëüíîñòü ÷èñåë. Ïîñ÷èòàòü â íåé êîëè÷åñòâî ÷åòíûõ ÷èñåë, ñòîÿùèõ íà ÷åòíûõ ìåñòàõ. Âõîäíûå äàííûå Ââîäèòñÿ ñíà÷àëà ÷èñëî N, à çàòåì N ÷èñåë - ÷ëåíû ïîñëåäîâàòåëüíîñòè. Âûõîäíûå äàííûå. Âûâåäèòå êîëè÷åñòâî ÷åòíûõ ÷èñåë, ñòîÿùèõ íà ÷åòíûõ ìåñòàõ â ïîñëåäîâàòåëüíîñòè. Ïðèìåð âõîäíîãî ôàéëà 5 1 2 4 5 6 Ïðèìåð âûõîäíîãî ôàéëà: 1 Ïîÿñíåíèå: åäèíñòâåííîå ÷åòíîå ÷èñëî, ñòîÿùåå íà ÷åòíîì ìåñòå â ïîñëåäîâàòåëüíîñòè - ýòî ÷èñëî 2. ×èñëà 4 è 6 íå ïîäõîäÿò, òàê êàê ñòîÿò, ñîîòâåòñòâåííî, íà 3 è 5-ì ìåñòàõ.
Çàäà÷à 112 (Ñêà÷àòü àðõèâ)
Çàäà÷à "Êîðîòêèé ÍÎÄ" Äàíû äâà ÷èñëà. Íàéòè èõ íàèáîëüøèé îáùèé äåëèòåëü. Âõîäíûå äàííûå Ââîäÿòñÿ äâà íàòóðàëüíûõ ÷èñëà, íå ïðåâûøàþùèõ 30000. Âûõîäíûå äàííûå Âûâåäèòå ÍÎÄ ââåäåííûõ ÷èñåë Ïðèìåð âõîäíîãî ôàéëà 9 12 Ïðèìåð âûõîäíîãî ôàéëà 6
Çàäà÷à 113 (Ñêà÷àòü àðõèâ)
Çàäà÷à "Äëèííûé ÍÎÄ" Äàíû äâà ÷èñëà. Íàéòè èõ íàèáîëüøèé îáùèé äåëèòåëü. Âõîäíûå äàííûå Ââîäÿòñÿ äâà íàòóðàëüíûõ ÷èñëà, íå ïðåâûøàþùèõ 10^9 (çàïèñü 10^9 îáîçíà÷àåò "10 â 9-é ñòåïåíè", òî åñòü 1000000000). Âûõîäíûå äàííûå Âûâåäèòå ÍÎÄ ââåäåííûõ ÷èñåë Ïðèìåð âõîäíîãî ôàéëà 9 12 Ïðèìåð âûõîäíîãî ôàéëà 6
Êîììåíòàðèè. Çàäà÷à 113 îòëè÷àåòñÿ îò 112 òåì, ÷òî 112 ìîæíî ðåøèòü ïîëíûì ïåðåáîðîì äåëèòåëåé, à â 113 òðåáóåòñÿ ðåàëèçàöèÿ àëãîðèòìà Åâêëèäà.
Êîììåíòàðèè. Ïåðåä ýòîé çàäà÷åé øêîëüíèêàì ðàññêàçûâàåòñÿ, ÷òî òàêîå ìàññèâû, êàê ñ íèìè ðàáîòàòü, êàê ñ÷èòûâàòü/çàïèñûâàòü ýëåìåíòû ìàññèâà. Äàëüøå èäóò çàäà÷è íà ìàññèâû.
Çàäà÷à 115 (Ñêà÷àòü àðõèâ)
Ââîäèòñÿ ñíà÷àëà ÷èñëî N, à çàòåì N ÷èñåë. Âûâåäèòå ýòè N ÷èñåë â îáðàòíîì ïîðÿäêå. Âõîäíûå äàííûå Ââîäèòñÿ ÷èñëî N (0<N<100), à çàòåì N ÷èñåë èç äèàïàçîíà Integer. Âûõîäíûå äàííûå Âûâåäèòå N ÷èñåë â îáðàòíîì ïîðÿäêå Ïðèìåð âõîäíîãî ôàéëà 7 2 4 1 3 5 3 1 Ïðèìåð âûõîäíîãî ôàéëà 1 3 5 3 1 4 2
Çàäà÷à 116 (Ñêà÷àòü àðõèâ)
Ââîäèòñÿ ñíà÷àëà ÷èñëî N, à çàòåì N ÷èñåë. Âûâåäèòå ýòè N ÷èñåë â ñëåäóþùåì ïîðÿäêå: ñíà÷àëà âûâîäÿòñÿ âñå íå÷åòíûå ÷èñëà â òîì ïîðÿäêå, â êàêîì îíè âñòðå÷àëèñü âî âõîäíîì ôàéëå, à çàòåì - âñå ÷åòíûå. Âõîäíûå äàííûå Ââîäèòñÿ ÷èñëî N (0<N<100), à çàòåì N ÷èñåë èç äèàïàçîíà Integer. Ïðèìåð âõîäíîãî ôàéëà 7 2 4 1 3 5 3 1 Ïðèìåð âûõîäíîãî ôàéëà 1 3 5 3 1 2 4
Çàäà÷à 117 (Ñêà÷àòü àðõèâ)
Ââîäèòñÿ ñíà÷àëà ÷èñëî N, à çàòåì N ÷èñåë. Âûâåäèòå ýòè N ÷èñåë â ñëåäóþùåì ïîðÿäêå: ñíà÷àëà âûâîäÿòñÿ ÷èñëà, ñòîÿùèå íà íå÷åòíûõ ìåñòàõ, à çàòåì - ñòîÿùèå íà ÷åòíûõ ìåñòàõ. Âõîäíûå äàííûå Ââîäèòñÿ ÷èñëî N (0<N<100), à çàòåì N ÷èñåë èç äèàïàçîíà Integer. Ïðèìåð âõîäíîãî ôàéëà 7 2 4 1 3 5 3 1 Ïðèìåð âûõîäíîãî ôàéëà 2 1 5 1 4 3 3
Çàäà÷à 118 (Ñêà÷àòü àðõèâ)
(Ìîæåò áûòü, äëÿ âàñ áóäåò ïðîùå ñíà÷àëà ðåøèòü çàäà÷ó 119, à ïîòîì óæå - ýòó) Ââîäèòñÿ ÷èñëî N, à çàòåì - N ÷èñåë. Îïðåäåëèòü, ñêîëüêî ñðåäè íèõ ïàð îäèíàêîâûõ ÷èñåë. 2˜N˜100 Ïðèìåð âõîäíîãî ôàéëà: 5 1 3 2 2 3 Ïðèìåð âûõîäíîãî ôàéëà: 2 Ïðèìåð âõîäíîãî ôàéëà: 4 1 1 1 1 Ïðèìåð âûõîäíîãî ôàéëà: 6 Ïîÿñíåíèå: Âî 2-ì ïðèìåðå ïàðó îäèíàêîâûõ ÷èñåë îáðàçîâûâàþò ëþáûå äâà ÷èñëà ïîñëåäîâàòåëüíîñòè, ïîýòîìó îòâåòîì áóäåò ÷èñëî ïàð, êîòîðîå âîîáùå ìîæåò áûòü (ýòî ïàðû ÷èñåë, ñòîÿùèõ íà ìåñòàõ: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4))
Çàäà÷à 119 (Ñêà÷àòü àðõèâ)
Ââîäèòñÿ ÷èñëî N, à çàòåì - N ÷èñåë. Îïðåäåëèòü, ñêîëüêî ñðåäè íèõ ïàð îäèíàêîâûõ ÷èñåë, ñòîÿùèõ ðÿäîì. 2˜N˜100 Ïðèìåð âõîäíîãî ôàéëà: 5 1 3 2 2 3 Ïðèìåð âûõîäíîãî ôàéëà: 1 Ïðèìåð âõîäíîãî ôàéëà: 4 1 1 1 1 Ïðèìåð âûõîäíîãî ôàéëà: 3
Çàäà÷à 120 (Ñêà÷àòü àðõèâ)
Ââîäèòñÿ ÷èñëî N, à çàòåì N ÷èñåë - ýëåìåíòîâ ìàññèâà (1˜N˜100), ýëåìåíòû ìàññèâà - ÷èñëà èç äèàïàçîíà Integer. Âûâåäèòå äâà ÷èñëà - íîìåðà ìåñò â ìàññèâå, íà êîòîðûõ ñòîÿò îäèíàêîâûå ýëåìåíòû, èëè äâà ÷èñëà 0 (òî åñòü 0 0), åñëè âñå ýëåìåíòû ðàçëè÷íû. Åñëè åñòü íåñêîëüêî ïàð ÷èñåë, ÿâëÿþùèõñÿ îòâåòîì, âûâåäèòå ëþáóþ èç íèõ. Ïðèìåð âõîäíîãî ôàéëà 5 1 2 1 3 4 Ïðèìåð âûõîäíîãî ôàéëà 1 3 Ïðèìåð âõîäíîãî ôàéëà 4 1 2 3 4 Ïðèìåð âûõîäíîãî ôàéëà 0 0
Çàäà÷à 121 (Ñêà÷àòü àðõèâ)
Äàíû N îòðåçêîâ ïðÿìîé. Íàéòè äëèíó îáùåé ÷àñòè âñåõ ýòèõ îòðåçêîâ. Âõîäíûå äàííûå. Ââîäèòñÿ ñíà÷àëà ÷èñëî N (1˜N˜100). Äàëåå âîîäèòñÿ N ïàð ÷èñåë, çàäàþùèõ êîîðäèíàòû ëåâîãî è ïðàâîãî êîíöîâ êàæäîãî îòðåçêà. Âñå êîîðäèíàòû - ÷èñëà èç äàïàçîíà îò 0 äî 30000. Ëåâûé êîíåö îòðåçêà âñåãäà èìååò êîîðäèíàòó ñòðîãî ìåíüøóþ, ÷åì ïðàâûé. Âûõîäíûå äàííûå. Âûâåäèòå äëèíó îáùåé ÷àñòè ýòèõ îòðåçîâ. Åñëè ó âñåõ ýòèõ îòðåçêîâ îáùåé ÷àñòè íåò, âûâåäèòå 0. Ïðèìåð âõîäíîãî ôàéëà 3 1 10 3 15 2 6 Ïðèìåð âûõîäíîãî ôàéëà 3 Ïîÿñíåíèå: îáùàÿ ÷àñòü ýòèõ îòðåçêîâ - îòðåçîê îò 3 äî 6. Ïðèìåð âõîäíîãî ôàéëà 3 1 10 2 20 11 20 Ïðèìåð âûõîäíîãî ôàéëà: 0 Ïîÿñíåíèå: ó ýòèõ îòðåçêîâ íåò îáùåé ÷àñòè
Çàäà÷à 122 (Ñêà÷àòü àðõèâ)
Ââîäÿòñÿ ÷èñëà îò 1 äî 9 äî òåõ ïîð, ïîêà íå áóäåò ââåäåí 0. Âñåãî áóäåò ââåäåíî íå áîëüøå 100 ÷èñåë. Ïîñ÷èòàòü êîëè÷åñòâî åäèíèö â ýòîé ïîñëåäîâàòåëüíîñòè, êîëè÷åñòâî äâîåê, êîëè÷åñòâî òðîåê è òàê äàëåå (â âûõîäíîì ôàéëå âñåãäà äîëæíî áûòü 9 ÷èñåë). Ïðèìåð âõîäíîãî ôàéëà 1 1 4 1 5 8 6 3 5 1 0 Ïðèìåð âûõîäíîãî ôàéëà: 4 0 1 1 2 1 0 1 0
Çàäà÷à 123 (Ñêà÷àòü àðõèâ)
(Òà æå çàäà÷à, ÷òî è 122, òîëüêî ìîæåò áûòü ââåäåíî äî 100000 ÷èñåë) Ââîäÿòñÿ ÷èñëà îò 1 äî 9 äî òåõ ïîð, ïîêà íå áóäåò ââåäåí 0. Âñåãî áóäåò ââåäåíî íå áîëåå 100000 ÷èñåë Ïîñ÷èòàòü êîëè÷åñòâî åäèíèö â ýòîé ïîñëåäîâàòåëüíîñòè, êîëè÷åñòâî äâîåê, êîëè÷åñòâî òðîåê è òàê äàëåå (â âûõîäíîì ôàéëå âñåãäà äîëæíî áûòü 9 ÷èñåë). Ïðèìåð âõîäíîãî ôàéëà 1 1 4 1 5 8 6 3 5 1 0 Ïðèìåð âûõîäíîãî ôàéëà: 4 0 1 1 2 1 0 1 0
Êîììåíòàðèè. Ýòà çàäà÷à î÷åíü íåïðîñòàÿ äëÿ øêîëüíèêîâ (â èäåéíîì ïëàíå). Åñëè ðàíüøå ìàññèâ èñïîëüçîâàëñÿ äëÿ õðàíåíèÿ ïîñëåäîâàòåëüíîñòè, òî çäåñü íóæíî èñïîëüçîâàòü ìàññèâ äëÿ ïîäñ÷åòà îòâåòà. Ìíîãèå øêîëüíèêè íå çàìå÷àþò ýòó èäåþ, è, ñîõðàíèâ ââîäèìûå ÷èñëà â ïàìÿòè, çàòåì 9 ðàç ïðîáåãàþò ïî ìàññèâó, ñ÷èòàÿ ñíà÷àëà 1, ïîòîì 2 è ò.ä.  ýòîì ñëó÷àå 122 çàäà÷à ïðîõîäèò, à âîò ñî 123 âîçíèêàþò ïðîáëåìû. Çäåñü îáÿçàòåëüíî íóæíî îñòàíîâèòüñÿ è îáñóäèòü ýòó èäåþ - â íåêîòîðîì ñìûñëå, ýòî íåêîòîðûé ïîäõîä ê èäåå öèôðîâîé ñîðòèðîâêè.
Çàäà÷à 124 (Ñêà÷àòü àðõèâ)
 íåêîòîðîì ãîñóäàðñòâå äåéñòâóåò N ôèðì, êîíêóðèðóþùèõ ìåæäó ñîáîé. Ó êàæäîé ôèðìû åñòü íåêîòîðàÿ ïðèáûëü â ãîä, ðàâíàÿ V[i] àìåðèêàíñêèõ ðóáëåé. Ó öàðÿ åñòü ëþáèìûå ôèðìû, à åñòü íåëþáèìûå. Ñîîòâåòñòâåííî, íàëîã äëÿ âñåõ ôèðì ðàçíûé è íàçíà÷àåòñÿ öàðåì â èíäèâèäóàëüíîì ïîðÿäêå. Íàëîã íà i-óþ ôèðìó ðàâåí p[i] ïðîöåíòîâ. Ñîáèðàòåëè ñòàòèñòèêè ðåøèëè ïîñ÷èòàòü, ñ êàêîé ôèðìû â ãîñóäàðñòâåííóþ êàçíó èäåò íàèáîëüøèé äîõîä (â êàçíó èäóò âñå íàëîãè). Ê ñîæàëåíèþ, îíè íå ó÷èëè â äåòñòâå íè ìàòåìàòèêó, íè èíôîðìàòèêó (òàê ÷òî ó÷èòåñü, äåòè!), è èõ çàäà÷à ðåçêî îñëîæíÿåòñÿ. Ïîìîãèòå èì â ýòîé íåëåãêîé çàäà÷å. Âõîäíîé ôàéë input.txt ----------------------- ñíà÷àëà çàïèñàíî ÷èñëî N - ÷èñëî ôèðì (0<N˜100). Äàëåå èäåò N öåëûõ íåîòðèöàòåëüíûõ ÷èñåë, íå ïðåâûøàþùèõ 154 - äîõîäû ôèðì, à çàòåì åùå N öåëûõ ÷èñåë îò 0 äî 100 - íàëîãè ôèðì â ïðîöåíòàõ. Âûõîäíîé ôàéë output.txt ------------------------  âûõîäíîé ôàéë âûâåäèòå îäíî ÷èñëî - íîìåð ôèðìû, îò êîòîðîé ãîñóäàðñòâî ïîëó÷àåò íàèáîëüøèé íàëîã. Åñëè òàêèõ ôèðì íåñêîëüêî, âûâåäèòå ëþáóþ èç íèõ. Ïðèìåð âõîäíîãî ôàéëà: 3 100 1 50 0 100 3 Ïðèìåð âûõîäíîãî ôàéëà: 3
Êîììåíòàðèè. Çäåñü, îáû÷íî, øêîëüíèêè âñïîìèíàþò âåùåñòâåííûå ÷èñëà, î êîòîðûõ øëà ðå÷ü íà 1-ì çàíÿòèè, è êîòîðûå áîëüøå íèãäå íå âñòðå÷àëèñü. Îäíàêî êàê ðàç íà ýòîé çàäà÷å íåïëîõî ïîãîâîðèòü ñ íèìè î òîì, ÷òî îïåðàöèè ñ âåùåñòâåííûìè ÷èñëàìè âûïîëíÿþòñÿ çíà÷èòåëüíî ìåäëåíåå, ÷åì ñ öåëûìè è î òîì, ìîæíî ëè â ýòîé çàäà÷å îáîéòèñü òîëüêî öåëûìè ÷èñëàìè (ìîæíî, åñëè íå äåëèòü íà 100).
Çàäà÷à 125 (Ñêà÷àòü àðõèâ)
Âî âõîäíîì ôàéëå çàïèñàíà ïîñëåäîâàòåëüíîñòü íàòóðàëüíûõ ÷èñåë, íå ïðåâûøàþùèõ 1000. Ïîñëåäîâàòåëüíîñòü çàêàí÷èâàåòñÿ ÷èñëîì 0. Êîëè÷åñòâî ÷èñåë â ïîñëåäîâàòåëüíîñòè íå ïðåâûøàåò 100. Âûâåäèòå â âûõîäíîé ôàéë êîëè÷åñòâî ÷èñåë â ïîñëåäîâàòåëüíîñòè (íå ñ÷èòàÿ 0), à ïîòîì ñàìè ÷èñëà. Ïðèìåð âõîäíîãî ôàéëà 1 3 5 0 Ïðèìåð âûõîäíîãî ôàéëà 3 1 3 5
Çàäà÷à 126 (Ñêà÷àòü àðõèâ)
Âî âõîäíîì ôàéëå çàïèñàíà ïîñëåäîâàòåëüíîñòü ÷èñåë â ñòðàííîì ôîðìàòå: ó êàæäîãî ÷èñëà ñíà÷àëà çàïèñàíî êîëè÷åñòâî öèôð â ýòîì ÷èñëå, à ïîòîì ÷åðåç ïðîáåë - ñàìè öèôðû. Ïîñëåäîâàòåëüíîñòü çàêàí÷èâàåòñÿ ÷èñëîì 0.  âûõîäíîé ôàéë íóæíî âûâåñòè ñíà÷àëà êîëè÷åñòâî ÷èñåë â ïîñëåäîâàòåëüíîñòè, à ïîòîì - ñàìè ÷èñëà. Êîëè÷åñòâî ÷èñåë â ïîñëåäîâàòåëüíîñòè íå ïðåâûøàåò 1000.  ÷èñëàõ - íå áîëåå 4-õ çíàêîâ. Ïðèìåðû: Ïðèìåð 1 input.txt output.txt 2 2 7 3 3 5 1 0 2 27 351 Ïðèìåð 2 input.txt output.txt 1 1 0 1 1 Ïðèìåð 3 input.txt output.txt 4 1 2 3 4 2 4 3 0 2 1234 43
Êîììåíòàðèè. Çàäà÷à äîñòàòî÷íî ñëîæíàÿ è òðåáóåò àêêóðàòíîãî ïðîãðàììèðîâàíèÿ.
Çàäà÷à 127 (Ñêà÷àòü àðõèâ)
Äàíî N öåëûõ ÷èñåë. Òðåáóåòñÿ âûáðàòü èç íèõ òðè òàêèõ ÷èñëà, ïðîèçâåäåíèå êîòîðûõ ìàêñèìàëüíî. Ôîðìàò âõîäíûõ äàííûõ Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî ÷èñåë â ïîñëåäîâàòåëüíîñòè (3˜N˜100). Äàëåå çàïèñàíà ñàìà ïîñëåäîâàòåëüíîñòü: N öåëûõ ÷èñåë, ïî ìîäóëþ íå ïðåâûøàþùèõ 1000. Ôîðìàò âûõîäíûõ äàííûõ  âûõîäíîé ôàéë âûâåäèòå òðè èñêîìûõ ÷èñëà â ëþáîì ïîðÿäêå. Åñëè ñóùåñòâóåò íåñêîëüêî ðàçëè÷íûõ òðîåê ÷èñåë, äàþùèõ ìàêñèìàëüíîå ïðîèçâåäåíèå, òî âûâåäèòå ëþáóþ èç íèõ. Ïðèìåð âõîäíîãî ôàéëà 9 3 5 1 7 9 0 9 -3 10 Ïðèìåð âûõîäíîãî ôàéëà 9 10 9 Ïðèìåð âõîäíîãî ôàéëà 3 -5 -300 -12 Ïðèìåð âûõîäíîãî ôàéëà -5 -300 -12
Êîììåíòàðèè. Çàäà÷à ïîõîæà íà çàäà÷ó ñ Ìîñêîâñêîé îëèìïèàäû 2004 ãîäà (ñ óìåíüøåííûìè îãðàíè÷åíèÿìè). Âîçìîæíî êàê ðåøåíèå, ïåðåáèðàþùåå âñå òðîéêè ÷èñåë (äëÿ øêîëüíèêîâ íà ýòîì óðîâíå ýòî òîæå îòíþäü íå ïðîñòàÿ çàäà÷à), òàê è ðåøåíèå, ðàçáèðàþùåå ñëó÷àè (ñì. êîììåíòàðèè ê ýòîé çàäà÷å â áðîøþðå ñ ðàçáîðîì çàäà÷ Ìîñêîâñêîé îëèìïèàäû).
Êîììåíòàðèè. Ñëåäóþùèå äâå çàäà÷è - âñòàâêà ýëåìåíòà â ìàññèâ è óäàëåíèå ýëåìåíòà ñíà÷àëà ðàçáèðàþòñÿ íà ïðèìåðå ñàìèõ øêîëüíèêîâ è ñòóëüåâ, íà êîòîðûõ îíè ñèäÿò. Èäåÿ î òîì, ÷òî äëÿ òîãî, ÷òîáû ýëåìåíò â ìàññèâ âñòàâèòü, íóæíî ñíà÷àëà ñäâèíóòü âñåõ, êòî ñèäåë íà ýòîì è ïîñëåäóþùèõ ìåñòàõ, äîñòàòî÷íî î÷åâèäíà. Ãîðàçäî ìåíåå î÷åâèäíî, ïî÷åìó â ñëó÷àå äîáàâëåíèÿ ñäâèã íóæíî íà÷èíàòü ñ êîíöà ìàññèâà, à â ñëó÷àå óäàëåíèÿ - ñ íà÷àëà.
Çàäà÷à 128 (Ñêà÷àòü àðõèâ)
Äàí ìàññèâ. Òðåáóåòñÿ óäàëèòü èç íåãî ýëåìåíò, ñòîÿùèé íà ìåñòå íîìåð B, ñäâèíóâ âñå ïîñëåäóþùèå ýëåìåíòû âëåâî. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî ýëåìåíòîâ ìàññèâà (2˜N˜100), çàòåì N ÷èñåë èç äèàïàçîíà Integer - ýëåìåíòû ìàññèâà, à çàòåì ÷èñëî B (1˜B˜N). Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå N-1 ÷èñëî - ýëåìåíòû ìàññèâà ñ óäàëåííûì B-ì ýëåìåíòîì. Ïðèìå÷àíèå Âû äîëæíû óäàëèòü ýëåìåíò íåïîñðåäñòâåííî èç ìàññèâà, à íå ñäåëàòü âèä ïðè âûâîäå äàííûõ, ÷òî ó âàñ òàêîãî ýëåìåíòà íåò. Òàêæå âû íå äîëæíû äëÿ ýòîãî çàâîäèòü â ïðîãðàììå äîïîëíèòåëüíûé ìàññèâ. Òî åñòü ââîä äàííûõ îñóùåñòâëÿåòñÿ ñëåäóþùèì ôðàãìåíòîì: read(fi,n); for i:=1 to n do read(fi,a[i]); read(fi,b); À âûâîä - ñëåäóþùèì: for i:=1 to n-1 do write(fo,a[i],' '); Íåîáõîäèìûå ôðàãìåíòû âû ìîæåòå íàéòè â ôàéëå P<íîìåð çàäà÷è>.PAS (P128.PAS) Ïðèìåð âõîäíîãî ôàéëà 5 1 3 5 6 7 2 Ïðèìåð âûõîäíîãî ôàéëà 1 5 6 7
Òåêñò ïðîãðàììû P128.PAS
const nmax=100;
var a:array[1..nmax] of integer;
n:integer;
i:integer;
b:integer;
fi,fo:text;
begin
assign(fi,'input.txt');
reset(fi);
assign(fo,'output.txt');
rewrite(fo);
read(fi,n);
for i:=1 to n do read(fi,a[i]);
read(fi,b);
{Âû äîëæíû ïèñàòü çäåñü}
for i:=1 to n-1 do write(fo,a[i],' ');
close(fi);
close(fo);
end.
Çàäà÷à 129 (Ñêà÷àòü àðõèâ)
Äàí ìàññèâ. Òðåáóåòñÿ âñòàâèòü â íåãî íà ìåñòî íîìåð B ýëåìåíò, ðàâíûé C, ñäâèíóâ âñå ïîñëåäóþùèå ýëåìåíòû (âêëþ÷àÿ ýëåìåíò, ñòîÿùèé íà B-îì ìåñòå) âïðàâî. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî ýëåìåíòîâ ìàññèâà (2˜N˜100), çàòåì N ÷èñåë èç äèàïàçîíà Integer - ýëåìåíòû ìàññèâà, çàòåì ÷èñëî B (1˜B˜N) è ÷èñëî C (èç äèàïàçîíà Integer). Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå N+1 ÷èñëî - ýëåìåíòû ìàññèâà ñ âñòàâëåííûì ýëåìåíòîì. Ïðèìå÷àíèå Âû äîëæíû âñòàâèòü ýëåìåíò íåïîñðåäñòâåííî â ìàññèâ, à íå ñäåëàòü âèä ïðè âûâîäå äàííûõ, ÷òî ó âàñ ïîÿâèëñÿ òàêîé ýëåìåíò. Òàêæå âû íå äîëæíû äëÿ ýòîãî çàâîäèòü â ïðîãðàììå äîïîëíèòåëüíûé ìàññèâ. Òî åñòü ââîä äàííûõ îñóùåñòâëÿåòñÿ ñëåäóþùèì ôðàãìåíòîì: read(fi,n); for i:=1 to n do read(fi,a[i]); read(fi,b,c); À âûâîä - ñëåäóþùèì: for i:=1 to n+1 do write(fo,a[i],' '); Íåîáõîäèìûå ôðàãìåíòû âû ìîæåòå íàéòè â ôàéëå P<íîìåð çàäà÷è>.PAS (P129.PAS) Ïðèìåð âõîäíîãî ôàéëà 5 1 3 5 6 7 2 10 Ïðèìåð âûõîäíîãî ôàéëà 1 10 3 5 6 7
Òåêñò ïðîãðàììû P129.PAS
const nmax=100;
var a:array[1..nmax] of integer;
n:integer;
i:integer;
b,c:integer;
fi,fo:text;
begin
assign(fi,'input.txt');
reset(fi);
assign(fo,'output.txt');
rewrite(fo);
read(fi,n);
for i:=1 to n do read(fi,a[i]);
read(fi,b,c);
{Âû äîëæíû ïèñàòü çäåñü}
for i:=1 to n+1 do write(fo,a[i],' ');
close(fi);
close(fo);
end.
Çàäà÷à 130 (Ñêà÷àòü àðõèâ)
 íà÷àëüíûé ìîìåíò â i-îì ýëåìåíòå ìàññèâà çàïèñàíî ÷èñëî i (âñåãî N ýëåìåíòîâ). Êàæäóþ ñåêóíäó ÷èñëà ñäâèãàþòñÿ â ñëåäóþùóþ ÿ÷åéêó (èç i-îé â i+1-óþ), à èç N-îé - â ïåðâóþ. Íàïå÷àòàòü ñîñòîÿíèå ìàññèâà ÷åðåç T ñåêóíä. Âî âõîíîì ôàéëå çàïèñàíû äâà ÷èñëà - N (1˜N˜100) è T (0˜T˜30000).  âûõîäíîé ôàéë âûâåäèòå N ÷èñåë - ñîñòîÿíèå ìàññèâà ÷åðåç T ñåêóíä. Ïðèìåð âõîäíîãî ôàéëà 5 3 Ïðèìåð âûõîäíîãî ôàéëà 3 4 5 1 2
Êîììåíòàðèè. Çàäà÷à äîïóñêàåò íåñêîëüêî ðåøåíèé. Ìîæíî ïðîñòî ïðîñ÷èòàòü, êòî êîãäà ãäå áóäåò, ìîæíî ïðîñòî ïðîìîäåëèíðîâàòü ïðîöåññ (ýòî ðåøåíèå ÿâëÿåòñÿ áîëåå ïðåäïî÷òèòåëüíûì). Îáÿçàòåëüíî ñòîèò îáñóäèòü, ÷òî ïåðåä ìîäåëèðîâàíèåì ïðîöåññà, ñòîèò âçÿòü T mod N.
Çàäà÷à 131 (Ñêà÷àòü àðõèâ)
Çàäà÷à Èîñèôà Ôëàâèÿ Ñóùåñòâóåò ëåãåíäà, ÷òî Èîñèô Ôëàâèé - èçâåñòíûé èñòîðèê ïåðâîãî âåêà - âûæèë è ñòàë èçâåñòíûì áëàãîäàðÿ ìàòåìàòè÷åñêîé îäàðåííîñòè.  õîäå èóäåéñêîé âîéíû îí â ñîñòàâå îòðÿäà èç 41 èóäåéñêîãî âîèíà áûë çàãíàí ðèìëÿíàìè â ïåùåðó. Ïðåäïî÷èòàÿ ñàìîóáèéñòâî ïëåíó, âîèíû ðåøèëè âûñòðîèòüñÿ â êðóã è ïîñëåäîâàòåëüíî óáèâàòü êàæäîãî òðåòüåãî èç æèâûõ äî òåõ ïîð, ïîêà íå îñòàíåòñÿ íè îäíîãî ÷åëîâåêà. Îäíàêî Èîñèô íàðÿäó ñ îäíèì èç ñâîèõ åäèíîìûøëåííèêîâ ñ÷åë ïîäîáíûé êîíåö áåññìûñëåííûì - îí áûñòðî âû÷èñëèë ñïàñèòåëüíûå ìåñòà â ïîðî÷íîì êðóãå, íà êîòîðûå ïîñòàâèë ñåáÿ è ñâîåãî òîâàðèùà. È ëèøü ïîýòîìó ìû çíàåì åãî èñòîðèþ.  íàøåì âàðèàíòå ìû íà÷íåì ñ òîãî, ÷òî âûñòðîèì â êðóã N ÷åëîâåê, ïðîíóìåðîâàííûõ ÷èñëàìè îò 1 äî N, è áóäåì èñêëþ÷àòü êàæäîãî k-îãî äî òåõ ïîð, ïîêà íå óöåëååò òîëüêî îäèí ÷åëîâåê. (Íàïðèìåð, åñëè N=10, k=3, òî ñíà÷àëà óìðåò 3-é, ïîòîì 6-é, çàòåì 9-é, çàòåì 2-é, çàòåì 7-é, ïîòîì 1-é, ïîòîì 8-é, çà íèì - 5-é, è ïîòîì 10-é. Òàêèì îáðàçîì, óöåëååò 4-é.) Çàäà÷à: îïðåäåëèòü íîìåð óöåëåâøåãî. Âõîäíûå äàííûå: ÷èñëà N è k ââîäÿòñÿ èç ôàéëà INPUT.TXT. Îãðàíè÷åíèÿ: 1˜N˜500, 1˜k˜100. Âûõîäíûå äàííûå: Ïðîãðàììà äîëæíà âûäàâàòü íîìåð óöåëåâøåãî ÷åëîâåêà â ôàéë OUTPUT.TXT. Ïðèìåð âõîäíîãî ôàéëà: 10 3 Ïðèìåð âûõîäíîãî ôàéëà: 4
Êîììåíòàðèè. Çàäà÷à Èîñèôà Ôëàâèÿ î÷åíü áîãàòà íà èäåè. Ïðåäïîëàãàåòñÿ, ÷òî øêîëüíèêè áóäóò ðåøàòü åå, ìîäåëèðóÿ ïðîöåññ. Ïðè ýòîì åñòü äâà ïîäõîäà: çàâåñòè ìàññèâ, ãäå ïîìå÷àòü, æèâ ÷åëîâåê èëè íåò. Áåãàòü ïî êðóãó è ñ÷èòàòü æèâûõ. Âòîðîé ïîäõîä: çàâåñòè ìàññèâ ñ íîìåðàìè æèâûõ ëþäåé, è ïðè óáèâàíèè ÷åëîâåêà óäàëÿòü èç íåãî ÷åëîâåêà. Ïðè êàæäîì èç ïîäõîäîâ, çàäà÷à ÿâëÿåòñÿ äîâîëüíî ñëîæíîé è òðåáóåò àêêóðàòíîé ðåàëèçàöèè.
Çàäà÷à 132 (Ñêà÷àòü àðõèâ)
Çàäà÷à "Òðîëëåéáóñû" Òðîëëåéáóñû îäíîãî ìàðøðóòà ïðîõîäÿò ÷åðåç îñòàíîâêó êàæäûå k (1˜k˜500) ìèíóò. Èçâåñòíû âðåìåíà ïðèõîäà ïàññàæèðîâ íà ýòó îñòàíîâêó. Åñëè ïàññàæèð ïðèõîäèò íà îñòàíîâêó â ìîìåíò ïðèõîäà òðîëëåéáóñà, òî îí óñïåâàåò óåõàòü íà íåì. Íàïèøèòå ïðîãðàììó, êîòîðàÿ áû îïðåäåëÿëà, âî ñêîëüêî äîëæåí ïðîéòè ïåðâûé òðîëëåéáóñ (ýòî âðåìÿ îò 0 äî k-1), ÷òîáû: 1) Ñóììàðíîå âðåìÿ îæèäàíèÿ òðîëëåéáóñà äëÿ âñåõ ïàññàæèðîâ áûëî ìèíèìàëüíî. 2) Ìàêñèìàëüíîå èç âðåìåí îæèäàíèÿ òðîëëåéáóñà áûëî ìèíèìàëüíî. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå INPUT.TXT çàïèñàíî ñíà÷àëà ÷èñëî k, çàòåì - ÷èñëî N (0˜N˜100000). Çàòåì èäåò N ÷èñåë, çàäàþùèõ âðåìåíà ïðèõîäà ïàññàæèðîâ íà îñòàíîâêó. Êàæäîå èç ýòèõ ÷èñåë - öåëîå îò 0 äî 100000. Âûõîäíûå äàííûå  âûõîäíîé ôàéë OUTPUT.TXT çàïèøèòå äâà ÷èñëà, ÿâëÿþùèåñÿ îòâåòàìè íà ïåðâûé è âòîðîé âîïðîñû çàäà÷è ñîîòâåòñòâåííî. Åñëè ðåøåíèé íåñêîëüêî, âûâåäèòå ëþáîå èç íèõ. Ïðèìåð ôàéëà INPUT.TXT 100 5 0 210 99 551 99 Ïðèìåð ôàéëà OUTPUT.TXT 10 51
Êîììåíòàðèè. Çàäà÷à ñ Êèðîâñêîé îáëàñòíîé îëèìïèàäû. Çàäà÷à î÷åíü íåïðîñòàÿ. Èäåÿ çàêëþ÷àåòñÿ â òîì, ÷òî âðåìåíà ïðèõîäà ëþäåé íà îñòàíîâêó íàñ èíòåðåñóþò òîëüêî ïî ìîäóëþ k. Íóæíî ïîñ÷èòàòü, ñêîëüêî ÷åëîâåê ïðèõîäèò íà îñòàíîâêó â êàæäûé (ïî mod k) ìîìåíò âðåìåíè, à çàòåì ïåðåáðàòü è íàéòè îïòèìàëüíîå âðåìÿ äëÿ òðîëëåéáóñà.
Çàäà÷à 133 (Ñêà÷àòü àðõèâ)
Çàäà÷à "Ïîåäàíèå ïëîñêîãî ñûðà" Åñòü êóñîê ñûðà â âèäå ïðÿìîóãîëüíèêà ðàçìåðà NxM. Ìàëåíüêèé ìûøîíîê õî÷åò ñúåñòü âåñü êóñîê ñûðà. Íà÷àâ â ïðîèçâîëüíîé êëåòêå, îí, ïîåäàÿ î÷åðåäíîé êóñî÷åê (1õ1), ïåðåõîäèò â ñîñåäíèé (òîëüêî åñëè îí åãî åùå íå ñúåë). Ïîìîãèòå ìàëåíüêîìó ìûøîíêó ñîñòàâèòü ìàðøðóò ïî ïðÿìîóãîëüíèêó, ÷òîáû îí ñúåë âåñü ñûð. Âõîäíûå äàííûå.  ôàéëå INPUT.TXT çàïèñàíû ÷èñëà N, M. (1˜N,M˜30) Âûõîäíûå äàííûå.  ôàéë OUTPUT.TXT âûâåñòè ìàðøðóò ìûøîíêà â âèäå ïîñëåäîâàòåëüíîñòè êîîðäèíàò êóñî÷êîâ, êîòîðûå îí ñúåäàåò. Êóñî÷êè ñûðà èìåþò êîîðäèíàòû îò 1 äî N ïî îñè X, îò 1 äî M ïî îñè Y. Ïðèìåð âõîäíîãî ôàéëà: 2 2 Ïðèìåð âûõîäíîãî ôàéëà: 1 1 2 1 2 2 1 2
Êîììåíòàðèè. Çäåñü íóæíî ïðèäóìàòü êàêîé-íèáóäü ñïîñîá îáîéòè ïðÿìîóãîëüíèê (íàïðèìåð, çìåéêà) è åãî çàïðîãðàììèðîâàòü.
Êîììåíòàðèè. Çàäà÷è 134-135 - ýòî ïîäãîòîâêà ê ðåàëèçàöèè ñîðòèðîâêè. Íà çàäà÷å 134 îòðàáàòûâàåòñÿ îáìåí ýëåìåíòîâ. Çàäà÷à 135 - ïîèñê ìèíèìàëüíîãî ýëåìåíòà è ïîñòàíîâêà åãî íà 1-å ìåñòî. Ïîñëå ýòîãî äî íàïèñàíèÿ ñîðòèðîâêè îñòàåòñÿ òîëüêî ê 135 çàäà÷å äîáàâèòü ïîèñê ìèíèìóìà, íà÷èíàÿ ñî 2-ãî ýëåìåíòà è ïîñòàíîâêó åãî íà 2-å ìåñòî è ò.ä. Çàäà÷è 134-136 ÿâëÿþòñÿ îáÿçàòåëüíûìè äëÿ âñåõ.
Çàäà÷à 134 (Ñêà÷àòü àðõèâ)
×èñëîîáìåííèê  íà÷àëüíûé ìîìåíò â ìàññèâå çàïèñàíû ïî ïîðÿäêó ÷èñëà îò 1 äî N (i-îå ÷èñëî - íà i-îì ìåñòå). Ñ ìàññèâîì ïðîäåëûâàþò ïîñëåäîâàòåëüíî ñëåäóþùóþ îïåðàöèþ: áåðóò äâà ÷èñëà, ñòîÿùèõ íà ìåñòàõ A è B, è ìåíÿþò èõ ìåñòàìè. Òðåáóåòñÿ íàïå÷àòàòü ìàññèâ ïîñëå âûïîëíåíèÿ ýòèõ îïåðàöèé. Âõîäíûå äàííûå Çàïèñàíî ñíà÷àëà ÷èñëî N (2˜N˜100). Äàëåå èäåò ÷èñëî K - êîëè÷åñòâî îïåðàöèé îáìåíà (0˜K˜10000). Äàëåå èäåò K ïàð ÷èñåë - íîìåðà ìåñò ýëåìåíòîâ, îáìåí êîòîðûõ ïðîèñõîäèò. Âûõîäíûå äàííûå Âûâåäèòå ýëåìåíòû ìàññèâà ïîñëå âûïîëíåíèÿ ýòèõ îïåðàöèé. Ïðèìåð âõîäíîãî ôàéëà: 10 2 1 3 3 5 Ïðèìåð âûõîäíîãî ôàéëà 3 2 5 4 1 6 7 8 9 10
Çàäà÷à 135 (Ñêà÷àòü àðõèâ)
"Âûòàñêèâàíèå" ìèíèìóìà  ìàññèâå òðåáóåòñÿ íàéòè ìèíèìàëüíûé ýëåìåíò, è ïîñòàâèòü åãî íà ïåðâîå ìåñòî, à òî, ÷òî ñòîÿëî íà 1-ì ìåñòå - íà åãî ìåñòî. Åñëè ìèíèìàëüíûõ ÷èñåë íåñêîëüêî, ìîæíî ìåíÿòü ñ ëþáûì èç íèõ. Åñëè ìèíèìàëüíîå ÷èñëî óæå ñòîèò íà 1-ì ìåñòå, íè÷åãî èçìåíÿòü íå íóæíî. Âõîäíûå äàííûå Ââîäèòñÿ ÷èñëî N - êîëè÷åñòâî ýëåìåíòîâ ìàññèâà (1˜N˜100), à çàòåì - ýëåìåíòû ìàññèâà (÷èñëà îò 1 äî 10000). Âûõîäíûå äàííûå Òðåáóåòñÿ âûâåñòè N ÷èñåë - ýëåìåíòû ìàññèâà ïîñëå ïåðåñòàíîâêè Ïðèìåð âõîäíîãî ôàéëà 5 3 5 4 1 4 Ïðèìåð âûõîäíîãî ôàéëà 1 5 4 3 4
Çàäà÷à 136 (Ñêà÷àòü àðõèâ)
Ñîðòèðîâêà Âî âõîäíîì ôàéëå çàäàíî ñíà÷àëà ÷èñëî N (1˜N˜100), à çàòåì N öåëûõ ÷èñåë, ïî ìîäóëþ íå ïðåâûøàþùèõ 1000. Âûâåäèòå N ÷èñåë â ïîðÿäêå íåóáûâàíèÿ. Ïðèìåð âõîäíîãî ôàéëà 5 3 1 2 4 2 Ïðèìåð âûõîäíîãî ôàéëà 1 2 2 3 4
Çàäà÷à 137 (Ñêà÷àòü àðõèâ)
Ñîðòèðîâêà âðåìåíè Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N (1˜N˜100), à çàòåì N ìîìåíòîâ âðåìåíè. Êàæäûé ìîìåíò âðåìåíè çàäàåòñÿ 3 öåëûìè ÷èñëàìè - ÷àñû (îò 0 äî 23), ìèíóòû (îò 0 äî 60) è ñåêóíäû (îò 0 äî 60).  âûõîäíîé ôàéë âûâåäèòå ìîìåíòû âðåìåíè, óïîðÿäî÷åííûå â ïîðÿäêå íåóáûâàíèÿ (ìîìåíò âðåìåíè òàêæå âûâîäèòñÿ â âèäå òðåõ ÷èñåë, âåäóùèå íóëè âûâîäèòü íå îáÿçàòåëüíî) Ïðèìåð âõîäíîãî ôàéëà: 4 10 20 30 7 30 00 23 59 59 13 30 30 Ïðèìåð âûõîäíîãî ôàéëà: 7 30 0 10 20 30 13 30 30 23 59 59
Êîììåíòàðèè. Èíòåðåñíî, ÷òî â ýòîé çàäà÷å øêîëüíèêè îáû÷íî ïèøóò ñðàâíåíèå âðåìåí (òî åñòü ñíà÷àëà ñðàâíèâàþò ÷àñû, ïîòîì - ìèíóòû è ò.ä.). Óìåòü ýòî äåëàòü ïðàâèëüíî - î÷åíü âàæíî. Îäíàêî çäåñü èíòåðåñíî îáñóäèòü ñ íèìè èäåþ ïðåäñòàâëåíèÿ âðåìåíè îäíèì öåëûì ÷èñëîì (÷àñû*360 + ìèíóòû*60 + ñåêóíäû) è ñîðòèðîâêó ýòèõ ÷èñåë, à çàòåì ïî ýòèì ÷èñëàì âîññòàíîâëåíèå âðåìåí.
Çàäà÷à 138 (Ñêà÷àòü àðõèâ)
Áîëüøàÿ ñîðòèðîâêà Äàíî ÷èñëî N (1˜N˜100000), à çàòåì N íàòóðàëüíûõ ÷èñåë èç äèàïàçîíà îò 1 äî 100. Âûâåäèòå N ÷èñåë â íåóáûâàþùåì ïîðÿäêå Ïðèìåð âõîäíîãî ôàéëà 5 3 1 2 4 2 Ïðèìåð âûõîäíîãî ôàéëà 1 2 2 3 4
Êîììåíòàðèè. Ýòî çàäà÷à íà öèôðîâóþ ñîðòèðîâêó (ñîðòèðîâêó ïîäñ÷åòîì).
Çàäà÷à 139 (Çàäà÷à áåç òåñòîâ!)
Íåïðàâèëüíàÿ ñîðòèðîâêà. Âàì äàíà ïðîãðàììà, ðåøàþùàÿ 136 çàäà÷ó (p139.pas). Òðåáóåòñÿ íàéòè â íåé îøèáêó, è îáúÿñíèòü (ïèñüìåííî èëè óñòíî), ïî÷åìó òàê ïðîèñõîäèò.
Òåêñò ïðîãðàììû p139.pas
const nmax=100;
var a:array[1..nmax] of integer;
n:integer;
i,j,g:integer;
f1,f2:text;
begin
assign(f1,'input.txt');
reset(f1);
assign(f2,'output.txt');
rewrite(f2);
{×òåíèå âõîäíûõ äàííûõ}
read(f1,n);
for i:=1 to n do read(f1,a[i]);
{Ñîðòèðîâêà ìàññèâà}
for i:=1 to n do begin {Ïîäáèðàåì ÷èñëî íà i-îå ìåñòî}
g:=i; {Ñ÷èòàåì, ÷òî ñàìîå ìàëåíüêîå ÷èñëî,
êîòîðîå íàì âñòðåòèëîñü, ñòîèò íà ìåñòå i}
for j:=i+1 to n do {Ïåðåáèðàåì âñå ÷èñëà ñ i+1 äî êîíöà ìàññèâà}
if a[j]<a[g] then g:=j; {Åñëè íàøëè ÷èñëî, êîòîðîå ìåíüøå,
÷åì òî, ÷òî óæå íàéäåíî, çàïîìèíàåì åãî}
{Ìåíÿåì ìåñòàìè ÷èñëà, ñòîÿùèå íà i-îì è
íà g-îì ìåñòàõ }
{Åñëè a[i]=x, a[g]=y, òî ïîñëå âûïîëíåíèÿ
êîìàíäû: }
a[i]:=a[i]+a[g]; {a[i]=x+y, a[g]=y}
a[g]:=a[i]-a[g]; {a[i]=x+y, a[g]=(x+y)-y=x}
a[i]:=a[i]-a[g]; {a[i]=(x+y)-x=y}
{Òî åñòü ïîñëå ýòîãî a[i]=y, a[g]=x
îáìåí çíà÷åíèé ïðîèçîøåë}
end;
{Âûâîäèì ðåçóëüòàò}
for i:=1 to n do
write(f2,a[i],' ');
close(f1);
close(f2);
end.
Êîììåíòàðèè. Íåïðàâèëüíîñòü ñîðòèðîâêè çàêëþ÷àåòñÿ â òîì, ÷òî êîãäà ïðîèñõîäèò îáìåí ýëåìåíòà ñ ñàìèì ñîáîé (i=g), òî a[i] è a[g] - ýòî îäíà è òà æå ïåðåìåííàÿ, è a[i]-a[g] = 0 âñåãäà. Ýòà çàäà÷à î÷åíü âàæíàÿ. Âî-ïåðâûõ, íà åå ïðèìåðå îáñóæäàåòñÿ âîçìîæíîñòü ïîáî÷íûõ ýôôåêòîâ (ïîêà òàêèõ, à â äàëüíåéøåì ýòî âñïëûâåò ïðè ïåðåäà÷å ïàðàìåòðîâ â ïðîöåäóðû). Âòîðîå - ýòà çàäà÷à ó÷èò øêîëüíèêîâ ÷èòàòü òåêñò ïðîãðàììû, òåñòèðîâàòü è îòëàæèâàòü ÷óæèå ïðîãðàììû (ïðåäïîëàãàåòñÿ, ÷òî øêîëüíèê ñíà÷àëà íàéäåò òåñò, íà êîòîðîì ïðîãðàììà íå ðàáîòàåò, à ïîòîì áóäåò ïîøàãîâî âûïîëíÿòü åå, ñðàâíèâàÿ ñ òåì, ÷òî äîëæíî ïðîèñõîäèòü).
Çàäà÷à 140 (Ñêà÷àòü àðõèâ)
Ðåçóëüòàòû îëèìïèàäû N ó÷àñòíèêîâ îëèìïèàäû ïîëó÷èëè óíèêàëüíûå íîìåðà îò 1 äî N.  ðåçóëüòàòå ðåøåíèÿ çàäà÷ íà îëèìïèàäå êàæäûé ó÷àñòíèê ïîëó÷èë íåêîòîðîå êîëè÷åñòâî áàëëîâ (öåëîå ÷èñëî îò 0 äî 600). Èçâåñòíî, êòî ñêîëüêî áàëëîâ íàáðàë. Òðåáóåòñÿ ïåðå÷èñëèòü ó÷àñòíèêîâ îëèìïèàäû â ïîðÿäêå íåâîçðàñòàíèÿ íàáðàííûõ èìè áàëëîâ. Âõîäíûå äàííûå. Ââîäèòñÿ ñíà÷àëà ÷èñëî N (1˜N˜100) - êîëè÷åñòâî ó÷àñòíèêîâ îëèìïèàäû. Äàëåå ââîäèòñÿ N ÷èñåë - êîëè÷åñòâà íàáðàííûõ ó÷àñòíèêàìè áàëëîâ (1-å ÷èñëî - ýòî áàëëû, íàáðàííûå ó÷àñòíèêîì íîìåð 1, 2-å - ó÷àñòíèêîì íîìåð 2 è ò.ä.) Âûõîäíûå äàííûå. Âûâåäèòå â âûõîäíîé ôàéë N ÷èñåë - íîìåðà ó÷àñòíèêîâ â ïîðÿäêå íåâîçðàñòàíèÿ íàáðàííûõ èìè áàëëîâ (ó÷àñòíèêè, íàáðàâøèå îäèíàêîâîå êîëè÷åñòâî áàëëîâ ìîãóò áûòü âûâåäåíû â ëþáîì ïîðÿäêå). Ïðèìåð âõîäíîãî ôàéëà 5 100 312 0 312 500 Ïðèìåð âûõîäíîãî ôàéëà 5 2 4 1 3
Êîììåíòàðèè. Çäåñü íóæíî ñîðòèðîâàòü îäèí ìàññèâ, è ñèíõðîííî ñ íèì ìåíÿòü äðóãîé. Òîæå, â îáùåì-òî, íå òðèâèàëüíàÿ èäåÿ.
Çàäà÷à 141 (Ñêà÷àòü àðõèâ)
Êîëè÷åñòâî îïåðàöèé Äàíà ïðîãðàììà ñîðòèðîâêè (p141.pas). Òðåáóåòñÿ óçíàòü, ñêîëüêî ðàç ïðè ñîðòèðîâêå êîíêðåòíîãî ìàññèâà ñ ïîìîùüþ ýòîé ïðîãðàììû âûïîëíÿåòñÿ îïåðàöèÿ ñðàâíåíèÿ äâóõ ýëåìåíòîâ ìàññèâà (ñòðîêà 25 ïðîãðàììû). Âõîäíûå äàííûå  ôàéëå input.txt çàïèñàí ìàññèâ â ôîðìàòå (è óäîâëåòâîðÿþùèé îãðàíè÷åíèÿì) èç çàäà÷è 136. Âûõîäíûå äàííûå  ôàéë output.txt âàøà ïðîãðàììà äîëæíà ïå÷àòàòü îäíî ÷èñëî - ñêîëüêî ðàç â ïðîöåññå ñîðòèðîâêè ýòîãî ìàññèâà ïðîãðàììîé p141.pas âûïîëíèòñÿ êîìàíäà ñðàâíåíèÿ äâóõ ýëåìåíòîâ ìàññèâà. Ïðèìåð âõîäíîãî ôàéëà 5 3 1 2 4 2 Ïðèìåð âûõîäíîãî ôàéëà 10
Òåêñò ïðîãðàììû p141.pas
const nmax=100;
var a:array[1..nmax] of integer;
n:integer;
i,j,g:integer;
f1,f2:text;
begin
assign(f1,'input.txt');
reset(f1);
assign(f2,'output.txt');
rewrite(f2);
{×òåíèå âõîäíûõ äàííûõ}
read(f1,n);
for i:=1 to n do read(f1,a[i]);
{Ñîðòèðîâêà ìàññèâà}
for i:=1 to n do begin {Ïîäáèðàåì ÷èñëî íà i-îå ìåñòî}
g:=i; {Ñ÷èòàåì, ÷òî ñàìîå ìàëåíüêîå ÷èñëî,
êîòîðîå íàì âñòðåòèëîñü, ñòîèò íà ìåñòå i}
for j:=i+1 to n do {Ïåðåáèðàåì âñå ÷èñëà ñ i+1 äî êîíöà ìàññèâà}
if a[j]<a[g] then g:=j; {Åñëè íàøëè ÷èñëî, êîòîðîå ìåíüøå,
÷åì òî, ÷òî óæå íàéäåíî, çàïîìèíàåì åãî}
{Ìåíÿåì ìåñòàìè ÷èñëà, ñòîÿùèå íà i-îì è
íà g-îì ìåñòàõ }
{Åñëè a[i]=x, a[g]=y, òî ïîñëå âûïîëíåíèÿ
êîìàíäû: }
if i<>g then begin
a[i]:=a[i]+a[g]; {a[i]=x+y, a[g]=y}
a[g]:=a[i]-a[g]; {a[i]=x+y, a[g]=(x+y)-y=x}
a[i]:=a[i]-a[g]; {a[i]=(x+y)-x=y}
{Òî åñòü ïîñëå ýòîãî a[i]=y, a[g]=x
îáìåí çíà÷åíèé ïðîèçîøåë}
end;
end;
{Âûâîäèì ðåçóëüòàò}
for i:=1 to n do
write(f2,a[i],' ');
close(f1);
close(f2);
end.
Êîììåíòàðèè. Çàäà÷à âàæíàÿ. Âî-ïåðâûõ, çäåñü áîëåå-ìåíåå ÿâíî âîçíèêàåò òàêîå ïîíÿòèå êàê "ñëîæíîñòü àëãîðèòìà", õîòÿ ðàçãîâîð î òîì, ñêîëüêî äåéñòâèé äåëàåò ïðîãðàììà, ìîæíî âåñòè è ðàíüøå. Âî-âòîðûõ, çäåñü ïîêàçûâàåòñÿ, êàê ýòî ìîæíî ïðàêòè÷åñêè ïîñ÷èòàòü (äîáàâèòü â ïðîãðàììó ñ÷åò÷èê).
Êîììåíòàðèè. Íà÷èíàÿ ñ ýòîé çàäà÷è, âîçíèêàþò ìíîãîìåðíûå ìàññèâû.
Çàäà÷à 142 (Ñêà÷àòü àðõèâ)
Ìèíèìóì â òàáëèöå Äàíà òàáëèöà ÷èñåë, ñîñòîÿùàÿ èç N ñòðîê ïî M ÷èñåë â êàæäîé. Âñå ÷èñëà â òàáëèöå - íàòóðàëüíûå, íå ïðåâûøàþùèå 1000. Òðåáóåòñÿ íàéòè íàèìåíüøåå ÷èñëî â ýòîé òàáëèöå. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî ñòðîê, à çàòåì ÷èñëî M - êîëè÷åñòâî ñòîëáöîì òàáëèöû (1˜N˜100, 1˜M˜100). Äàëåå èäåò ñàìà òàáëèöà. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå íàèìåíüøåå ÷èñëî, êîòîðîå âñòðå÷àåòñÿ â òàáëèöå. Ïðèìåð âõîäíîãî ôàéëà 3 4 6 4 10 4 3 7 5 7 6 3 4 3 Ïðèìåð âûõîäíîãî ôàéëà 3
Çàäà÷à 143 (Ñêà÷àòü àðõèâ)
ÃÀÈ Âäîëü øîññå â òî÷êàõ X1,X2,...,XN ðàñïîëîæåíû ïîñòû ÃÀÈ.  òî÷êå X ïðîèçîøëî ìåëêîå ÄÒÏ (äîðîæíî-òðàíñïîðòíîå ïðîèñøåñòâèå). Òðåáóåòñÿ îïðåäåëèòü, êàêîé èç ïîñòîâ ÃÀÈ ðàñïîëîæåí áëèæå âñåãî ê ýòîé òî÷êå, ÷òîáû ñ íåãî ïîñëàòü ê ìåñòó ïðîèñøåñòâèÿ íàðÿä ìèëèöèè. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî ïóíêòîâ ÃÀÈ. (1˜N˜100) Äàëåå ñëåäóþò êîîðäèíàòû ðàñïîëîæåíèÿ ïîñòîâ ÃÀÈ íà ïðÿìîì øîññå (öåëûå ÷èñëà îò -10000 äî 10000). Äàëåå èäåò êîîðäèíàòà òî÷êè, â êîòîðîé ïðîèçîøëî ÄÒÌ (öåëîå ÷èñëî îò -10000 äî 10000). Âûõîäíûå äàííûå  âûõîäíîé ôàéë òðåáóåòñÿ âûâåñòè îäíî ÷èñëî - íîìåð ïîñòà ÃÀÈ, ñ êîòîðîãî íóæíî ïîñëàòü íàðÿä ê ìåñòó ÄÒÏ. Åñëè íåñêîëüêî ïîñòîâ ÃÀÈ íàõîäÿòñÿ íà îäèíàêîâîì ðàññòîÿíèè îò òî÷êè ÄÒÏ, âûâåäèòå ëþáîé èç íèõ. Ïðèìåð âõîäíîãî ôàéëà 5 10 2 8 -7 3 7 Ïðèìåð âûõîäíîãî ôàéëà 3
Çàäà÷à 144 (Ñêà÷àòü àðõèâ)
Äèàãîíàëüêè  êâàäðàòíîé òàáëèöå NxN ïîäñ÷èòàòü ñóììû ÷èñåë, ñòîÿùèõ íà äèàãîíàëÿõ. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå ñîäåðæèòñÿ ÷èñëî N (1˜N˜100), à çàòåì ìàòðèöà NxN. Ýëåìåíòû ìàòðèöû - ÷èñëà èç äèàïàçîíà integer. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûäàòü ñíà÷àëà ñóììó ÷èñåë íà ãëàâíîé, à çàòåì - íà ïîáî÷íîé äèàãîíàëè. Ïðèìåð âõîäíîãî ôàéëà 3 1 2 3 4 5 6 10 9 8 Ïðèìåð âûõîäíîãî ôàéëà 14 18
Çàäà÷à 145 (Ñêà÷àòü àðõèâ)
Ìàêñèìàëüíàÿ ñòðîêà  ìàòðèöå íàéòè íîìåð ñòðîêè, ñóììà ÷èñåë â êîòîðîé ìàêñèìàëüíà. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíû ÷èñëà N è M - êîëè÷åñòâî ñòðîê è ñòîëáöîâ ìàòðèöû (êàæäîå èç íèõ - èç äèàïàçîíà îò 1 äî 100), à çàòåì ñàìà ìàòðèöà. Ýëåìåíòû ìàòðèöû - ÷èñëà èç äèàïàçîíà integer. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåñòè íîìåð ñòðîêè, ñóììà ÷èñåë â êîòîðîé ìàêñèìàëüíà. Åñëè òàêèõ ñòðîê íåñêîëüêî, âûâåñòè ïîñëåäíþþ èç íèõ. Ïðèìåð âõîäíîãî ôàéëà 3 2 1 2 3 4 5 6 Ïðèìåð âûõîäíîãî ôàéëà 3
Çàäà÷à 146 (Ñêà÷àòü àðõèâ)
Íîëèêè  ìàòðèöå íàéòè ïîëîæåíèå íóëåâîãî ýëåìåíòà. Âõîäíûå äàííûå Ôîðìàò âõîäíûõ äàííûõ òàêîé æå, êàê â ïðåäûäóùåé çàäà÷å. Õîòÿ áû îäèí íóëåâîé ýëåìåíò â ìàòðèöå âñåãäà ñóùåñòâóåò. Âûõîäíûå äàííûå Âûâåñòè ñíà÷àëà íîìåð ñòðîêè, à çàòåì - íîìåð ñòîëáöà íóëåâîãî ýëåìåíòà. Åñëè â ìàòðèöå íåñêîëüêî íóëåé, âûäàòü ïîçèöèþ ëþáîãî èç íèõ. Ïðèìåð âõîäíîãî ôàéëà 3 4 0 1 2 3 4 5 0 1 2 3 4 5 Ïðèìåð âûõîäíîãî ôàéëà 2 3
Çàäà÷à 147 (Ñêà÷àòü àðõèâ)
Ñèììåòðè÷íàÿ ìàòðèöà Äàíà êâàäðàòíàÿ ìàòðèöà. Ïðîâåðèòü, ÿâëÿåòñÿ ëè îíà ñèììåòðè÷íîé îòíîñèòåëüíî ãëàâíîé äèàãîíàëè. Âõîäíûå äàííûå.  ôàéëå INPUT.TXT çàïèñàíî ÷èñëî n (0<n˜100).  ñëåäóþùèõ n ñòðîêàõ çàïèñàíî ïî n öåëûõ ÷èñåë îò -32768 äî 32767. Âûõîäíûå äàííûå.  ôàéë OUTPUT.TXT âûâåñòè YES, åñëè ìàòðèöà ñèììåòðè÷íà îòíîñèòåëüíî ãëàâíîé äèàãîíàëè, èíà÷å âûâåñòè NO. Ïðèìåð ôàéëà INPUT.TXT 3 1 2 3 2 4 5 3 5 6 Ïðèìåð ôàéëà OUTPUT.TXT YES
Çàäà÷à 148 (Ñêà÷àòü àðõèâ)
Òðåóãîëüíèê Ïàñêàëÿ Òðåóãîëüíèê Ïàñêàëÿ ñòðîèòñÿ ñëåäóþùèì îáðàçîì. Ïåðâàÿ ñòðîêà ñîñòîèò èç îäíîãî ÷èñëà, ðàâíîãî åäèíèöå. Êàæäàÿ ñëåäóþùàÿ ñîäåðæèò íà îäíî ÷èñëî áîëüøå, ÷åì ïðåäûäóùàÿ. Ïåðâîå è ïîñëåäíåå èç ýòèõ ÷èñåë ðàâíû 1, à âñå îñòàëüíûå âû÷èñëÿþòñÿ êàê ñóììà ÷èñëà, ñòîÿùåãî â ïðåäûäóùåé ñòðîêå íàä íèì è ÷èñëà, ñòîÿùåãî â ïðåäûäóùåé æå ñòðîêå ñëåâà îò íåãî. Âõîäíûå äàííûå.  ôàéëå INPUT.TXT çàïèñàíî îäíî ÷èñëî N (0˜N˜30). Âûõîäíûå äàííûå.  ôàéë OUTPUT.TXT âûâåñòè N ñòðîê òðåóãîëüíèêà Ïàñêàëÿ. Ïðèìå÷àíèå. Âñå ÷èñëà â òðåóãîëüíèêå Ïàñêàëÿ ïðè óêàçàííûõ îãðàíè÷åíèÿõ âõîäÿò â Longint. Ïðèìåð ôàéëà INPUT.TXT 8 Ïðèìåð ôàéëà OUTPUT.TXT 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1
Çàäà÷à 149 (Ñêà÷àòü àðõèâ)
Äàíû äâå êâàäðàòíûõ òàáëèöû ÷èñåë. Òðåáóåòñÿ ïîñòðîèòü òðåòüþ, êàæäûé ýëåìåíò êîòîðîé ðàâåí ñóììå ýëåìåíòîâ, ñòîÿùèõ íà òîì æå ìåñòå â 1-é è 2-é òàáëèöàõ. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N, çàòåì çàïèñàíà ïåðâàÿ òàáëèöà, à ïîñëå íåå - âòîðàÿ. Ýëåìåíòû òàáëèö - ÷èñëà îò 0 äî 100. 1˜N˜100. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå ðåçóëüòèðóþùóþ òàáëèöó. Ïðèìåð âõîäíîãî ôàéëà 3 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 Ïðèìåð âûõîäíîãî ôàéëà 12 14 16 18 20 22 24 26 28
Êîììåíòàðèè. Çàäà÷è ïðî õîæäåíèå ïî òàáëèöå â íåêîòîðîì ñìûñëå ïðåäâàðÿþò òåìó àëãîðèòìîâ íà ãðàôàõ. Ãðàôû çàòåì âîçíèêàþò êàê âïîëíå ëîãè÷íîå îáîáùåíèå ëàáèðèíòîâ, çàäàâàåìûõ òàáëèöàìè.
Çàäà÷à 150 (Ñêà÷àòü àðõèâ)
Õîæäåíèå çà çîëîòîì - 1 Îäíàæäû öàðü ðåøèë âîçíàãðàäèòü îäíîãî èç ñâîèõ ìóäðåöîâ çà õîðîøóþ ðàáîòó. Îí ïðèâåë åãî â ïðÿìîóãîëüíóþ êîìíàòó ðàçìðîì NxM, â êàæäîé êëåòêå êîòîðîé ëåæàëî íåñêîëüêî êèëîãðàììîâ çîëîòà. Öàðü ðàçðåøèë ìóäðåöó ñäåëàòü îáîéòè íåñêîëüêî êëåòîê (ïåðåõîäÿ ñ êëåòêè, ãäå ñåé÷àñ íàõîäèòñÿ ìóäðåö, â îäíó èç ÷åòûðåõ ñ íåé ñîñåäíèõ), è ñîáðàòü âñå çîëîòî, êîòîðîå ïîïàäåòñÿ íà åãî ïóòè. Âàì äàí ìàðøðóò ìóäðåöà. Òðåáóåòñÿ îïðåäåëèòü, ñêîëüêî êèëîãðàììîâ çîëîòà îí ñîáðàë. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ïëàí êîìíàòû. Ñíà÷àëà çàïèñàíî êîëè÷åñòâî ñòðîê N, çàòåì - êîëè÷åñòâî ñòîëáöîâ M (1˜N˜20,1˜M˜20). Çàòåì çàïèñàíî N ñòðîê ïî M ÷èñåë â êàæäîé - êîëè÷åñòâî êèëîãðàììîâ çîëîòà, êîòîðîå ëåæèò â äàííîé êëåòêå (÷èñëî îò 0 äî 50). Äàëåå çàïèñàíî ÷èñëî X - ñêîëüêî êëåòîê îáîøåë ìóäðåö. Äàëåå çàïèñàíû êîîðäèíàòû ýòèõ êëåòîê (êîîðäèíàòû êëåòêè - ýòî äâà ÷èñëà: ïåðâîå îïðåäåëÿåò íîìåð ñòðîêè, âòîðîå - íîìåð ñòîëáöà, âåðõíÿÿ ëåâàÿ êëåòêà íà ïëàíå èìååò êîîðäèíàòû (1,1), ïðàâàÿ íèæíÿÿ - (N,M)). Ãàðàíòèðóåòñÿ, ÷òî ìóäðåö íå ïðîõîäèë ïî îäíîé è òîé æå êëåòêå äâàæäû. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå êîëè÷åñòâî êèëîãðàììîâ çîëîòà, êîòîðîå ñîáðàë ìóäðåö. Ïðèìåð âõîäíîãî ôàéëà 3 4 1 2 3 4 5 6 7 8 9 10 11 12 5 1 1 2 1 2 2 2 3 1 3 Ïðèìåð âûõîäíîãî ôàéëà 22
Çàäà÷à 151 (Ñêà÷àòü àðõèâ)
Õîæäåíèå çà çîëîòîì - 2 Çàäà÷à òàêàÿ æå, êàê è ïðåäûäóùàÿ, òîëüêî ìóäðåö ìîã áîëåå îäíîãî ðàçà ïðîõîäèòü ïî îäíîé è òîé æå êëåòêå. Çîëîòî ñ íåå îí áðàë ïðè ýòîì òîëüêî îäèí ðàç - êîãäà ïðîõîäèë ïî êëåòêå â ïåðâûé ðàç. Âõîäíûå è âûõîäíûå äàííûå òàêèå æå, êàê â ïðåäûäóùåé çàäà÷å. Äîïîëíèòåëüíîå îãðàíè÷åíèå: ÷èñëî ïðîéäåííûõ ìóäðåöîì êëåòîê íå ïðåâûøàåò 10000. Ïðèìåð âõîäíîãî ôàéëà 3 4 1 2 3 4 5 6 7 8 9 10 11 12 9 1 1 2 1 2 2 2 3 1 3 1 2 1 1 1 2 2 2 Ïðèìåð âûõîäíîãî ôàéëà 30
Çàäà÷à 152 (Ñêà÷àòü àðõèâ)
Õîæäåíèå çà çîëîòîì - 3 Çàäà÷à òàêàÿ æå, êàê è ïðåäûäóùàÿ, òîëüêî ïåðåäâèæåíèÿ ìóäðåöà çàäàþòñÿ äðóãèì ñïîñîáîì: Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ïëàí êîìíàòû. Ñíà÷àëà çàïèñàíî êîëè÷åñòâî ñòðîê N, çàòåì - êîëè÷åñòâî ñòîëáöîâ M (1˜N˜20,1˜M˜20). Çàòåì çàïèñàíî N ñòðîê ïî M ÷èñåë â êàæäîé - êîëè÷åñòâî êèëîãðàììîâ çîëîòà, êîòîðîå ëåæèò â äàííîé êëåòêå (÷èñëî îò 0 äî 50). Äàëåå çàïèñàíî ÷èñëî X - ñêîëüêî êëåòîê îáîøåë ìóäðåö. 1˜X˜10000. Èçâåñòíî, ÷òî ìóäðåö íà÷àë ñ êëåòêè ñ êîîðäèíàòàìè (1,1). Äàëåå çàïèñàíî X-1 ÷èñëî: êóäà ïåðåìåùàëñÿ ìóäðåö: ÷èñëî 1 îáîçíà÷àåò, ÷òî ìóäðåö äåëàë øàã âïðàâî, ÷èñëî 2 îáîçíà÷àåò, ÷òî ìóäðåö äåëàë øàã ââåðõ, ÷èñëî 3 îáîçíà÷àåò, ÷òî ìóäðåö äåëàë øàã âëåâî, ÷èñëî 4 îáîçíà÷àåò, ÷òî ìóäðåö äåëàë øàã âíèç. Èçâåñòíî, ÷òî ìóäðåö íå âûõîäèë èç ëàáèðèíòà, ïðè ýòîì îí ìîã ÷åðåç îäíó è òó æå êëåòêó ïðîéòè íåñêîëüêî ðàç. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå êîëè÷åñòâî êèëîãðàììîâ çîëîòà, êîòîðîå ñîáðàë ìóäðåö. 3 4 1 2 3 4 5 6 7 8 9 10 11 12 9 4 1 1 2 3 3 1 4
Çàäà÷à 153 (Ñêà÷àòü àðõèâ)
 ïðÿìîóãîëüíîé òàáëèöå NxM â íà÷àëå èãðîê íàõîäèòñÿ â ëåâîé âåðõíåé êëåòêå. Çà îäèí õîä åìó ðàçðåøàåòñÿ ïåðåìåùàòüñÿ â ñîñåäíþþ êëåòêó ëèáî âïðàâî, ëèáî âíèç (âëåâî è ââåðõ ïåðåìåùàòüñÿ çàïðåùåíî). Ïîñ÷èòàéòå, ñêîëüêî åñòü ñïîñîáîâ ó èãðîêà ïîïàñòü â ïðàâóþ íèæíþþ êëåòêó. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàäàíî äâà ÷èñëà N è M - ðàçìåðû òàáëèöû (1˜N˜10, 1˜M˜10). Âûõîäíûå äàííûå  âûõîäíîé ôàéë çàïèøèòå èñêîìîå ÷èñëî ñïîñîáîâ. Ïðèìå÷àíèå Ïðè óêàçàííûõ îãðàíè÷åíèÿõ, ÷èñëî ñïîñîáîâ âõîäèò â òèï Longint. Ïðèìåð âõîäíîãî ôàéëà 2 3 Ïðèìåð âûõîäíîãî ôàéëà 3 Ïîÿñíåíèå Åñëè ó íàñ åñòü òàáëèöà èç 2 ñòðîê è 3 ñòîëáöîâ, òî ñóùåñòâóþò ñëåäóþùèå ñïîñîáû ïîïàñòü èç ëåâîãî âåðõíåãî óãëà â ïðàâûé íèæíèé: 1) âíèç, âïðàâî, âïðàâî 2) âïðàâî, âíèç, âïðàâî 3) âïðàâî, âïðàâî, âíèç Åùå îäèí ïðèìåð âõîäíîãî ôàéëà 3 3 Ïðèìåð âûõîäíîãî ôàéëà 6
Êîììåíòàðèè. Çàäà÷à íà äèíàìè÷åñêîå ïðîãðàììèðîâàíèå. Âïðî÷åì, îíà èñïîëüçóåòñÿ ëèøü êàê ïîâîä ïîãîâîðèòü î ìåòîäå ïîñëåäîâàòåëüíîãî ïîäñ÷åòà (íå íàçûâàÿ åãî ïîêà äèíàìè÷åñêèì ïðîãðàììèðîâàíèåì). Ðåøåíèþ ýòîé çàäà÷å ïîìîãàåò è çíàíèå êîìáèíàòîðèêè. Ñëåäóþùàÿ çàäà÷à ÿâëÿåòñÿ ëîãè÷íûì ïðîäîëæåíèåì, îäíàêî òóò óæå áåç äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ íå îáîéòèñü.
Çàäà÷à 154 (Ñêà÷àòü àðõèâ)
 ïðÿìîóãîëüíîé òàáëèöå NxM (â êàæäîé êëåòêå êîòîðîé çàïèñàíî íåêîòîðîå ÷èñëî) â íà÷àëå èãðîê íàõîäèòñÿ â ëåâîé âåðõíåé êëåòêå. Çà îäèí õîä åìó ðàçðåøàåòñÿ ïåðåìåùàòüñÿ â ñîñåäíþþ êëåòêó ëèáî âïðàâî, ëèáî âíèç (âëåâî è ââåðõ ïåðåìåùàòüñÿ çàïðåùåíî). Ïðè ïðîõîäå ÷åðåç êëåòêó ñ èãðîêà áåðóò ñòîëüêî ó.å., êàêîå ÷èñëî çàïèñàíî â ýòîé êëåòêå (äåíüãè áåðóò òàêæå çà ïåðâóþ è ïîñëåäíþþ êëåòêè åãî ïóòè). Òðåáóåòñÿ íàéòè ìèíèìàëüíóþ ñóììó ó.å., çàïëàòèâ êîòîðóþ èãðîê ìîæåò ïîïàñòü â ïðàâûé íèæíèé óãîë. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàäàíî äâà ÷èñëà N è M - ðàçìåðû òàáëèöû (1˜N˜20, 1˜M˜20). Çàòåì èäåò N ñòðîê ïî M ÷èñåë â êàæäîé - ðàçìåðû øòðàôîâ â ó.å. çà ïðîõîæäåíèå ÷åðåç ñîîòâåòñòâóþùèå êëåòêè (÷èñëà îò 0 äî 100). Âûõîäíûå äàííûå  âûõîäíîé ôàéë çàïèøèòå ìèíèìàëüíóþ ñóììó, ïîòðàòèâ êîòîðóþ ìîæíî ïîïàñòü â ïðàâûé íèæíèé óãîë. Ïðèìåð âõîäíîãî ôàéëà 3 4 1 1 1 1 5 2 2 100 9 4 2 1 Ïðèìåð âûõîäíîãî ôàéëà 8
Êîììåíòàðèè. Ïåðåä òåì, êàê ðåøàòü çàäà÷è äàëüøå, îáñóæäàåòñÿ, êàêèì îáðàçîì â ïàìÿòè êîìïüþòåðà ìîæíî ïðåäñòàâëÿòü ãðàôû. Ðå÷ü èäåò î ìàòðèöå ñìåæíîñòè è ñïèñêå ðåáåð.
Çàäà÷à 155 (Ñêà÷àòü àðõèâ)
Ãîðîäà è äîðîãè  ãàëàêòèêå "Milky Way" íà ïëàíåòå "Neptune" åñòü N ãîðîäîâ, íåêîòîðûå èç êîòîðûõ ñîåäèíåíû äîðîãàìè. Èìïåðàòîð "Maximus" ãàëàêòèêè "Milky Way" ðåøèë ïðîâåñòè èíâåíòàðèçàöèþ äîðîã íà ïëàíåòå "Neptune". Íî, êàê îêàçàëîñü, îí íå ñèëåí â ìàòåìàòèêå, ïîýòîìó îí ïðîñèò âàñ ñîñ÷èòàòü êîëè÷åñòâî äîðîã. Âõîäíûå äàííûå.  ôàéëå INPUT.TXT çàïèñàíî ÷èñëî N (0˜N˜100).  ñëåäóþùèõ N ñòðîêàõ çàïèñàíî ïî N ÷èñåë, êàæäîå èç êîòîðûõ ÿâëÿåòñÿ åäèíè÷êîé èëè íîëèêîì. Ïðè÷åì, åñëè â ïîçèöèè (i,j) êâàäðàòíîé ìàòðèöû ñòîèò åäèíè÷êà, òî i-ûé è j-ûé ãîðîäà ñîåäèíåíû äîðîãàìè, à åñëè íîëèê, òî íå ñîåäèíåíû. Âûõîäíûå äàííûå.  ôàéë OUTPUT.TXT âûâåñòè îäíî ÷èñëî - êîëè÷åñòâî äîðîã íà ïëàíåòå "Neptune". Ïðèìå÷àíèå. Âñå äîðîãè äâóñòîðîííèå, òî åñòü åñëè åñòü äîðîãà èç ãîðîäà i â ãîðîä j, òî åñòü è äîðîãà èç ãîðîäà j â ãîðîä i, è ýòî òà æå ñàìàÿ äîðîãà. Ïðèìåð ôàéëà INPUT.TXT 5 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 Ïðèìåð ôàéëà OUTPUT.TXT 3
Çàäà÷à 156 (Ñêà÷àòü àðõèâ)
Ñâåòîôîð÷èêè  ïîäçåìåëüå M òîííåëåé è N ïåðåêðåñòêîâ, êàæäûé òîííåëü ñîåäèíÿåò êàêèå-òî äâà ïåðåêðåñòêà. Ìûøèíûé êîðîëü ðåøèë ïîñòàâèòü ïî ñâåòîôîðó â êàæäîì òîííåëå ïåðåä êàæäûì ïåðåêðåñòêîì. Íàïèøèòå ïðîãðàììó, êîòîðàÿ ïîñ÷èòàåò, ñêîëüêî ñâåòîôîðîâ äîëæíî áûòü óñòàíîâëåíî íà êàæäîì èç ïåðåêðåñòêîâ. Ïåðåêðåñòêè ïðîíóìåðîâàíû ÷èñëàìè îò 1 äî N. Âõîäíûå äàííûå.  ôàéëå INPUT.TXT çàïèñàíî äâà ÷èñëà N è M (0<N˜100, 0˜M˜N*(N-1)/2 ).  ñëåäóþùèõ M ñòðîêàõ çàïèñàíû ïî äâà ÷èñëà i è j (1˜i,j˜N ), êîòîðûå îçíà÷àþò, ÷òî ïåðåêðåñòêè i è j ñîåäèíåíû òîííåëåì. Âûõîäíûå äàííûå.  ôàéë OUTPUT.TXT âûâåñòè N ÷èñåë: k-îå ÷èñëî îçíà÷àåò êîëè÷åñòâî ñâåòîôîðîâ íà k-îì ïåðåêðåñòêå. Ïðèìå÷àíèå. Ìîæíî ñ÷èòàòü, ÷òî ëþáûå äâà ïåðåêðåñòêà ñîåäèíåíû íå áîëåå, ÷åì îäíèì òîííåëåì. Íåò òîííåëåé îò ïåðåêðåñòêà i äî íåãî ñàìîãî. Ïðèìåð ôàéëà INPUT.TXT 7 10 5 1 3 2 7 1 5 2 7 4 6 5 6 4 7 5 2 1 5 3 Ïðèìåð ôàéëà OUTPUT.TXT 3 3 2 2 5 2 3
Çàäà÷à 157 (Ñêà÷àòü àðõèâ)
Öâåòíîé äîæäü  Áàíàíîâîé ðåñïóáëèêå î÷åíü ìíîãî õîëìîâ, ñîåäèíåííûõ ìîñòàìè. Íà õèìè÷åñêîì çàâîäå ïðîèçîøëà àâàðèÿ, â ðåçóëüòàòå ÷åãî èñïàðèëîñü ýêñïåðèìåíòàëüíîå óäîáðåíèå "çîâàí". Íà ñëåäóþùèé äåíü âûïàë öâåòíîé äîæäü, ïðè÷åì îí ïðîøåë òîëüêî íàä õîëìàìè, â íåêîòîðûõ ìåñòàõ ïàäàëè êðàñíûå êàïëè, â íåêîòîðûõ - ñèíèå, à â îñòàëüíûõ - çåëåíûå, â ðåçóëüòàòå ÷åãî õîëìû ñòàëè ñîîòâåòñòâóþùåãî öâåòà. Ïðåçèäåíòó Áàíàíîâîé ðåñïóáëèêè ýòî ïîíðàâèëîñü, íî åìó çàõîòåëîñü ïîêðàñèòü ìîñòû ìåæäó âåðøèíàìè õîëìîâ òàê, ÷òîáû ìîñòû áûëè ïîêðàøåíû â öâåò õîëìîâ, êîòîðûå îíè ñîåäèíÿþò. Ê ñîæàëåíèþ, åñëè õîëìû ðàçíîãî öâåòà, òî ïîêðàñèòü ìîñò òàêèì îáðàçîì íå óäàñòñÿ. Ïîñ÷èòàòü êîëè÷åñòâî òàêèõ "ïëîõèõ" ìîñòîâ. Âõîäíûå äàííûå.  ôàéëå INPUT.TXT â ïåðâîé ñòðîêå çàïèñàíî N (0<N˜100) - ÷èñëî õîëìîâ. Äàëåå èäåò ìàòðèöà ñìåæíîñòè, îïèñûâàþùàÿ íàëè÷èå ìîñòîâ ìåæäó õîëìàìè (1-ìîñò åñòü, 0-íåò).  ïîñëåäíåé ñòðîêå çàïèñàíî N ÷èñåë, îáîçíà÷àþùèõ öâåò õîëìîâ: 1 - êðàñíûé; 2 - ñèíèé; 3 - çåëåíûé. Âûõîäíûå äàííûå.  ôàéë OUTPUT.TXT âûâåñòè êîëè÷åñòâî "ïëîõèõ" ìîñòîâ. Ïðèìåð ôàéëà INPUT.TXT 7 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 3 3 Ïðèìåð ôàéëà OUTPUT.TXT 4
Çàäà÷à 158 (Ñêà÷àòü àðõèâ)
Èçäåâàòåëüñòâî Ýïèãðàô: Øòèðëèö åõàë íà ìàøèíå, óâèäåë ãîëîñóþùåãî Áîðìàíà, è ïðîåõàë ìèìî. ×åðåç íåêîòîðîå âðåìÿ îí ñíîâà óâèäåë ãîëîñóþùåãî Áîðìàíà, è ñíîâà ïðîåõàë ìèìî. Âñêîðå îí îïÿòü óâèäåë ãîëîñóþùåãî Áîðìàíà. -Èçäåâàåòñÿ! - ïîäóìàë Áîðìàí. -Êîëüöåâàÿ! - äîãàäàëñÿ Øòèðëèö.  ãîðîäå N ïëîùàäåé. Ëþáûå äâå ïëîùàäè ñîåäèíåíû ìåæäó ñîáîé ðîâíî îäíîé äîðîãîé ñ äâóñòîðîííèì äâèæåíèåì.  ýòîì ãîðîäå æèâåò Øòèðëèö. Ó Øòèðëèöà åñòü õîááè - îí ëþáèò âîñêðåñíûì óòðîì âûéòè èç äîìà, ñåñòü â ìàøèíó, âûáðàòü êàêîé-íèáóäü êîëüöåâîé ìàðøðóò, ïðîõîäÿùèé ðîâíî ïî òðåì ïëîùàäÿì (òî åñòü ñíà÷àëà îí åäåò ñ êàêîé-òî ïëîùàäè íà êàêóþ-òî äðóãóþ, ïîòîì - íà òðåòüþ, çàòåì âîçâðàùàåòñÿ íà íà÷àëüíóþ, è îïÿòü åäåò ïî ýòîìó ìàðøðóòó). Îí âîîáðàæàåò, ÷òî ãäå-òî íà ýòîì ïóòè ñòîèò Áîðìàí. È òàê âîò åçäèò Øòèðëèö âñå âîñêðåñåíüå, ïîêà ãîëîâà íå çàêðóæèòñÿ, è ðàäóåòñÿ... Åñòåñòâåííî, ÷òî Øòèðëèöó õî÷åòñÿ ïðîåçæàòü ìèìî òî÷êè, â êîòîðîé, êàê îí âîîáðàæàåò, ñòîèò Áîðìàí, êàê ìîæíî ÷àùå. Äëÿ ýòîãî, åñòåñòâåííî, âûáðàííûé Øòèðëèöåì ìàðøðóò äîëæåí áûòü êàê ìîæíî êîðî÷å. Íàïèøèòå ïðîãðàììó, êîòîðàÿ âûáåðåò îïòèìàëüíûé äëÿ Øòèðëèöà ìàðøðóò. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå INPUT.TXT çàïèñàíî ñíà÷àëà ÷èñëî N (3˜N˜100), à çàòåì ìàòðèöà NxN ðàññòîÿíèé ìåæäó ïëîùàäÿìè (÷èñëî â ïîçèöèè i,j îáîçíà÷àåò äëèíó äîðîãè, ñîåäèíÿþùåé i-óþ è j-óþ ïëîùàäè). Âñå ÷èñëà â ìàòðèöå (êðîìå ñòîÿùèõ íà ãëàâíîé äèàãîíàëè) - íàòóðàëüíûå, íå ïðåâûøàþùèå 1000. Ìàòðèöà ñèììåòðè÷íà îòíîñèòåëüíî ãëàâíîé äèàãîíàëè, íà ãëàâíîé äèàãîíàëè ñòîÿò 0. Âûõîäíûå äàííûå  âûõîäíîé ôàéë OUTPUT.TXT âûâåäèòå íîìåðà ïëîùàäåé â îïòèìàëüíîì ìàðøðóòå. Åñëè ìàðøðóòîâ íåñêîëüêî, âûâåäèòå ëþáîé èç íèõ. Ïðèìåð ôàéëà INPUT.TXT 5 0 20 10 30 40 20 0 30 1 2 10 30 0 40 1000 30 1 40 0 21 40 2 1000 21 0 Ïðèìåð ôàéëà OUTPUT.TXT 4 5 2
Çàäà÷à 159 (Ñêà÷àòü àðõèâ)
Òðåóãîëüíèê Íà ïëîñêîñòè äàíû N òî÷åê. Íèêàêèå äâå òî÷êè íå ñîâïàäàþò, íèêàêèå òðè íå ëåæàò íà îäíîé ïðÿìîé. Íàéäèòå òðåóãîëüíèê ñ âåðøèíàìè â ýòèõ òî÷êàõ, èìåþùèé íàèìåíüøèé âîçìîæíûé ïåðèìåòð. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå INPUT.TXT çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî òî÷åê (3˜N˜50), à çàòåì N ïàð âåùåñòâåííûõ ÷èñåë, çàäàþùèõ êîîðäèíàòû òî÷åê. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå òðè ÷èñëà - íîìåðà òî÷åê, êîòîðûå äîëæíû áûòü âåðøèíàìè òðåóãîëüíèêà, ÷òîáû åãî ïåðèìåòð áûë ìèíèìàëåí. Åñëè ðåøåíèé íåñêîëüêî âûâåäèòå ëþáîå èç íèõ. Ïðèìå÷àíèå Åñëè ó âàñ åñòü äâå òî÷êè, è êîîðäèíàòû îäíîé èç íèõ X1,Y1, à äðóãîé X2,Y2, òî ðàññòîÿíèå R ìåæäó íèìè ìîæíî âû÷èñëèòü ïî ôîðìóëå: R:=sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); Çäåñü R äîëæíà áûòü ïåðåìåííîé âåùåñòâåííîãî òèïà (íàïðèìåð, real), à sqrt - ñòàíäàðòíàÿ ôóíêöèÿ, âû÷èñëÿþùàÿ êâàäðàòíûé êîðåíü. Ïðèìåð ôàéëà INPUT.TXT 5 0 0 1.3 0 -2 0.1 1 0 10 10 Ïðèìåð ôàéëà OUTPUT.TXT 1 2 4
Êîììåíòàðèè. Ýòà çàäà÷à ê ãðàôàì íèêàêîãî îòíîøåíèÿ íå èìååò. Íî ñ äðóãîé ñòîðîíû, ýòî íè÷òî èíîå, êàê ïðåäûäóùàÿ çàäà÷à, â êîòîðîé ãðàô ÿâíî íå çàäàí. Âïðèíöèïå, ìîæíî ïîñòðîèòü ïîëíûé ãðàô (âåñ ðåáðà - äëèíà îòðåçêà ìåæäó òî÷êàìè) è äàëüøå èñïîëüçîâàòü ïðåäûäóùóþ çàäà÷ó. Õîòÿ ìîæíî (è, íàâåðíî, áîëåå ïðàâèëüíî) âîîáùå íèêàêîãî ãðàôà íå ñòðîèòü, ÷òî áîëüøèíñòâî è äåëàåò.
Êîììåíòàðèè. Ðàññìàòðèâàåòñÿ è ðàçáèðàåòñÿ âîëíîâîé àëãîðèòì. Îí ðàçáèðàåòñÿ íà ïðèìåðå òàáëèöû, à çàòåì îáîùàåòñÿ íà ãðàôû. Íà ìîé âçãëÿä, ïèñàòü åãî íà ãðàôå äàæå ïðîùå, ÷åì íà òàáëèöå, õîòÿ äëÿ ïîíèìàíèÿ òàáëèöà, âîçìîæíî, íåñêîëüêî íàãëÿäíåå.
Çàäà÷à 160 (Ñêà÷àòü àðõèâ)
Äëèíà ïóòè  íåîðèåíòèðîâàííîì ãðàôå òðåáóåòñÿ íàéòè äëèíó ìèíèìàëüíîãî ïóòè ìåæäó äâóìÿ âåðøèíàìè. Ãàðàíòèðóåòñÿ, ÷òî ïóòü ñóùåñòâóåò. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî âåðøèí â ãðàôå (1˜N˜100). Çàòåì çàïèñàíà ìàòðèöà ñìåæíîñòè (0 îáîçíà÷àåò îòñóòñòâèå ðåáðà, 1 - íàëè÷èå ðåáðà). Çàòåì çàïèñàíû íîìåðà äâóõ âåðøèí - íà÷àëüíîé è êîíå÷íîé. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå îäíî ÷èñëî - äëèíó ïóòè (êîëè÷åñòâî ðåáåð, êîòîðûå íóæíî ïðîéòè). Ïðèìåð âõîäíîãî ôàéëà 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 Ïðèìåð âûõîäíîãî ôàéëà 3
Çàäà÷à 161 (Ñêà÷àòü àðõèâ)
Äëèíà ïóòè - 2 (Òàêàÿ æå çàäà÷à, êàê äëèíà ïóòè, íî ïóòü ìîæåò íå ñóùåñòâîâàòü).  íåîðèåíòèðîâàííîì ãðàôå òðåáóåòñÿ íàéòè äëèíó ìèíèìàëüíîãî ïóòè ìåæäó äâóìÿ âåðøèíàìè. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî âåðøèí â ãðàôå (1˜N˜100). Çàòåì çàïèñàíà ìàòðèöà ñìåæíîñòè (0 îáîçíà÷àåò îòñóòñòâèå ðåáðà, 1 - íàëè÷èå ðåáðà). Çàòåì çàïèñàíû íîìåðà äâóõ âåðøèí - íà÷àëüíîé è êîíå÷íîé. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå îäíî ÷èñëî - äëèíó ïóòè (êîëè÷åñòâî ðåáåð, êîòîðûå íóæíî ïðîéòè). Åñëè ïóòè íå ñóùåñòâóåò, âûâåäèòå îäíî ÷èñëî -1. Ïðèìåð âõîäíîãî ôàéëà 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 4 5 Ïðèìåð âûõîäíîãî ôàéëà -1
Çàäà÷à 162 (Ñêà÷àòü àðõèâ)
Ïóòü  íåîðèåíòèðîâàííîì ãðàôå òðåáóåòñÿ íàéòè ìèíèìàëüíûé ïóòü ìåæäó äâóìÿ âåðøèíàìè. Âõîäíûå äàííûå Âî âõîäíîì ôàéëå çàïèñàíî ñíà÷àëà ÷èñëî N - êîëè÷åñòâî âåðøèí â ãðàôå (1˜N˜100). Çàòåì çàïèñàíà ìàòðèöà ñìåæíîñòè (0 îáîçíà÷àåò îòñóòñòâèå ðåáðà, 1 - íàëè÷èå ðåáðà). Çàòåì çàïèñàíû íîìåðà äâóõ âåðøèí - íà÷àëüíîé è êîíå÷íîé. Âûõîäíûå äàííûå  âûõîäíîé ôàéë âûâåäèòå ñíà÷àëà L - äëèíó ïóòè (êîëè÷åñòâî ðåáåð, êîòîðûå íóæíî ïðîéòè). À çàòåì âûâåäèòå L+1 ÷èñëî - âåðøèíû â ïîðÿäêå ñëåäîâàíèÿ âäîëü ýòîãî ïóòè. Åñëè ïóòè íå ñóùåñòâóåò, âûâåäèòå îäíî ÷èñëî -1. Ïðèìåð âõîäíîãî ôàéëà 5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 Ïðèìåð âûõîäíîãî ôàéëà 3 3 2 1 5
Êîììåíòàðèè.  ýòîé çàäà÷å íóæíî, ñíà÷àëà âû÷èñëèâ äëèíû ïóòåé äî âåðøèí, çàòåì "ðàñêðóòèòü" ïóòü (â îáðàòíîì íàïðàâëåíèè). Ýòà èäåÿ îáñóæäàåòñÿ ïåðåä òåì, êàê ðåøàòü çàäà÷ó.
Çàäà÷à 163 (Ñêà÷àòü àðõèâ)
×èñëà â âåðøèíàõ  íåîðèåíòèðîâàííîì ãðàôå áåç êðàòíûõ ðåáåð è ïåòåëü ðàññòàâèòü â âåðøèíàõ ÷èñëà òàê, ÷òîáû åñëè âåðøèíû ñîåäèíåíû ðåáðîì, òî ÷èñëà èìåëè îáùèé äåëèòåëü, à åñëè íåò - òî íåò. Âõîäíûå äàííûå.  ôàéëå INPUT.TXT çàïèñàíî ÷èñëî N (0<N<7) - êîëè÷åñòâî âåðøèí â ãðàôå. Çàòåì çàïèñàíà ìàòðèöà ñìåæíîñòè. Âûõîäíûå äàííûå.  ôàéë OUTPUT.TXT âûâåñòè N íàòóðàëüíûõ ÷èñåë èç äèàïàçîíà Longint, êîòîðûå âû ïðåäëàãàåòå ïðèïèñàòü âåðøèíàì. Ïðèìåð ôàéëà INPUT.TXT 3 0 1 1 1 0 0 1 0 0 Ïðèìåð ôàéëà OUTPUT.TXT 6 2 3
Êîììåíòàðèè. Çàäà÷à íà ñîîáðàçèòåëüíîñòü (ðåøåíèå ýòîé çàäà÷è îò âñåõ íå òðåáóåòñÿ). Âàðèàíòîâ ðåøåíèÿ, íàâåðíî, ìíîãî. Íàèáîëåå èçÿùíûé âûãëÿäèò òàê: ïðèïèøåì êàæäîìó ðåáðó ïðîñòîå ÷èñëî (êàæäîìó ñâîå). Òîãäà ïîñòàâèì â âåðøèíû ÷èñëà, ÿâëÿþùèåñÿ ïðîèçâåäåíèåì ÷èñåë, ïðèïèñàííûõ ðåáðàì, âûõîäÿùèì èç ýòîé âåðøèíû.
Çàäà÷à 164 (Ñêà÷àòü àðõèâ)
"Êîìïîíåíòû ñâÿçíîñòè"  íåîðèåíòèðîâàííîì ãðàôå ïîñ÷èòàòü êîëè÷åñòâî êîìïîíåíò ñâÿçíîñòè.  ãðàôå ìîãóò áûòü ïåòëè è êðàòíûå ðåáðà. Âõîäíûå äàííûå. Âî âõîäíîì ôàéëå INPUT.TXT çàïèñàíû ñíà÷àëà äâà ÷èñëà N è M, çàäàþùèå ñîîòâåòñòâåííî êîëè÷åñòâî âåðøèí è êîëè÷åñòâî ðåáåð (1˜N˜100, 0˜M˜10000), à çàòåì ïåðå÷èñëÿþòñÿ ðåáðà. Êàæäîå ðåáðî çàäàåòñÿ íîìåðàìè âåðøèí, êîòîðûå îíî ñîåäèíÿåò. Âûõîäíûå äàííûå.  âûõîäíîé ôàéë OUTPUT.TXT âûâåäèòå îäíî ÷èñëî - êîëè÷åñòâî êîìïîíåíò ñâÿçíîñòè. Ïðèìåð âõîäíîãî ôàéëà 3 4 1 1 1 2 1 3 2 3 Ïðèìåð âûõîäíîãî ôàéëà 1 Ïðèìåð âõîäíîãî ôàéëà 5 3 1 1 1 2 2 1 Ïðèìåð âûõîäíîãî ôàéëà 4 Ïðèìåð âõîäíîãî ôàéëà 5 0 Ïðèìåð âûõîäíîãî ôàéëà 5
Êîììåíòàðèè. Ðåøåíèå - òîæå âîëíà, ïîìå÷àþùàÿ êîìïîíåíòó ñâÿçíîñòè. Èäåÿ íå òàê ïðîñòà, êàê ìîæåò êàçàòüñÿ.
Êîììåíòàðèè. Çàêàí÷èâàåòñÿ âñå äâóìÿ çàíÿòèÿìè ïî òåìå "ïðîöåäóðû", íà êîòîðûõ øêîëüíèêàì ïðåäëàãàåòñÿ íàïèñàòü äîñòàòî÷íî áîëüøóþ èãðîâóþ ïðîãðàììó, â êîòîðîé èãðîê óïðàâëÿåò ÷åëîâå÷êîì, èùóùèì êëàä â ëàáèðèíòå. Ïðîãðàììà ïðîâåðÿåòñÿ âðó÷íóþ (ñîîòâåòñòâåííî, òåñòîâ ê íåé íåò). Áîëåå òîãî, ïðàâèëà èãðû ôîðìàëèçóþòñÿ êàæäûì øêîëüíèêîì ñàìîñòîÿòåëüíî (ïî ïðèíöèïó "ïðèäóìàé è íàïèøè èãðó ñàì").
Íàïèñàíèå áîëüøîé ïðîãðàììû íå ñëó÷àéíî - íà íåé ìîæíî ìàêñèìàëüíî íàãëÿäíî ïðîäåìîíñòðèðîâàòü êðàñîòó ðàçáèåíèÿ çàäà÷è íà ïîäçàäà÷è è ðåàëèçàöèþ êàæäîé èç ïîäçàäà÷ îòäåëüíîé ïðîöåäóðîé.
Âûáîð èãðîâîé çàäà÷è òàêæå íå ñëó÷àåí. Äåòè ê èãðàì íåðàâíîäóøíû, îäíàêî â òå÷åíèå öåëîãî ïîëóãîäèÿ ìû ñ íèìè ðåøàåì çàäà÷è, êîòîðûå äàëåêî íå âñåãäà ïîíÿòíî, êàêîå ïðàêòè÷åñêîå çíà÷åíèå èìåþò. È òóò øêîëüíèêàì ïðåäëàãàåòñÿ íàïèñàòü èãðó, è îíè âäðóã ñ óäèâëåíèåì ïîíèìàþò, ÷òî äëÿ ýòîãî èì ïîíàäîáèòñÿ òî, ÷åì ìû âñå ïîëóãîäèå çàíèìàëèñü.