М И Н И СТ Е РСТ В О О Б РА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Н Н ЫЙ У Н И В Е РСИ Т Е Т
О .Ф .У скова О .Д .Гор бенко А .И .Ш аш кин
О ЛИ М П И А Д Н ЫЕ ЗА Д А ЧИ П О П РО ГРА М М И РРО В А Н И Ю . ЛУ ЧШ И Е РЕ Ш Е Н И Я Часть1
У чебное издание
В О РО Н Е Ж - 2001
Б Б К 32.97 У Д К 681.3 О ли м п и ад н ы е зад ачи п о п рограм м и рован и ю и лу чш и е ре ш е н и я. Часть 1.: У че бн ое и зд ан и е / О .Ф.У скова, О .Д .Горбе н ко, А.И .Ш аш ки н – Ворон е ж: О О О ПФ «Д жу д и », 2001 – 76 с. Работа вы п олн е н а в рам ках Фе д е ральн ойце ле войп рограм м ы «И н те граци я» п о н ап равле н и ю «Воссозд ан и е сту д е н че ски х н ау чн ы хш коли оли м п и ад » (п рое ктР0054). И зд ае тся п ри фи н ан совойп од д е ржке О О О ПФ «Д жу д и ». Пе чатае тся п о ре ш е н и ю ре д акци он н о-и зд ате льского сове та факу льте та п ри клад н ой м ате м ати ки , и н форм ати ки и м е хан и ки Ворон е жского у н и ве рси те та. Ре це н зе н т - д октор фи зи ко-м ате м ати че ски х н ау к, п рофе ссор М .А.Арте м ов. Б Б К 32.97 У Д К 681.3 IABN 5-815-047-0
© Ворон е жски йу н и ве рси те т © Фе д е ральн ая це ле вая п рограм м а «И н те граци я» © О .Ф.У скова, О .Д .Горбе н ко, А.И .Ш аш ки н
О ГЛ АВЛ Е Н И Е Пре д и слови е . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. О бщ ая и н форм аци я о ш коле -оли м п и ад е . . . . . . . . . . .4 2. Зад ачи , п ре д лагавш и е ся н а оли м п и ад ахп о и н форм ати ке п рош лы хле т.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14 3. Зад ачи с ком м е н тари ям и и ре ш е н и ям и . . . . . . . . . . . . . . . . . . . .
П РЕ Д И СЛО В И Е И зд ание по д г о т о вле но в рам ках про е кт а Р 0054 Ц е лево й Ф е д е рально й
про г рам м ы
"И нт е г рация"
по
направле нию
"Во ссо зд ание ст уд е нч е ских науч ны х ш ко л и о лим пиад ". Оно о рие нт иро вано
в
о т кр ы т о й
ст уден ческо й
п р о гр ам м ир о ван ию м о же т
о сно вно м
на
уч аст нико в
р егио н ал ь н о й
ш ко л ы -о л им п иады
и ко м п ь ю т ер н о м у
м о дел ир о ван ию ,
по но
бы т ь т акже по ле зно ш ко льникам ст арш их классо в,
ст уд е нт ам и уч ит е лям инфо рм ат ики о бщ е о бразо ват е льны х и про фильны х уч е бны х заве д е ний. Организат о рам и ш ко лы -о лим пиад ы являют ся Во ро не жский г о суниверсит е т , Вы ч ислит е льны й Ц е нт р Ро ссийско й Акад е м ии Н аук (Р АН ) и Во ро не жский г о сударст ве нны й пед аго г ич е ский униве рсит е т . В пе рво й ч аст и рассм ат ривают ся зад ач и пред ш е ст во вавш их о лим пиад по инфо рм ат ике различ но го уро вня (факульт е т ских, вузо вских, м е жвузо вских, ре г ио нальны х, фе д е ральны х). Н е ко т о ры е задач и приве д е ны с ре ш е ниям и, в о сно вно м разрабо т анны м и ст уд е нт ам и факульт е т а приклад но й м ат е м ат ики и м е ханики Во ро не жско г о униве рсит е т а, ст авш им и в сво е вре м я призе рам и эт их о лим пиад . Во вт о ро й ч аст и, ко т о рая буд е т заве рш е нии ш ко лы -о лим пиад ы , буд ут
издана по
пре д ст авле ны м ат ериалы
эт о й ш ко лы , включ ающ ие задач иилуч ш ие ре ш е ния.
Во ро не жский университ ет , на базе ко т о ро го про во д ит ся ш ко ла-о лим пиад а, вы ражае т признат е льно ст ь ООО ПФ "Джуд и" (д ире кт о р А.В.Анд ре йч ико в), о казавш е м у се рье зную по д д е ржку в изданииэт о й книг и.
1. О Б Щ А Я И Н Ф О РМ А Ц И Я О Ш К О ЛЕ -О ЛИ М П И А Д Е П О ЛО Ж Е Н И Е оботкр ы той р егиональной сту денческой ш коле-олим п иаде п о п р огр амм ир ованию и ком п ью тер ном у моделир ованию О Б Щ И Е ПО Л О Ж Е Н И Я О ткры тая ре ги он альн ая сту д е н че ская ш кола-оли м п и ад а п о п рограм м и рован и ю и ком п ью те рн ом у м од е ли рован и ю п ровод и тся в рам ках Фе д е ральн ой це ле вой п рограм м ы "И н те граци я", н ап равле н и е 1.6 "Воссозд ан и е н ау чн ы х оли м п и ад , кон ку рсов, н ау чн ы х м олод ёжн ы х ш кол и кон фе ре н ци й", п рое кт Р0054. Головн ая орган и заци я п рое кта - Ворон е жски й госу д арстве н н ы й у н и ве рси те т. И сп олн и те ли : Вы чи сли те льн ы й це н тр РАН , Ворон е жски йгосу д арстве н н ы йп е д агоги че ски йу н и ве рси те т. Прое кт н ап равле н н а разви ти е творче ской акти вн ости сту д е н тов, ори е н таци ю у чащ е йся м олод е жи н а ре ш е н и е зад ач и н форм ати заци и н ау чн ы х и ссле д ован и й в сфе ре е сте стве н н ы х н ау к, а также н а вы явле н и е н аи боле е талан тли вы х сту д е н тов в области м од е ли рован и я • фи зи че ски х, •
хи м и че ски х,
•
би ологи че ски х,
•
э кологи че ски х,
•
ге ологи че ски х,
•
э кон ом и че ски х,
•
ге ографи че ски х
п роце ссов, п рое кти рован и я и разработки соотве тству ю щ и х п рограм м н ы хп род у ктов, и сп ользован и я се те вы хи м у льти м е д и йн ы хком п ью те рн ы хте хн ологи й, а также в области и н форм аци он н ого м од е ли рован и я в •
ли н гви сти ке ,
•
ю ри сп ру д е н ци и ,
•
и стори и ,
•
фи лософи и и п си хологи и .
М ате ри алы ш колы -оли м п и ад ы (н овости , сп и ски у частн и ков, зад ан и я ту ров, ре зу льтаты и д р.) бу д у т разм е щ аться н а стран и цах Web-сайта п о ад ре су www.main.vsu.ru/~pmmmo. ПО РЯ Д О К ПРО ВЕД Е Н И Я О ли м п и ад а п ровод и тся в н е сколько ту ров. Пе рвы й ту р п ровод и тся в те ле ком м у н и каци он н ом ре жи м е (17 се н тября 2001 год а), второй (осн овн ой) - н а лабораторн ой базе Ворон е жского у н и ве рси те та (октябрь 2001 год а). В ш коле - оли м п и ад е м огу т п ри н ять у части е сту д е н ты лю бы х ку рсов лю бы х ву зов Ц е н тральн о-Че рн озе м н ого ре ги он а. Всту п и те льн ы й взн ос д ля у части я в ш коле -оли м п и ад е н е тре бу е тся. В п робн ом и п е рвом ту ре м огу т п ри н ять у части е все же лаю щ и е . К у части ю в осн овн ом ту ре бу д у т д оп у щ е н ы 20 и н огород н и х и 30 м е стн ы х у частн и ков, п оказавш и е лу чш и е ре зу льтаты в п е рвом ту ре . Ре ш е н и е о д оп у ске к у части ю во втором ту ре п ри н и м ае тся оргком и те том оли м п и ад ы . И н огород н и е у частн и ки осн овн ого ту ра разм е щ аю тся в общ е жи ти и (гости н и це ) и обе сп е чи ваю тся п и тан и е м бе сп латн о.
У частн и ки оли м п и ад ы п рослу ш аю т ле кци и ве д у щ и х у че н ы х п о совре м е н н ы м п робле м ам н ау ки и п ри м у т у части е в работе кру глого стола "К ом п ью те рн ы е те хн ологи и в образован и и ". Точн ая д ата п рове д е н и я второго ту ра ш колы -оли м п и ад ы оп ре д е ляе тся оргком и те том и оглаш ае тся че ре з С М И и в И н те рн е те . ПО Д ВЕД Е Н И Е И ТО ГО В И Н АГРАЖ Д Е Н И Е ПО Б ЕД И ТЕЛ Е Й Под ве д е н и е и тогов откры той ре ги он альн ой сту д е н че ской ш колы - оли м п и ад ы п о п рограм м и рован и ю и ком п ью те рн ом у м од е ли рован и ю п ровод и тся оргком и те том оли м п и ад ы . О ри ги н альн ы е ре ш е н и я бу д у т оп у бли кован ы в сборн и ке "О ли м п и ад н ы е зад ачи . Л у чш и е ре ш е н и я". Побе д и те ли оли м п и ад ы н агражд аю тся грам отам и и п ри зам и . С п и сок п ри зе ров оли м п и ад ы , зан явш и х 1-10 м е ста, п е ре д ае тся в ву зы ре ги он а, а также разм е щ ае тся на Web-сайте www.main.vsu.ru/~pmmmo . Н аш и ре кви зи ты : 394693 Ворон е ж, У н и ве рси те тская п л., 1. К афе д ра м ате м ати че ского обе сп е че н и я Э ВМ факу льте та п ри клад н ойм ате м ати ки , и н форм ати ки и м е хан и ки (ау д .8). О ргком и те тш колы -оли м п и ад ы п о п рограм м и рован и ю и ком п ью те рн ом у м од е ли рован и ю . E-mail:
[email protected] URL: www.main.vsu.ru/~pmmmo Те ле фон ы : (0732) 789-698, 789-266
О ргком и те т откры тойре ги он альн ойсту д е н че скойш колы -оли м п и ад ы п о п рограм м и рован и ю и ком п ью те рн ом у м од е ли рован и ю (Фе д е ральн ая це ле вая п рограм м а "И н те граци я", разд е л1.6, п рое ктР0054) Пре д се д ате ль оргком и те та -
ЗАПРЯ ГАЕ В С е рге йАле ксан д рови ч, Пе рвы й п роре ктор Ворон е жского госу н и ве рси те та, д октор фи зи ко-м ате м ати че ски хн ау к, п рофе ссор
Зам . Ш АШ К И Н Але ксан д р И ван ови ч, д е кан факу льте та п ре д се д ате ля - ПМ М , д октор фи зи ко-м ате м ати че ски хн ау к, п рофе ссор. Чле н ы оргком и те та:
М И Х АЙ Л О В Гу ри йМ и хайлови ч, зам . д и ре ктора Вы чи сли те льн ого це н тра РАН , кан д и д атфи зи ком ате м ати че ски хн ау к, г.М осква Ш АК И Н Все волод Влад и м и рови ч, зав. се ктором Вы чи сли те льн ого це н тра РАН , кан д и д атфи зи ком ате м ати че ски хн ау к, г.М осква С У РО ВЦ Е В И горьС те п ан ови ч, н ачальн и к у п равле н и я п рофе сси он альн ого образован и я и н ау ки Главн ого у п равле н и я образован и я ад м и н и страци и Ворон е жскойобласти , д октор те хн и че ски хн ау к, п рофе ссор У С К О ВА О льга Фе д оровн а, д оце н ткафе д ры м ате м ати че ского обе сп е че н и я Э ВМ ВГУ , кан д и д ат те хн и че ски хн ау к, коорд и н атор п рое кта ГО РБ Е Н К О О ле г Д ан и лови ч, зав.кафе д рой м ате м ати че ского обе сп е че н и я Э ВМ ВГУ , кан д и д ат фи зи ко-м ате м ати че ски хн ау к ПО ТАПО В Але ксан д р С е рге е ви ч, п роре ктор
Ворон е жского госп е д у н и ве рси те та, п рофе ссор АН ТИ ПО В С е рге йАн атолье ви ч, ре ктор Ворон е жского областн ого и н сти ту та п овы ш е н и я квали фи каци и и п е ре п од готовки работн и ков образован и я, д октор фи зи ко-м ате м ати че ски хн ау к, п рофе ссор ПАН Ю Ш К И Н Вале н ти н Ан атолье ви ч, д е кан ю ри д и че ского факу льте та ВГУ , д октор ю ри д и че ски хн ау к, п рофе ссор К О С ТИ Н Влад и м и р Але ксе е ви ч, д е кан м ате м ати че ского факу льте та ВГУ , д октор фи зи ком ате м ати че ски хн ау к, п рофе ссор К АЗАК О В Ви тали йГри горье ви ч, д и ре ктор С тарооскольского фи ли ала ВГУ , кан д и д ат п е д агоги че ски хн ау к Л АПЫ ГИ Н Д м и три йРу д ольфови ч, зам . ге н е ральн ого д и ре ктора ЗАО "РЕТ", г.Ворон е ж Б АШ К И Н Ви ктор Н ау м ови ч, п ре д се д ате льС ове та д и ре кторов ЗАО Торговы йд ом "Фи н и ст", г.Ворон е ж ПЕРЕЛ Ы ГИ Н А Зоя Н е сте ровн а, зав. лаборатори е й вы чи сли те льн ойте хн и ки ВГУ ЧЕРН Ы Х Н и н а Пе тровн а, кан д и д атфи зи ком ате м ати че ски хн ау к, ру ковод и те льре ги он альн ого це н тра фи рм ы «М и рра-Л ю кс» К РАС Н ЕР И лья Н ау м ови ч, д и ре ктор Ц е н тра п равовойи н форм ати ки М и н и сте рства ю сти ци и РФ п о Ворон е жскойобласти С е кре тари атоли м п и ад ы
К РО ВЯ К О ВА Вале н ти н а Але ксе е вн а, лаборан ткафе д ры ММИ О ТЮ Н И Н А Л и д и я Н и колае вн а, и н же н е р Л ВТ М Е Н Ь Ш И К О ВА О льга И ван овн а, се кре тарьд е кан ата факу льте та ПМ М С ту д е н че ски йд и ре кторат Я К У Б Е Н К О Ад ре й, сту д . 5 ку рса факу льте та ПМ М ВАХ ТИ Н Але ксе й, м аги стран т2 год а обу че н и я ПО Л Я К О В Ан д ре й, м аги стран т1 год а обу че н и я ЕФРЕ М О В М акси м , м аги стран т1 год а обу че н и я М Х И ТАРЯ Н Л у си н е , сту д . 5 ку рса факу льте та ПМ М РО М АЩ Е Н К О Але ксе й, сту д е н т5 ку рса факу льте та ПМ М
Ж ю ри откры тойре ги он альн ойсту д е н че скойш колы -оли м п и ад ы п о п рограм м и рован и ю и ком п ью те рн ом у м од е ли рован и ю Пре д се д ате ль жю ри -
ГО РБ Е Н К О О ле г Д ан и лови ч, зав. кафе д рой м ате м ати че ского обе сп е че н и я Э ВМ ВГУ , кан д и д атфи зи ко-м ате м ати че ски хн ау к
Зам .п ре д се д ате ля - У С К О ВА О льга Фе д оровн а, д оце н ткафе д ры м ате м ати че ского обе сп е че н и я Э ВМ ВГУ , кан д и д атте хн и че ски хн ау к Чле н ы жю ри :
М И Л О ВС К АЯ Л ю д м и ла С е рафи м овн а, д оце н т кафе д ры и н форм ати ки ВГПУ , кан д и д ат
фи зи ко-м ате м ати че ски хн ау к К У Л АПИ Н Л е он и д Ге н ри хови ч, д и ре ктор це н тра И Н ТЕРН Е Т, кан д и д атфи зи ком ате м ати че ски хн ау к ВО РО Н И Н А И ри н а Евге н ье вн а, зам . д и ре ктора н ау чн о-м е тод и че ского це н тра п о ком п ью те рн ойли н гви сти ке , кан д и д ат те хн и че ски хн ау к, д оце н т М ЕЛ Ь Н И К О В Вад и м М и трофан ови ч, п ре п од авате лькафе д ры м ате м ати че ского обе сп е че н и я Э ВМ ; С ЕЛ ЕЗ Н Е В К он стан ти н Егорови ч, п ре п од авате лькафе д ры м ате м ати че ского обе сп е че н и я Э ВМ ; АЗ Н АУ РЬ Я Н Ц Але ксан д р Влад и м и рови ч, ге н е ральн ы йд и ре ктор Ц е н тральн оЧе рн озе м н ого п ре д стави те льства корп ораци и "ПАРУ С ", г.Ворон е ж
С п он соры откры тойре ги он альн ойсту д е н че скойш колы оли м п и ад ы п о п рограм м и рован и ю и ком п ью те рн ом у м од е ли рован и ю Ад м и н и страци я Ворон е жскойобласти
Ц е н тральн о-Че рн озе м н ое п ре д стави те льство корп ораци и "ПАРУ С ", г.Ворон е ж ЗАО "РЕТ", г.Ворон е ж Завод ке рам и че ски хи зд е ли й, г.Ворон е ж Торговы йд ом "Фи н и ст", г.Ворон е ж К осм е ти че ская фи рм а NINELLE, И сп ан и я ЗАО "РЕЛ Э К С ", г.Ворон е ж С п е цгорм олзавод "Л и ски н ски й", г.Л и ски , Ворон е жскойобласти ЗАО Н Э К С , г.Ворон е ж Фон д С .Г.К ре йн а АО О “М аслосы рзавод ”, с.Ве рхн и йМ ам он Ворон е жскойобласти О скольски йэ ле ктро-м е таллу рги че ски йком би н атБ е лгород ской области Фи ли алГу та-бан ка в г.С т.О сколБ е лгород скойобласти Росси йская Ассоци аци я "Ж е н щ и н ы в н ау ке и образован и и " Росси йская Ассоци аци я "Ж е н щ и н ы -м ате м ати ки "
К он д и те рская фабри ка "С лавян ка" г. С т. О сколБ е лгород ской области (Д и ре ктор С .А.Гу се в) Ре ги он альн ы йце н тр фи рм ы «М и рра-Л ю кс» ЗАО "К е д р+" , г.Ворон е ж. (Д и ре ктор Ю .П.Л и строва, кан д . фи зи ком ате м ати че ски хн ау к, д оце н т) О О О ПФ "Д жу д и " (Д и ре ктор А.В.Ан д ре йчи ков)
Управле ние про фе ссио нально го о бразо вания инаукиГлавно г о управле ния о бразо вания ад м инист рацииВо ро не жско й о бласт и уч ре д ило призы д ля ст уд е нт о в – уч аст нико в ш ко лы -о лим пиады – из м ало о бе спе ч е нны х се м е й. С е м ья Н .Я .К расне ра уч ре дила приз пам ят иН аум а Я ко влевич а (1924 – 1999) д ля уч аст ника ш ко лы -о лим пиады , по казавш е г о луч ш ие ре зульт ат ы в разд е ле эко но м ика иэко но м ич е ская киберне т ика по ит о гам вт о ро го т ура. Н .Я .К расне р – о д иниз ве д ущ их о рг анизат о ро в наукина факульт е т е П М М , вид ны й уч е ны й в о бласт иприм е не ния м ат е м ат ич е ских м е т о д о в в эко но м ике , о рг анизат о р кафе дры м ат е м ат ич е ских м е т о до в иссле д о вания о пераций. Р е г ио нальны й це нт р фирм ы «М ирра-Л юкс» уч ред ил призы уч аст ницам ш ко лы -о лим пиады за луч ш ий ко м пьют е рны й дизайн ре ализациизад ания пе рво г о т ура. Управле ние про фе ссио нально го о бразо вания инаукиГлавно г о управле ния о бразо вания ад м инист рацииВо ро не жско й о бласт и уч ре д ило призы д ля ст уд е нт о в– инвалид о в - уч аст нико в пе рво го и вт о ро го т уро в ш ко лы -о лим пиады .
Ф ирм а «Р Е Т» уч ре дила призы д ля ст уд е нт о в - по бед ит е лей ш ко лы -о лим пиад ы - спе циализирующ ихся в о бласт иприклад но й м ат ем ат икииинфо рм ат ики. Ц е нт р право во й инфо рм ат икиМ инист е рст ва юст ицииР Ф по Во ро не жско й о бласт иуч ре дил приз д ля уч аст ника ш ко лы о лим пиады , по казавш е г о луч ш ие ре зульт ат ы в разд е ле юриспруд е нция по ит о гам вт о ро го т ура. Р е кт о рат Во ро не жско го го суниве рсит е т а планируе т вы д е лит ь бе сплат ны е пут евкид ля о т д ы ха на т урбазах Ро ссии, а т акже санат о рно -куро рт ны е пут евкиво сьм ист уд е нт ам Во ро не жско г о униве рсит е т а, по казавш им наилуч ш ие ре зульт ат ы в о лим пиад е . Р е кт о рат Во ро не жско го го суниве рсит е т а планируе т вы д е лит ь бе сплат ны е пут евкид ля санат о рно -куро рт но г о ле ч е ния все м ст уд е нт ам -инвалидам Во ро не жско го униве рсит е т а – уч аст никам ш ко лы -о лим пиад ы ипо о щ рит ьих д е не жны м во знаг ражд е ние м . К о нд ит ерская фабрика «С лавянка» (г . С т ары й Оско л Б е лг о ро д ско й о бласт и) планируе т по о щ рит ьуч аст нико в перво го т ура из г . С т ары й Оско л, по казавш их хо ро ш ие ре зульт ат ы в о лим пиад е. Ассо циация «Ж е нщ ины в науке ио бразо вании» вы д е лила приз уч аст никупе рво г о т ура, пе рвы м приславш е м управильно е ре ш е ние заданий пе рво го т ура не зависим о о т но м инации. Ассо циация «Ж е нщ ины - м ат е м ат ики» вы д е лила приз уч аст нице пе рво г о т ура, пре д ст авивш е й о ригинально е ре ш е ние зад аний пе рво г о т ура не зависим о о т но м инации. Ф о нд про фе ссо ра С .Г.К ре йна вы д е лил приз уч аст никупе рво г о т ура, по казавш е м унаилуч ш ие ре зульт ат ы в разд е ле м ат ем ат ика.
С пе цго рм о лзаво д "Л искинский" ( г .Л иски, Во ро не жско й о бласт и) планируе т по о щ рит ьуч аст нико в перво го т ура из г .Л иски, по казавш им хо ро ш ие ре зульт ат ы . АОО “ М асло сы рзаво д ” ( с.Ве рхний М ам о нВо ро не жско й о бласт и) планируе т по о щ рит ьуч аст нико в перво го т ура из с.Ве рхний М ам о н, по казавш им хо ро ш ие ре зульт ат ы . ЗАО Н Э К С ( г .Во ро не ж) планируе т по о щ рит ьуч аст нико в вт о ро го т ура, по казавш их хо ро ш ие ре зульт ат ы в не м ат е м ат ич е ских разд е лах. ЗАО "К е д р+" планируе т по о щ рит ьд е кана факульт е т а любо го вуза, ст уд е нт ы ко т о ро го принялинаибо ле е акт ивно е уч аст ие в ш ко ле -о лим пиад е . Во ро не жский го суниве рсит е т уч ре дил призы ст уд е нт ам , по казавш им хо ро ш ие ре зульт ат ы в о лим пиад е - г е о ло гич е ский факульт ет : по направле нию г е о ло гия иг е о физика; - физич е ский факульт е т : по направле нию физико м ат ем ат ич е ские науки; - факульт е т ко м пьют е рны х наук: по направле нию ко м пьют е рны е науки; - м ат ем ат ич е ский факульт е т : по направле нию м ат ем ат ика; - био ло го -по ч ве нны й факульт е т : по направле ниям био ло гия ипо ч во ве д е ние ; - хим ич е ский факульт е т : по направле ниям хим ия и м е д ицина; - юридич е ский факульт е т : по направле нию юриспруд е нция; - факульт е т ро м ано -г ерм анско й фило ло гии: по направле нию ко м пьют е рная лингвист ика; - ист о рич е ский факульт е т : по направле нию ист о рич е ская инфо рм ат ика; - фило ло гич е ский факульт е т : по направле нию
-
г ум анит арны е науки; факульт е т фило со фииипсихо ло г ии: по направле ниям фило со фия ипсихо ло г ия; эко но м ич е ский факульт е т : по направле нию эко но м ика; факульт е т приклад но й м ат е м ат икиим е ханики: по направле ниям про г рам м иро вание и ко м пьют е рно е м о д е лиро вание .
Р е кт о рат Во ро не жско го г о сударст ве нно г о пед аго г ич е ско го униве рсит е т а планируе т по о щрит ь ст уд е нт о в пе риферийны х пе д аго г ич е ских вузо в (М ич уринско г о , Б о рисо г ле бско г о , Е ле цко го ), по казавш их хо ро ш ие ре зульт ат ы в о лим пиад е. П риг лаш аем к со т руд нич е ст вулюбы е пред прият ия любы х фо рм со бст ве нно ст и. Р е клам а о Ваш е м пре д прият иибуд е т разм е щ е на на ст раницах о лим пиад но г о сайт а www.main.vsu.ru/~pmmmo, а т акже на ст раницах пе ч ат и Б ан ковски е ре кви зи ты : ВГУ И Н Н 3666029505 Р/с 40503810313002000067 Ц е н тральн о-Че рн озе м н ы йбан к С бе рбан ка РФ г.Ворон е жа Б И К 042007681 к/с 3010181060000000068 К од О К ПО 02068120 К од О К О Н Х 92110 В п лате жн ом п ору че н и и у казать Н И Ч-1069 (У скова О .Ф.)
И н форм аци он н ая п од д е ржка откры тойре ги он альн ой сту д е н че скойш колы -оли м п и ад ы п о п рограм м и рован и ю и ком п ью те рн ом у м од е ли рован и ю
"Газе та с у ли цы Л и зю кова" Газе та "М олод ойком м у н ар" Газе та "Ворон е жски йу н и ве рси те т" Газе та "К ом п ью те рн ое чти во" Газе та «Факу льте тПМ М » О О О ПФ "Д жу д и "
2. ЗА Д А ЧИ П О И Н Ф О РМ А Т И К Е , П РЕ Д ЛА ГА В Ш И Е СЯ Н А О ЛИ М П И А Д А Х П РО Ш ЛЫХ ЛЕ Т С ле д ующ ая г руппа задач пре д лагалась на униве рсит е т ско й о лим пиад е ст уд е нт о в по инфо рм ат ике в 1997 го д у. Задача1. "Т елеф онная связь" Посе лок состои ти з N д ом ов, расп оложе н н ы хвд ольп рям ой д ороги с од н ой сторон ы н а равн ы х расстоян и ях. Д ом а п рон у м е рован ы п осле д овате льн о: 1, 2, 3,..., N. В п осе лке п ровод ят те ле фон н у ю связь. В табли це Т у казан о, сколько те ле фон н ы х ап п аратов н ад о у стан ови ть в кажд ом д ом е . Расстоян и е м е жд у д ву м я сосе д н и м и д ом ам и счи тае тся равн ы м е д и н и це . Зад ан и е .
С озд ать п рограм м у д ля оп ре д е ле н и я н ом е ра д ом а, в котором н ад о у стан ови ть АТС , чтобы су м м арн ое расстоян и е от АТС д о все хте ле фон н ы хап п аратов бы ло м и н и м альн ы м . Если таки хд ом ов н е сколько, д остаточн о н айти лю бой. К ажд ы йте ле фон связан с АТС отд е льн ы м п ровод ом . (Под расстоян и е м д о те ле фон н ого ап п арата п од разу м е вае тся расстоян и е д о д ом а, в котором бу д е т у стан овле н ап п арат. Расстоян и е от АТС д о те ле фон н ого ап п арата, у стан овле н н ого в д ом е , гд е стои тАТС , счи тае тся равн ы м н у лю .) Те хн и че ски е тре бован и я. Вход н ы е д ан н ы е бе ру тся и з те кстового файла input1.txt, п е рвая строка которого сод е ржи тчи сло д ом ов, вторая - ли н е йн у ю табли цу Т. И сход н ы е д ан н ы е корре ктн ы , и хп рове рка н е тре бу е тся. Вы ход н ы е д ан н ы е - н ом е р д ом а, гд е н у жн о п остави ть АТС , и су м м арн ое расстоян и е д о все х те ле фон н ы х ап п аратов - вы вод ятся н а э кран . При м е р вход н ы хд ан н ы х 6 103113
При м е р вы ход н ы хд ан н ы х АТС - в д ом е 4 С у м м арн ое расстоян и е - 13
Задача2. " Ф у нкц ия" Ц е лое п оложи те льн ое чи сло М зап и сы вае тся в д вои чн ой си сте м е счи сле н и я, зате м разряд ы п е ре ставляю тся в обратн ом п оряд ке . Полу чи вш е е ся чи сло п ри н и м ае тся за зн аче н и е фу н кци и В(М ). Зад ан и е . С озд ать п рограм м у д ля вы вод а в те кстовы йфайл OUT.TXT зн аче н и йфу н кци и В(М ) н а отре зке [512,1023]. Задача3. "Считалка" Вокру г счи таю щ е го стоятN че лове к, од и н и з которы х н азван п е рвы м , а остальн ы е зан у м е рован ы п о часовойстре лке чи слам и от 2 д о N. С чи таю щ и йве д е тсче тд о М , н ачи н ая с п е рвого. Че лове к, н а котором остан ови лся сче т, вы ход и т и з кру га. С че т вн овь н ачи н ае тся со сле д у ю щ е го за вы бы вш и м че лове ка (п ри э том
вы бы вш и е и з кру га н е счи таю тся) и так д о те х п ор, п ока н е остан е тся од и н че лове к. Зад ан и е . О п ре д е ли тьн ачальн ы йн ом е р оставш е гося че лове ка. Те хн и че ски е тре бован и я . Вход н ы м и д ан н ы м и являю тся чи сла N и M, которы е ввод ятся с клави ату ры . Ре зу льтат - н ом е р оставш е гося че лове ка – вы вод и тся н а э кран . При м е р вход н ы хд ан н ы х 5 3
При м е р вы ход н ы хд ан н ы х Н ом е р оставш е гося - 4
С ле д у ю щ и е зад ачи п ре д лагали сь н а город ской сту д е н че ской оли м п и ад е п о и н форм ати ке в 1997 год у . Задача4. "М ногоу гольник" Вы п у клы й м н огоу гольн и к на п лоскости зад ан це лочи сле н н ы м и коорд и н атам и свои х ве рш и н . Тре бу е тся п од счи тать коли че ство точе к с це лочи сле н н ы м и коорд и н атам и , ле жащ и хн а гран и це м н огоу гольн и ка. Зад ан и е . С озд ать п рограм м у д ля вы чи сле н и я тре бу е м ого коли че ства точе к (д ля кажд ого и з д ву ху казан н ы хслу чае в). Те хн и че ски е тре бован и я . Вход н ы м и д ан н ы м и являю тся чи сло ве рш и н м н огоу гольн и ка и и х коорд и н аты в п оряд ке обход а п о часовой стре лке . К оорд и н аты ве рш и н - це лы е чи сла и п о м од у лю н е п ре восход ят 1000000. Вход н ы е д ан н ы е бе ру тся и з те кстового файла INPUT4.TXT, в п е рвой строке которого у казы вае тся чи сло ве рш и н м н огоу гольн и ка, в кажд ой сле д у ю щ е й строке - п ара коорд и н ат. Ре зу льтаты вы вод ятся н а э кран . И сход н ы е д ан н ы е корре ктн ы , и хп рове рка н е тре бу е тся. При м е р вход н ы хд ан н ы х 4 -10 -10
Вы ход н ы е д ан н ы е 80
-10 10 10 10 10 -10 Задача5. « М етеостанц ии» Н а Ю жн ом п олю се расп оложе н ы N п рон у м е рован н ы х м е те oрологи че ски х стан ци й. К ажд ая стан ци я сое д и н е н а с д ру ги м и стан ци ям и ли н и ям и связи . В ре зу льтате сти хи йн ого бе д стви я н е которы е ли н и и связи оказали сь н ару ш е н н ы м и . И сп равн ость ли н и и связи м е жд у I-той и K-той стан ци ям и оп ре д е ляе тся и з це лочи сле н н ой табли цы NET: э ле м е н т с и н д е ксам и (I,K) раве н 1, е сли связь м е жд у I-тойи K-тойстан ци ям и н е н ару ш е н а, и 0 - в п роти вн ом слу чае . Тре бу е тся оп ре д е ли ть, м е жд у каки м и п арам и стан ци й связь н е возм ожн а д аже че ре з це п очки д ру ги хстан ци й. Зад ан и е . С озд ать п рограм м у д ля оп ре д е ле н и я п ар стан ци й, которы м н е возм ожн о у стан ови тьсвязь.
м е жд у
Те хн и че ски е тре бован и я. Вход н ы м и д ан н ы м и являю тся чи сло стан ци й N и це лочи сле н н ая табли ца NET разм е ром NxN. Вход н ы е д ан н ы е бе ру тся и з те кстового файла INPUT5.TXT, в п е рвойстроке которого у казы вае тся чи сло стан ци й, в кажд ой сле д у ю щ е йстроке - оче ре д н ая строка табли цы . Ре зу льтаты - п ары н ом е ров стан ци й- вы вод ятся п острочн о н а э кран . И сход н ы е д ан н ы е корре ктн ы , и хп рове рка н е тре бу е тся. При м е р вход н ы хд ан н ы х 4 1101 1100 0010 1001
Вы ход н ы е д ан н ы е 13 23 34
Задача6. « Скобки» Д ан о ари фм е ти че ское вы раже н и е , состоящ е е и з бу кв, од н озн ачн ы х чи се л, зн аков ари фм е ти че ски х оп е раци й и скобок, зап и сан н ое в общ е п ри н ятой форм е . Тре бу е тся у д али ть и з вы раже н и я ли ш н и е п ары скобок (то е сть п ары , н е вли яю щ и е н а п оряд ок вы п олн е н и я оп е раци й). Зад ан и е . С озд ать п рограм м у д ля у д але н и я и з зад ан н ого вы раже н и я ли ш н и хп ар скобок. Те хн и че ски е тре бован и я. И сход н ая строка с вы раже н и е м ввод и тся с клави ату ры . Ре зу льтат- у п рощ е н н ое вы раже н и е - вы вод и тся н а э кран . При м е р вход н ы хд ан н ы х ((6/2)*А+(8-5))/(E)
Вы ход н ы е д ан н ы е (6/2*A+8-5)/E
Задача7. « К р ип тогр амм а» Те кст закод и рован с п ом ощ ью се тки , п ре д ставле н н ой н а ри су н ке , гд е ци фрой 0 обозн аче н о отве рсти е . Д ля того, чтобы раскод и ровать сообщ е н и е (кри п тограм м у ), н у жн о н аложи ть се тку н а те кст так, чтобы в отве рсти я м ожн о бы ло ви д е ть си м волы закод и рован н ого те кста. Пе рвы й раз се тка н аклад ы вае тся так, чтобы сторон а, отм е че н н ая зн аком "+", бы ла ве рхн е й, зате м се тка п оворачи вае тся п о часовой стре лке н а 90 град у сов, чи тае тся сле д у ю щ и йн абор си м волов, и т.д . д о п олн ого оборота се тки н а 360 град у сов. + 101010 111101 110111 101101
111110 111011 Зад ан и е . С озд ать п рограм м у д ля ввод а закод и рован н ого те кста п о строкам и расш и фровки е го с п ом ощ ью д ан н ойсе тки . Те хн и че ски е тре бован и я. И сход н ы е д ан н ы е - те кст и се тка - зад аю тся в ви д е квад ратн ы х табли ц в те кстовы х файлах inp1.txt и inp2.txt, кажд ая строка табли цы разм е щ ае тся в отд е льн ойстроке файла. Ре зу льтат вы вод и тся н а э кран . При м е р и сход н ы хд ан н ы х ж бв у н р и ы н е яе к хм б р р о г у р лк ти р я о о се н ю е т
Вы ход н ы е д ан н ы е
бу рям глою н е бокрое тви хри сн е жн ы е кру тя
101010 111101 110111 101101 111110 111011 Задача8. « Зоны » Д ву м е рн ая табли ца Р[1:M,1:N] зап олн е н а н у лям и и е д и н и цам и . Ц е п очкой бу д е м н азы вать п осле д овате льн ость е д и н и чн ы х э ле м е н тов табли цы , в которой п осле д овате льн о расп оложе н н ы е п ары э ле м е н тов табли цы являю тся сосе д н и м и п о гори зон тали , ве рти кали и ли д и агон али . С м ы каясь кон цам и д ру г с д ру гом и с краям и табли цы , це п очки д е лят табли цу н а "зон ы ",
зап олн е н н ы е н у лям и . С вои м и и н д е ксам и P и Q зад ае тся э ле м е н т табли цы . Тре бу е тся зап олн и ть е д и н и цам и зон у табли цы , в котором н аход и тся зад ан н ы й э ле м е н т. Если зад ан н ы йэ ле м е н т окаже тся е д и н и чн ы м , то табли ца н е п ре образу е тся. Зад ан и е . С озд ать п рограм м у д ля п олу че н и я табли цы (и з зад ан н ой), в которойзон а с зад ан н ы м э ле м е н том зап олн е н а е д и н и цам и , е сли зад ан н ы йэ ле м е н т- н у ле вой. Те хн и че ски е тре бован и я. Вход н ы м и д ан н ы м и являю тся чи сло строк М и столбцов N табли цы , зн аче н и я э ле м е н тов табли цы и и н д е ксы зад авае м ого э ле м е н та. Вход н ы е д ан н ы е бе ру тся и з те кстового файла INP5.TXT, в п е рвой строке которого у казы вае тся чи сла M и N стан ци й, в кажд ой сле д у ю щ е й строке - оче ре д н ая строка табли цы , в п осле д н е йстроке файла - чи сла P и Q. Ре зу льтат- н овая табли ца - вы вод и тся н а э кран . При м е р вход н ы хд ан н ы х 12 12 000000000000 011000000000 010111110000 010000001000 010011000100 010101000010 010011011110 010000010000 010010011000 010101001000 011000110000 000000000000 5 8 Задача9. « Листбу м аги»
Вы ход н ы е д ан н ы е : 000000000000 011000000000 011111110000 011111111000 011111111100 011101111110 011111111110 011111110000 011111111000 011101111000 011000110000 000000000000
И м е е тся п рям оу гольн ы йли стбу м аги , д ли н а которого равн а N сан ти м е тров, а ш и ри н а M сан ти м е тров. С ли стом м ожн о п рои звод и ть сле д у ю щ и е оп е раци и : сги бать ли ст вд вое , cовм е щ ая п роти воп оложн ы е сторон ы ли ста; сги бать ли ст совм е щ ая од н у строн у с п аралле льн ойе йли н и е й сги ба; разги бать ли ст, п ри э том оставляя н а н е м ли н и ю сги ба. Н ап и сать п рограм м у , которая оп ре д е ляе т: м ожн о ли е го све рн у ть так, чтобы п олу чи лся п рям оу гольн и к д ли н ойP сан ти м е тров и ш и ри н ойQ сан ти м е тров. В слу чае у тве рд и те льн ого отве та п рограм м а д олжн а вы д авать м и н и м альн ое коли че ство оп е раци й с ли стом , н е обход и м ы х д ля э того. Т ех нические тр ебования: Вход н ойфайл: INPUТ.ТХ Т Вы ход н ойфайл: О UTPUТ.ТХ Т О гран и че н и е вре м е н и : 5 се ку н д Ф ор м атвх одны х данны х : В п е рвой строке вход н ого файла сод е ржаться ве щ е стве н н ы е чи сла N,M,P и Q в ви д е д е сяти чн ы хд робе й. Ф ор м атвы х одны х данны х : Если ли ст све рн у ть м ожн о, то п е рвая строка те кста д олжн а сод е ржать строка д олжн а сод е ржать YES и м и н и м альн ое чи сло оп е раци й, н е обход и м ы х д ля э того. В п роти вн ом слу чае , п е рвая строка те кста д олжн а сод е ржатьслово NO. П р им ер ф ай лов вх одны х и вы х одны х данны х : INPUT.TXT OUTPUT.TXT
1 2 1 0.75
YES 4
Задача10. « Системасчисления» М н оже ство си м волов I-ри чн ой си сте м ы и счи сле н и я(2<=I<=36) образу ю тси м волы 0,… ,9,A,B,… ,Z. Е сли I<36, то соотве тству ю щ е е коли че ство п осле д н и х бу кв лати н ского алфави та в каче стве ци фр н е и сп ользу ю тся. Если I<10, то н е и сп ользу ю тся соотве тству ю щ и е ци фры . Н е обход и м о н ап и сать п рограм м у , которая п о д ву м те кстовы м строкам , озн ачаю щ и м од н о и тоже чи сло в I-ри чн ойи Jри чн ойси сте м е и счи сле н и я, оп ре д е ляе тм и н и м альн ы е зн аче н и я I и J. Т ех нические тр ебования: Вход н ойфайл: INPUТ.ТХ Т Вы ход н ойфайл: О UTPUТ.ТХ Т О гран и че н и е вре м е н и : 10 се ку н д Ф ор м атвх одны х данны х : Во вход н ом файле хран ятся д ве строки си м волов, озн ачаю щ и х п е рвое и второе чи сла. Д ли н а строки н е боле е 40 си м волов. Ф ор м атвы х одны х данны х : В вы ход н ом файле в те кстовом ви д е д олжн ы сод е ржаться п ары чи се лI и J и ли слово NO, е сли зад ан н ы е чи сла н е равн ы н и в каки х и з у казан н ы х ( 2<=I<=36 и 2<=J<=36) си сте м ах и счи сле н и я.. П р имер ф ай лов вх одны х и вы х одны х данны х : INPUT.TXT OUTPUT.TXT 10 23
2 Задача11. « Э лектр ическая ц еп ь» В э ле ктри че ску ю це п ь вклю че н о N у стройств. У стройство с н ом е ром I ре аги ру е тн а п осту п аю щ и е в се тьси гн алы оп ре д е ле н н ой частоты (частота – н е отри цате льн ое ве щ е стве н н ое чи сло), п ри че м сам о тоже ге н е ри ру е т си гн алы и п осы лае т и х в це п ь. Д ля кажд ого у стройства зад ан д и ап азон частотси гн алов (A(I),B(I)) (A(I) и B(I) – н е отри цате льн ы е ве щ е стве н н ы е чи сла, п ри че м A(I)
че тве рки ве щ е стве н н ы х чи се л A(I), B(I), C(I), D(I) в ви д е д е сяти чн ы х д робе й. К ажд ая че тве рка зан и м ае т отд е льн у ю строку файла. Ф ор м атвы х одны х данны х : В вы ход н ом файле у казы ваю тся п ары ве щ е стве н н ы х чи се л – н ачала и кон цы д и ап азон ов частотси гн алов, п ри п од аче которы х це п ь н и когд а н е закон чи тсвою работу . Если таки х си гн алов н е т, то файлд олже н сод е ржатьслово NO. П р имер ф ай лов вх одны х и вы х одны х данны х : INPUT.ТХ Т OUTPUT.TXT 2 0 5 2 10 05 10 15 1 –10
10 15
Задача12. « Н овы е гвозди» Н а п рям оу гольн ы й стол разложи ли N од и н аковы х ли стков бу м аги со сторон ам и , п аралле льн ы м и краям стола. Н е обход и м о п ри би ть ли стки к столу гвозд ям и так, чтобы в кажд ы йли сток бы л вби т ровн о од и н гвозд ь, а кажд ы м гвозд ём п ри кре п лялся к столу хотя бы од и н ли сток. Гвозд и н е льзя заби вать в гран и цы ли стков бу м аги . Т ех нические тр ебования Вход н ойфайл: INPUT.TXT Вы ход н ойфайл: OUTPUT.TXT О гран и че н и е вре м е н и : 20 се ку н д
Ф ор м атвх одны х данны х В файле и сход н ы х д ан н ы х зап и сан о коли че ство ли стков N (1≤N≤100), д ли н а ли стка L и е го ш и ри н а W (1≤L,W≤1000). Д але е сле д у ю т оп и сан и я N ли стков, зад ан н ы х коорд и н атам и ле вого н и жн е го у гла. О си коорд и н атрасп оложе н ы п о краям стола, н ачало коорд и н ат н аход и тся в ле вом н и жн е м у глу стола. К оорд и н аты точе к – п ары н е отри цате льн ы х це лы х чи се л, н е п ре восход ящ и х 1000. Все чи сла разд е ляю тся п робе лам и и /и ли си м волам и п е ре вод а строки . Ф ор м атвы х одны х данны х Если вби ть гвозд и тре бу е м ы м
в
у слови и
сп особом
н е возм ожн о, то н е обход и м о п ом е сти ть в вы ход н ой файл строку «вби ть гвозд и н е возм ожн о». Если и ском ы йсп особ су щ е ству е т, то п рограм м а д олжн а вы ве сти в вы ход н ойфайлкоорд и н аты гвозд е йв п рои звольн ом п оряд ке . К оорд и н аты гвозд е й– ве щ е стве н н ы е чи сла. Чи сла в вы ход н ом файле д олжн ы разд е ляться п робе лам и и /и ли си м волам и п е ре вод а строки . П р им ер ф ай лов вх одны х и вы х одны х данны х INPUТ.ТХ Т OUTPUT.TXT 3 6 6 10 10 13 7.5 0 0 5 5 12 3
Задача13. "П РО Б И РК И "
И м е ю тся три п роби рки . Вм е сти м ость кажд ой и з н и х - 100 м и лли ли тров. Н а п е рвы х д ву х п роби рках н ан е се н ы од и н аковы е ри ски . Тре тья п роби рка - бе з ри сок. Возле кажд ойри ски н ад п и сан о це лое чи сло м и лли ли тров, которое вм е щ ае тся в п роби рку отд н а д о э тойри ски . И зн ачальн о од н а и з п роби рок с ри скам и н ап олн е н а 100 м и лли ли трам и кваса, а остальн ы е д ве - п у сты е . Тре бу е тся н ап и сать п рограм м у , которая вы ясн яе т, м ожн о ли п ом е сти ть в п роби рку бе з ри сок од и н м и лли ли тр кваса, и е сли д а, то н аход и т м и н и м альн о н е обход и м ое д ля э того чи сло п е ре ли ван и й. К вас м ожн о п е ре ли вать и з од н ойп роби рки в д ру гу ю д о те х п ор, п ока ли бо п е рвая и з н и х н е стан е т п у стой, ли бо од н а и з п роби рок н е окаже тся зап олн е н н ойд о какой-ли бо ри ски . Т ех нические тр ебования: Вход н ойфайл: INPUТ.ТХ Т Вы ход н ойфайл: О UTPUТ.ТХ Т О гран и че н и е вре м е н и : 20 се ку н д Ф ор м атвх одны х данны х В п е рвойстроке вход н ого файла сод е ржи тся чи сло ри сок N (1<=N<=20) н а кажд ойи з п е рвы х д ву х п роби рок. Зате м в п оряд ке возрастан и я сле д у ю т N це лы х чи се л V1,...,VN (1<=Vi<=100), п ри п и сан н ы х ри скам . После д н яя ри ска счи тае тся сд е лан н ой н а ве рхн е м крае п роби рки (VN =100). Все чи сла разд е ляю тся п робе лам и и /и ли си м волам и п е ре вод а строки . Ф ор м атвы х одны х данны х В п е рвойстроке вы ход н ого файла д олжн а сод е ржаться строка "Yes", е сли в тре тью п роби рку возм ожн о отд е ли тьод и н м и лли ли тр
кваса, и "No" - в п роти вн ом слу чае . В п е рвом слу чае во втору ю строку н е обход и м о вы ве сти и ском ое коли че ство п е ре ли ван и й. П р им ер ф ай лов вх одны х и вы х одны х данны х INPUT.ТХ Т О UTPUТ.ТХ Т 4 Yes 13 37 71 100
8
Задача14. « Т очки» И м е е тся N точе к и и зве стн ы расстоян и я м е жд у н е которы м и и з н и х. Н ап и сать п рограм м у , которая п рове ряе т, м ожн о ли э ти точки расп оложи тьн а п лоскости так, чтобы у казан н ы е расстоян и я м е жд у н и м и сохран и ли сь. Т ех нические тр ебования Вход н ойфайл: INPUT.TXT Вы ход н ойфайл: OUTPUT.TXT О гран и че н и е вре м е н и : 20 се ку н д Ф ор м атвх одны х данны х В файле и сход н ы х д ан н ы х зап и сан о коли че ство точе к N (1≤N≤100), и
расстоян и я м е жд у н е которы м и
и з н и х в ви д е :
N_п е рвой_точки N_второй точки Расстоян и е . Расстоян и е – ве щ е стве н н ое н е отри цате льн ое чи сло, н е п ре восход ящ и е 1000. Н ом е р точки – це лое чи сло и з отре зка 1..N. Все чи сла разд е ляю тся п робе лам и и /и ли си м волам и п е ре вод а строки . Ф ор м атвы х одны х данны х
О тве том д олжн о бы тьслово Yes и ли No (Yes - точки м ожн о расп оложи ть, No –точки н е льзя расп оложи ть). П р им ер ф ай лов вх одны х и вы х одны х данны х INPUТ.ТХ Т OUTPUT.TXT 3 No 1 2 10 2 3 20 3 1 100 С ле д ующ ие
зад ач и пре д лаг ались на
о бласт ны х о лим пиадах
ш ко льнико в по инфо рм ат ике в 1998 – 2000 го д ах. Задача15. « В ы р аж ение» Зад ан ы д ва м ате м ати че ски х вы раже н и я, сод е ржащ и е це лы е чи сла, зн аки сложе н и я, вы чи тан и я и у м н оже н и я, кру глы е скобки и п е ре м е н н ы е , д ли н а которы х н е боле е од н ого си м вола. Н ап и сать п рограм м у , которая п о зад ан н ы м вы раже н и ям оп ре д е ляе т, равн ы ли он и тожд е стве н н о п ри все хзн аче н и яхп е ре м е н н ы х. Т ех нические тр ебования Вход н ойфайл: INPUT.TXT Вы ход н ойфайл: OUTPUT.TXT О гран и че н и е вре м е н и : 20 се ку н д Ф ор м атвх одны х данны х В файле и сход н ы хд ан н ы хзап и сан ы в отд е льн ы хстрокахд ва вы раже н и я.
Ф ор м атвы х одны х данны х О тве том д олжн о бы ть слово Yes и ли No (Yes – вы раже н и я тожд е стве н н о равн ы , No –вы раже н и я тожд е стве н н о н е равн ы ).
П р им ер ф ай лов вх одны х и вы х одны х данны х INPUТ.ТХ Т OUTPUT.TXT a+b*(c+d) Yes b*d+a+b*c Задача16. « А Б РА К А Д А Б РА » После д овате льн ость и з лати н ски х бу кв строи тся сле д у ю щ и м образом . Н а п е рвом ш аге он а п у ста. Н а кажд ом п осле д у ю щ е м ш аге п осле д овате льн ость у д ваи вае тся, п осле че го к н е й сле ва д оп и сы вае тся оче ре д н ая бу ква лати н ского алфави та (а, b, с, … ). Н и же п ри ве д е н ы п е рвы е ш аги п острое н и я п осле д овате льн ости : п у стая п осле д овате льн ость Ш аг 1. а Ш аг 2. bаа Ш аг 3. сbааbаа Ш аг 4. dсbааbаасbааbаа ......... Зад ача состои т в том , чтобы
п о зад ан н ом у чи слу N
оп ре д е ли ть си м вол, которы й стои т н а N-ом м е сте п осле д овате льн ости , п олу чи вш е йся п осле 26-го ш ага. Т ех нические тр ебования
в
Вход н ойфайл: INPUT.ТХ Т Вы ход н ойфайл: О UTPUТ.ТХ Т О гран и че н и е вре м е н и : 20 се ку н д Ф ор м атвх одны х данны х Во вход н ом файле зап и сан о од н о н ату ральн ое чи сло N (1<=N<226). Ф ор м атвы х одны х данны х Зап и ш и те в вы ход н ой файл си м вол, стоящ и й в п ози ци и N п олу чи вш е йся п осле д овате льн ости . П р им ер ф ай лов вх одны х и вы х одны х данны х INPUТ.ТХ Т OUTPUT.TXT 4 w С ле д у ю щ ая зад ача п ре д лагалась н а тре н и ровочн ом че тве ртьфи н ала м и рового п е рве н ства сту д е н тов
ту ре по
п рограм м и рован и ю ACM NEERC в 1996 год у . ЗадачаC « А нализсор тир овки» Н и же п ри ве д е н алгори тм MSort, которы йсорти ру е т зад ан н ы й м асси в A и з N це лы х чи се л. Э тот м е тод сорти ровки н азы вае тся сорти ровкой сли ян и е м . М асси в A разби вае тся н а д ве части , которы е сорти ру ю тся п о отд е льн ости э ти м же м е тод ом . Зате м отсорти рован н ы е п олови н ы сли ваю тся в од и н отсорти рован н ы й м асси в. И м я файла и сход н ы хд ан н ы х: INPUT.TXT
И м я вы ход н ого файла: OUTPUT.TXT Вре м я те сти рован и я: 10 се ку н д н а кажд ы йте ст Тре бу е тся н ап и сать п рограм м у , которая д ля зад ан н ого N (1< =N< =50.000.000) н аход и т: 1) М акси м альн ое коли че ство оп е раторов cравн е н и я "if A[i]< A[j]", которое м оже твы п олн и тьалгори тм MSort. 2) С трои т п ри м е р м асси ва A, н а котором д ости гае тся м акси м альн ое чи сло сравн е н и й (только д ля N< =10.000). Все э ле м е н ты м асси ва A д олжн ы бы ть разли чн ы м и и н аход и ться в д и ап азон е от1 д о N, т.е . м асси в A д олже н сод е ржать п е ре стан овку чи се л1,2, ..., N. Вход н ы е д ан н ы е Файли сход н ы хд ан н ы хсод е ржи тчи сло N. Вы ход н ы е д ан н ы е Вы ве сти в вы ход н ой файл м акси м альн ое
коли че ство
сравн е н и йи зн аче н и я э ле м е н тов м асси ва A[1], A[2], ..., A [N]. Если N >10000, то вы ход н ой файл д олже н сод е ржать только м акси м альн ое коли че ство сравн е н и й. Все чи сла в вы ход н ом файле разд е ляю тся п робе лам и и (и ли ) си м волам и п е ре вод а строки . При м е р 1 файла и сход н ы хд ан н ы хINPUT.TXT: 3 Вы ход н ойфайлOUTPUT.TXT д ля п ри м е ра 1: 3 213 При м е р 2 файла и сход н ы хд ан н ы хINPUT.TXT:
10001 Вы ход н ойфайлOUTPUT.TXT д ля п ри м е ра 2: 123631 АЛ ГО РИ ТМ MSort: | algorithm MSort (N: integer; var A: integer array [1..N]); | var Help: integer array [1..N]; | | procedure Make (u, v: integer); | var i, j, m, k: integer; | begin | if u < v then | m := (u+v) / 2; (* д е ле н и е н аце ло с окру гле н и е м в сторон у н у ля *) | |
call Make (u, m); call Make (m+1, v);
| | | |
i := u; j := m+1; k := u; while (i<=m) and (j<=v) do (* !!! О ПЕРАТО Р С РАВН Е Н И Я *) if A[i]
| | | | | | | |
else Help [k] := A [j]; j := j+1; end if; k := k+1; end while; while i<=m do Help [k] := A [i]; i:=i+1; k:=k+1; end while; while j<=v do Help [k] := A [j]; j:=j+1; k:=k+1; end while; for i = u to v do A [i] := help [i]; end for; end if;
| |
end Make;
| begin | call Make (1, N); | end MSort;
3. ЗА Д А ЧИ СК О М М Е Н Т А РИ Я М И И РЕ Ш Е Н И Я М И Задача1. « М онеты ». Зад ач а бы ла пре д ло же на на К расно ярско й краево й о лим пиад е ш ко льнико в, а т акже на Во ро не жско й г о ро д ско й ст уд е нч е ско й о лим пиад е 2000 г о д а. Од ним из призе ро в о лим пиады бы л ст уд е нт 3 курса факульт е т а приклад но й м ат ем ат ики и м е ханики М аксим Сер геевич Ефр ем о в. Н иже приво дит ся е г о вариант ре ш е ния задач и. 1. У слови е зад ачи . В су н д у ке у м и сте ра Z и м е е тся N м он е т. Н а сле д у ю щ и й год м и сте р Z взял и з су н д у ка M м он е т. В кажд ы й сле д у ю щ и й год м и сте р Z д обавлял в су н д у к столько м он е т, сколько у н е го бы ло д ва год а н азад . И зве стн о, что н а X-йгод в су н д у ке м и сте ра Z бы ло Y м он е т. Тре бу е тся оп ре д е ли ть, сколько м он е т бы ло в су н д у ке и зн ачальн о, и сколько м он е тм и сте р Z взялн а второйгод . Форм атввод а: файлInput.txt сод е ржи тчи сла X и Y.
Форм атвы вод а файлOutput.txt сод е ржи тчи сла N и M. 2. Алгори тм ре ш е н и я. Алгори тм ре ш е н и я - чи сто п осле д овате льн остьчи се л
м ате м ати че ски й. Рассм отри м
А(1), А(2), .. , А(n),.., гд е А(k) - чи сло м он е тв су н д у ке н а k-йгод . И з у слови я зад ачи п олу чае м A(1)=N, A(2)=N-M, A(3)=2N-M, A(4)=3N-2M, A(5)=5N-3M, A(6)=8N-5M,
гд е
........ A(X)=F(X)N-F(X-1)M=Y, ........ F(n) - п осле д овате льн ость чи се л Ф и бон аччи , которы е
оп ре д е ляю тся ре ку рре н тн ы м и соотн ош е н и ям и F(1) = 1, F(2) = 1, F(K) = F(K-1)+F(K-2), K>2. Вп олн е оче ви д н о, что д ля н ахожд е н и я M и N д остаточн о н айти це лочи сле н н ое ре ш е н и е у равн е н и я F(X)N - F(X-1)M = Y. (*) Такое у равн е н и е , вообщ е говоря, и м е е т сче тн ое м н оже ство ре ш е н и й. О д н ако в д ан н ом слу чае э то м н оже ство кон е чн о, п оскольку A(n)>=0 д ля все хn и
A(K)>=A(K-2), д ля K>2, а зн ачи ти M<=N<=Y. 3. Програм м н ая ре али заци я. Програм м н ая ре али заци я
(**)
свод и тся
к
н ахожд е н и ю
це лочи сле н н ого ре ш е н и я у равн е н и я (*) п ри у слови и вы п олн е н и я (**). Програм м а н аход и т все возм ожн ы е вари ан ты отве та и ли вы д ае тсообщ е н и е о том , что ре ш е н и я н е т. Program Money; Var F:Text; X,Y:Integer; Procedure Init; {ввод и з файла} Begin Assign(F,'Input.txt');ReSet(F); ReadLn(F,X,Y); Close(F) End; Function GetValue(K:Integer):Integer; {п олу че н и е F(k)} Var I,A,B,C:Integer; Begin If K<=2 Then GetValue:=1 Else Begin A:=1;B:=1;
For I:=3 To K Do Begin C:=B; B:=B+A; A:=C End; GetValue:=B End End; Procedure Run; Var M,N:Integer; A,B:Integer; T:Boolean;
{ре ш е н и е у равн е н и я}
{флаг разре ш и м ости у равн е н и я: true-е сли
ре ш е н и е е сть} Begin Assign(F,'Output.txt');ReWrite(F); A:=GetValue(X); B:=GetValue(X-1); T:=False; For N:=1 To Y Do For M:=0 To N Do If A*N-B*M=Y Then Begin T:=True; WriteLn(F,N,' ',M) End; If Not T Then WriteLn(F,'Зад ача н е и м е е тре ш е н и я!');
Close(F) End; Begin Init; Run End.
Задача2. "Ф у нкц ия" Зад ач а бы ла пре д ло же на на М о ско вско й о лим пиад е ш ко льнико в в 1981г. ина о лим пиад е перво курснико в факульт е т а П М М в 1998г . Н иже приво дит ся про грам м а, разрабо т анная Ол его м Викт о р о вичем Г л ады ш евы м , ко т о ры й се йч ас о буч ае т ся на 4-м курсе факульт е т а П М М ВГУ. 1. У слови е зад ачи . Фу н кци я F(n) д ля це лы хн е отри цате льн ы хn оп ре д е ле н а так: F(0)=0, F(1)=1, F(2n) = F(n), F(2n+1)=F(n)+F(n+1). Д ля д ан н ого N н айти и н ап е чатать F(n). О бязате льн ое у слови е : N стольве ли ко, что н е д оп у сти м о завод и тьм асси в и з N чи се л. 2. Алгори тм ре ш е н и я. О сн овн ая и д е я алгори тм а заклю чае тся в том , что п ри разложе н и и f(2n+1) н а f(n) и f(n+1) м ы д олжн ы вы чи сли ть 2 зн аче н и я фу н кци и . Л и бо n, ли бо n+1 окаже тся н е че тн ы м и д ля е го вы чи сле н и я п он ад оби тся оп ять вы чи слять 2 зн аче н и я фу н кци и . А д ля че тн ого аргу м е н та е щ е од н о. Н а п е рвы йвзгляд , каже тся, что
те п е рь н ам н ад о вы чи сли ть зн аче н и я F д ля 3 аргу м е н тов, н о н а сам ом д е ле 2 и з н и х (аргу м е н тов) все гд а совп ад у т! То е сть кол-во вы чи сле н и й фу н кци и н а кажд ом ш аге н е у ве ли чи вае тся. При м е р: F(26) = F(13) = F(6)+F(7) = F(3)+F(3)+F(4) = 2F(3)+F(4) = =2(F(1)+F(2))+F(2) = 2F(1)+3F(2) = 5F(1) = 5 3. Програм м н ая ре али заци я Program func; {Автор: Глад ы ш е в О .В.} var c, {Те ку щ и йче тн ы йаргу м е н т} nc, kc, knc, n:LongInt;
{Те ку щ и йн е че тн ы йаргу м н т} {К оэ ффи ци е н тп ри че тн ом аргу м е н те } {К оэ ффи ци е н тп ри н е че тн ом аргу м е н те }
{В п е ре м е н н ойc все гд а д олже н бы ть че тн ы й аргу м е н т, а в nc н е че тн ы й. Э та п роце д у ра м е н яе тм е стам и зн аче н и я п е ре м е н н ы хc и nc, е сли э то н е обход и м о} Procedure Correct; var Temp:LongInt; Begin if odd(c) then Begin Temp:=c; c:=nc; nc:=Temp; Temp:=kc; kc:=knc;
knc:=Temp; End; End; Begin Write('Вве д и те чи сло '); ReadLn(N); n:=abs(n); {Вы чи сли м м од у льn} if n=0 then Writeln('0') else Begin while n mod 2 = 0 do n:=n div 2; {у м е н ьш ае м n д о н е че тн ого чи сла} c:=n div 2; {Разложи м n н а че тн ое } nc:=n-c; {и н е че тн ое чи сла} if c=0 then kc:=0 else kc:=1; knc:=1; while (c>2) or (nc>2) do Begin Correct; c:=c div 2; kc:=kc+knc; nc:=nc-c; End; WriteLn(Kc+knc); ReadLn; End; End. Задача3. "Лабир инт"
{п ом е н яе м c и nc, е сли н у жн о} {п олу чи м н овы йаргу м е н т} {п олу чи м коэ фф. п ри н е м } {вы чи сли м второйаргу м е н т} {Вы ве д е м ре зу льтат} {Под ожд е м }
Задач а бы ла пре д ло же на на о бщ е униве рсит е т ско й о лим пиад е по про г рам м иро ванию, по свящ е нно й д ню ро жд е ния факульт е т а П М М (м арт 2001). Н иже приве д е но ре ш е ние по бе дит е ля о лим пиады , в наст о ящ е е вре м я ст уд е нт а 4 курса факульт е т а П М М ВГУ Ан т о н а Ал ексан др о вича Кл ин ских. 1. У слови е зад ачи . В ре зу льтате ре йд а н алоговойп оли ци и город а О блом ова в фи рм у Real в од н ом и з н е боскрёбов бы лобн ару же н се кре тн ы йу рове н ь, н а которы йве ла только од н а ле стн и ца, а в н е которы х м е стах бы ли авари йн ы е вы ход ы (в ви д е лю ков в п олу ). С огласн о аге н ту рн ы м д ан н ы м , у рове н ь п ре д ставляе т собой п рям оу гольн и к и з M*N ком н атод и н акового разм е ра (M ком н атвд оль зап ад н ойсте н ы , N -вд оль се ве рн ой), п ри чём м е жд у н е которы м и п арам и сосе д н и х ком н ат е сть д ве ри . Положе н и е осложн яе тся те м , что точн ы е коорд и н аты как вход а, так и вы ход ов н е и зве стн ы . Н а разве д ку бы ли отп равле н ы обе зьян ки и з м е стн ого зооп арка. К ажд ая и з н и х п од н и м алась п о ле стн и це и ход и ла п о у ровн ю , п ока н е н аты калась н а какой-н и бу д ь вы ход . После э того он а сп у скалась п о н е м у и сообщ ала свойм арш ру т н ачальству . При э том п е рвая обе зьян ка в н ачальн ой точке см отре ла н а се ве р, а остальн ы е н е и зве стн о ку д а. М арш ру т кажд ойобе зьян ки п ре д ставле н в ви д е п осле д овате льн ости си м волов, п ре д ставляю щ и х д ви же н и я и п овороты : F ш аг вп е рёд R п оворотн ап раво L п оворотн але во B разворот W вп е ре д и сте н а, д ви же н и я н е бы ло
E вы ход , кон е ц м арш ру та (м оже т и д ти только н е п осре д стве н н о п осле F) Зад ача состои т в том , чтобы п острои ть п лан обсле д ован н ой части у ровн я, сод е ржащ и й всю собран н у ю и н форм аци ю : сте н ки , п роход ы , вы ход ы . Вход н ойфайл: INPUT.TXT Вы ход н ойфайл: OUTPUT.TXT Вре м я те сти рован и я: 20 се к/те ст Вход н ы е д ан н ы е В п е рвой строке вход н ого п отока зад аю тся чи сла M и N, разд е лён н ы е п робе лам и . Н а сле д у ю щ е йстроке зад аётся общ е е коли че ство м арш ру тов. Д але е и д у т м арш ру ты , п ре д ставляю щ и е собойп осле д овате льн ость си м волов F, R, L, B, W, E, возм ожн о, разд е лён н ы х п робе льн ы м и си м волам и . К ажд ы й м арш ру т закан чи вае тся си м волом E, п осле которого н ачи н ае тся сле д у ю щ и йм арш ру т. О гран и че н и я Вход н ы е д ан н ы е у д овле творяю т сле д у ю щ и м огран и че н и ям : 1 < M < 50, 1 < N < 50, общ е е коли че ство м арш ру тов -- н е боле е 100, общ е е коли че ство си м волов в зап и си м арш ру тов -- н е боле е 255. Ре зу льтат Програм м а д олжн а н ап е чатать карту у ровн я разм е ра (2M+1)*(2N+1), н ари сован н у ю си м волам и : (<<п робе л>>) п у стая ком н ата и ли п роход + у голком н аты - се ве рн ая/ю жн ая сте н ка | зап ад н ая/восточн ая сте н ка * вход
# вы ход ? н е и зве стн ое состоян и е ком н аты и ли сте н ки Если су щ е ству е т н е сколько п лан ов у ровн е й, у д овле творяю щ и х у слови ям зад ачи , д остаточн о н ап е чатать лю бой, е сли п лан п острои тьн е у д аётся, п рограм м а д олжн а н ап е чататьстроку NO. 2. Алгори тм ре ш е н и я. Д ля п острое н и я п лан а н е обход и м о соотн е сти д он е се н и я все х обе зьян ок так, чтобы он и н е п роти воре чи ли д ру г д ру гу . И сп ользу е тся бэ к-трэ ки н г, расш и фровы ваю щ и й м арш ру т оче ре д н ойобе зьян ки , и е сли э то п ри вод и тк кон фли кту , п осле д н и й м арш ру т отм е н яе тся, и п рои звод и тся п оп ы тка согласовать м арш ру т э тойобе зьян ки , п ре д п оложи в, что в н ачальн ы й м ом е н т он а см отре ла в д ру гу ю сторон у и т.д . Е сли все че ты ре н ачальн ы х н ап равле н и я обе зьян ки п ри вод ят к кон фли ктам , счи тае тся, что п лан д ля э той обе зьян ки п острои ть н е у д ае тся, что вы зове т и зм е н е н и е н ачальн ого н ап равле н и я п ре д ы д у щ е йобе зьян ки и т.д . д о п е рвой. О ткат ре али зу е тся с п ом ощ ью ре ку рси и , а состоян и я п лан а хран ятся в сте ке . Если п ри какой-ли бо ком би н аци и н ачальн ы х состоян и йвсе х обе зьян ок п лан п острое н , он и являе тся отве том . Если такой ком би н аци и н е т, п лан а н е су щ е ству е т. 3. Програм м н ая ре али заци я. Program Labirint; {Автор-К ли н ски хА.А.} const MaxN=50; MaxM=50; type TPoint=record
x,y:integer end; PPlan=^TPlan; TPlan=array[-2*MaxN..2*MaxN,-2*MaxM..2*MaxM] of char; {План } TStack=^TElem; TElem=record Plan:TPlan; L,R,T,B:integer; Next:TStack end; var Stack:TStack; {С те к} Input,Output:Text; {Файлы ввод а/вы вод а} M,N:integer; {Разм е ры п оля} NOfM:integer; {Чи сло м арш ру тов} L,R,T,B:integer; {Те ку щ и е гран и цы п оля} Cur,Next,Dir:TPoint; {Те ку щ ая и сле д у ю щ ая точки и н ап равле н и е , ку д а см отри тобе зьян а} Plan:TPlan; {План } Monkeys:array[1..10] of string; {М арш ру ты } {****************************} {Проце д у ры работы со сте ком } {И н и ци али заци я сте ка} procedure InitStack; begin Stack:=nil end;
{Д обавле н и е в сте к} procedure PushStack(var Plan:TPlan;T,B,L,R:integer); var p:TStack; begin p:=Stack; new(Stack); Stack^.Plan:=Plan; Stack^.T:=T; Stack^.L:=L; Stack^.R:=R; Stack^.B:=B; Stack^.next:=p end; {И звле че н и е и з сте ка} procedure PopStack(var Plan:TPlan;var T,B,L,R:integer); var p:TStack; begin p:=Stack; Stack:=Stack^.next; T:=p^.T; L:=p^.L; R:=p^.R; B:=p^.B; Plan:=p^.Plan; dispose(p) end;
{Прове рка сте ка н а п у стоту } Function Empty:boolean; begin Empty:=Stack=nil end; {********************************} {Проце д у ра чте н и я} procedure InitIO; var i:integer; begin assign(input,'input.txt'); assign(output,'output.txt'); reset(input); rewrite(output); read(input,M); readln(input,N); readln(input,NOfM); For i:=1 to NofM do readln(input,Monkeys[i]) end; {*****************************************} {----------------Алгори тм ------------------} {Фу н кци я,"п ы таю щ аяся" расш и фроватьоче ре д н ойм арш ру т} {Если у д алосьп острои тьп лан ,возвращ ае тtrue}
Function GetNextMonkey(nom:integer):boolean; var index:byte; c:char; begin GetNextMonkey:=False; index:=1; {Н ом е р оче ре д н ого си м вола в м арш ру те } repeat c:=Monkeys[nom][index]; case c of 'F':begin {Если бы лш аг вп е ре д } if (Plan[Next.x,Next.y] in [' ','?']) then {Если вп е ре д и сте н ка,} begin {ш агатьту д а н е льзя} Cur:=Next; Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y; Plan[cur.x,cur.y]:=' '; if Monkeys[nom][index+1]='E' then {О бе зьян ка зд е сьвы ш ла} begin GetNextMonkey:=Plan[Next.x,Next.y] in ['?','#']; {е сли э то н е возм ожн о} if [Plan[Next.x,Next.y]]*['?','#']=[] then exit; {зап ом и н ае м ош и бку } Plan[Next.x,Next.y]:='#' {и н аче у стан авли вае м вы ход } end; if Plan[Next.x,Next.y] in ['?'] then Plan[Next.x,Next.y]:=' '; Cur:=Next; Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y; {--------} if cur.y>=T then T:=cur.y+1; {И зм е н яе м м е стоп оложе н и е обе зьян ки }
if cur.y<=B then B:=cur.y-1; if cur.x>=R then R:=cur.x+1;
{и габари ты п лан а(е сли н у жн о)}
if cur.x<=L then L:=cur.x-1; {-----------} if ((T-B+1)>2*M+1) or ((R-L+1)>2*N+1) then exit; {План сли ш ком больш ой} if Plan[cur.x,cur.y]='#' then begin {При ш ли н а вы ход :п рове ри м сообщ е н и е обе зьян ки } GetNextMonkey:=Monkeys[nom][index+1]='E'; {и вы йд е м } exit end end else exit end; 'L':begin
{Пове рн е м обе зьян ку н але во}
if dir.x=0 then begin dir.x:=-dir.y; dir.y:=0 end else begin dir.y:=dir.x; dir.x:=0 end; Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y end; 'R':begin {Пове рн е м обе зьян ку н ап раво} if dir.x=0 then
begin dir.x:=dir.y; dir.y:=0 end else begin dir.y:=-dir.x; dir.x:=0 end; Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y end; 'B':begin {Разве рн е м обе зьян ку } dir.x:=-dir.x; dir.y:=-dir.y; Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y end; 'W':begin {Вп е ре д и сте н ка} if Plan[Next.x,Next.y] in ['?','-','|'] then begin if dir.x=0 then Plan[Next.x,Next.y]:='-' гори зон тальн ая} else Plan[Next.x,Next.y]:='|'; if Next.y>T then T:=Next.y; if Next.yR then R:=Next.x; н у жн о)} if Next.x
{ве рти кальн ая и ли
{И зм е н яе м габари ты п лан а(е сли
else exit end end; inc(index) until c='E'; GetNextMonkey:=True {Если н е бы ло авари йн ы хвы ход ов,все в п оряд ке } end; {Фу н кци я, н аход ящ ая п лан п о все м м арш ру там н ачи н ая с por.} {Ре ку рси вн о вы зы вае тсам у се бя п ока н е и сп ользу е твсе м арш ру ты } {Если у д алосьп острои тьп лан ,возвращ ае тtrue} Function GetMonkeys(por:integer):boolean; var t0,b0,l0,r0:integer; D:TPoint; p:PPlan; OK:boolean; Count:integer; begin if por>NOfM then begin {Все м арш ру ты согласован ы } GetMonkeys:=True; {Зап ом и н ае м ,что п лан п острое н } new(p); while not Empty do {О чи щ ае м сте к} PopStack(p^,T0,B0,L0,R0); exit
end; Count:=1; d.x:=0; d.y:=1; repeat Dir:=D; Cur.x:=0; Cur.y:=0; Next.x:=Cur.x+Dir.x; Next.y:=Cur.y+Dir.y; PushStack(Plan,T,B,L,R); {С охран яе м н астройки } OK:=GetNextMonkey(por) and GetMonkeys(por+1); {Д обавляе м м арш ру т} if OK then break; {Если OK вы ход и м } PopStack(Plan,T,B,L,R); {и н аче восстан ови м н астройки } if d.x=0 then {и п ове рн е м обе зьян ку } begin d.x:=d.y; d.y:=0 end else begin d.y:=-d.x;d.x:=0 end; inc(Count) until (Count=5) or OK; GetMonkeys:=OK end; {***********************************} {И н и ци али заци я п оля} procedure Clear; var i,j:integer;
begin For i:=-MaxN to MaxN do For j:=-MaxM to MaxM do if odd(abs(i)) and odd(abs(j)) then Plan[i,j]:='+' else Plan[i,j]:='?'; Plan[0,0]:='*' end; {Вы вод п лан а} procedure ShowPlan; var i,j:integer; begin For i:=T downto T-2*M do begin For j:=L to L+2*N do begin if (i=T) or (i=T-2*M) then if odd(j-L) then write(output,'-') else write(output,'+') else if (j=L) or (j=L+2*N) then if odd(T-i) then write(output,'|') else write(output,'+') else
write(output,Plan[j,i]); end; writeln(output); end end; {Вы вод сообщ е н и я об ош и бке } procedure ShowError; begin writeln(output,'NO') end; {Закры вае м и сп ользован н ы е файлы } procedure CloseIO; begin close(input);close(output) end; begin
{О сн овн ая п рограм м а}
InitIO; Clear; if GetMonkeys(1) then ShowPlan else ShowError; CloseIO end. Задача4. « П р ямоу гольники»
Зад ач а пред лагалась в 1998 г о д у на о лим пиад е пе рво курснико в факульт е т а П М М ВГУ. Авт о р ре ш е ния – о д на из призеро в о лим пиады , Лусин е Азат о вн а М хит ар ян , в наст о ящ е е вре м я ст уд е нт ка 5 курса факульт е т а П М М 1. У слови е зад ачи Н а п лоскости зад ан о N п рям оу гольн и ков с коорд и н атам и ве рш и н (X1i,Y1i),(X2i,Y2i),(X3i,Y3i),(X4i,Y4i) , i=1,2,3,...,N. И зве стн о, что все сторон ы п рям оу гольн и ков п аралле льн ы осям коорд и н ат. Все п рям оу гольн и ки являю тся зам кн у ты м и м н оже ствам и , т.е . сод е ржат свою гран и цу . Б у д е м счи тать, что п рям оу гольн и ки п е ре се каю тся, е сли он и и м е ю хотя бы од н у общ у ю точку (в том чи сле и н а гран и це ). Н е обход и м о оп ре д е ли ть коли че ство фи гу р образован н ы х в ре зу льтате н аложе н и я п рям оу гольн и ков. Вход н ы е д ан н ы е В п е рвойстроке (1<=N<=100) - чи сло п рям оу гольн и ков. В кажд ойп осле д у ю щ е йи хкоорд и н аты , зад ан н ы е це лы м и чи слам и -1000<=X1i,Y1i,X2i,Y2i,X3i,Y3i,X4i,Y4i<=1000) i=1,2,3,...,N. Вы ход н ы е д ан н ы е Чи сло фи гу р. 2. Алгори тм ре ш е н и я. Зад ача ре ш ае тся с и сп ользован и е м э ле м е н тов те ори и графов. С трои тся м атри ца и н ци д е н тн ости M, гд е M[I,J]=1 е сли I-ты й п рям оу гольн и к п е ре се кае тся с J-ты м . О стае тся ли ш ь оп ре д е ли ть чи сло ком п он е н тсвязн ости п олу че н н ого графа.
3. Програм м н ая ре али заци я Program Rectangular; {Автор М хи тарян Л .А.} Const MaxN=100; Type TRec=Record XA,YA,XB,YB:Integer End; Var PA:Array [1..MaxN] of TRec; M:Array[1..MaxN,1..MaxN] of Boolean; N,FC:Integer; BA:Array[1..MaxN] of Boolean; Function Min(A,B:Integer):Integer; Begin If A>B Then Min:=B Else Min:=A End; Function Max(A,B:Integer):Integer; Begin If A
ReadLn(F,X1,Y1,X2,Y2,X3,Y3,X4,Y4); PA[I].XA:=Min(Min(X1,X2),Min(X3,X4)); PA[I].YA:=Min(Min(Y1,Y2),Min(Y3,Y4)); PA[I].XB:=Max(Max(X1,X2),Max(X3,X4)); PA[I].YB:=Max(Max(Y1,Y2),Max(Y3,Y4)); End; For I:=1 to N do For X1:=1 to N do M[I,X1]:=False; For I:=1 to N do BA[I]:=False; Close(F) End; Function Check(I,J:Integer):Boolean; {Прове рка: п е ре се каю тся ли I-ы йи J-ы йп рям оу гольн и ки } Var R1,R2:TRec; Begin Check:=False; If PA[I].XA=R2.XA Then Begin If (R1.YB>=R2.YA) and (R1.YB<=R2.YB) Then Check:=True; If (R2.YB>=R1.YA) and (R2.YB<=R1.YB) Then Check:=True End End; Function GetPodGraph:Boolean;
{Вы д е ле н и е ком п он е н ты связн ости графа} Var I,J,K,T:Integer; Begin T:=-1; For I:=1 to N do If not BA[I] Then Begin T:=I;Break End; If T=-1 Then Begin GetPodgraph:=False;Exit End; M[T,T]:=True; For I:=1 to N do For J:=1 to N do For K:=1 to n Do If M[J,J] Then If M[J,K] Then M[K,K]:=True; For I:=1 to N do If not BA[I] and M[I,I] Then BA[I]:=True; GetPodGraph:=True End; Procedure Run; {Вы чи сле н и е коли че ства п од графов} Var I,J:Integer; Begin FC:=0; For I:=1 to N do For J:=1 to N do If I<>J Then M[I,J]:=Check(I,J); While GetPodgraph do Begin Inc(FC);
For I:=1 to N do If M[I,I] then M[I,I]:=False; End; End; Procedure Done; {Вы вод ре зу льтатов} Var F:Text; Begin Assign(F,'output.txt');ReWrite(F); WriteLn(F,FC); Close(F); End; Begin Init; Run; Done End. Задача5. « Т р у боп р овод» В о сно ву усло вия задач и по ло же на задач а, ко т о рая пре д лаг алась на ч е т ве рт ь финале м иро во го пе рве нст ва по про г рам м иро ванию 2000 г о д а (г .С арат о в). Авт о р про г рам м ы – ч ле н сбо рно й ВГУ по про г рам м иро ванию, в наст о ящ е е вре м я ст уд е нт 5 курса факульт е т а П М М ВГУ Ан др ей Евген ь евич П о л яко в. 1. У слови е зад ачи .
Пу сть и м е е тся тру боп ровод , зад ан н ы й п рям ой ли н и е й н а п лоскости Ax+By+C=0 и д ва город а с коорд и н атам и (x1,y1), (x2,y2). Н е обход и м о сое д и н и ть э ти д ва город а с тру боп ровод ом , и страти в п ри э том н аи м е н ьш е е чи сло тру б; у казать су м м арн у ю д ли н у и сп ользован н ы х тру б и д ве точки гд е п рои сход и т сое д и н е н и е тру боп ровод ов. Вход н ы е д ан н ы е Ц е лы е чи сла -100000<=A,B,C<=100000 - п арам е тры тру боп ровод а -100000<=X1,Y1<=100000 - коорд и н аты п е рвого город а -100000<=X2,Y2<=100000 - коорд и н аты второго город а Вы ход н ы е д ан н ы е В п е рвойстроке су м м арн ая д ли н а и сп ользован н ы хтру б Во второйи тре тье йсоотве тстве н н о коорд и н аты точе к сое д и н е н и я тру боп ровод ов 2. Алгори тм ре ш е н и я Рассм отри м д ве возм ожн ости 1). Точки ле жат с разн ы х сторон от п рям ой. Тогд а д ля и х сое д и н е н и я д остаточн о оп у сти ть н а п рям у ю п е рп е н д и ку ляры и з э ти х точе к. Н а вы ход е п олу чи м су м м у д ли н э ти х п е рп е н д и ку ляров и и хточки п е ре се че н и я с п рям ой. 2). Точки ле жат п о од н у сторон у от п рям ой. Зд е сь возм ожн ы 3 слу чая а) О д н а точка сое д и н яе тся с д ру гой, и з которойзате м оп у скае тся п е рп е н д и ку ляр н а п рям у ю . Н а вы ход е : д ли н а п е рп е н д и ку ляра п лю с расстоян и е м е жд у точкам и , коорд и н аты точки п е ре се че н и я
п е рп е н д и ку ляра и п рям ой, коорд и н аты сам ойбли жн е й к п рям ой точки . б) С у щ е ству е ттре тья точка, д ля которойвы п олн яе тся у слови е : п е рп е н д и ку ляр и з э тойточки к п рям ойи отре зки , сое д и н яю щ и е э ту точку с д ву м я зад ан н ы м и , образу ю ту гол120 град у сов. Н а вы ход е : д ли н а п е рп е н д и ку ляра + су м м а расстоян и й, коорд и н аты тре тье й точки и е е п рое кци и н а п рям у ю . в) ан алоги чн о 1). 3. Програм м н ая ре али заци я Program Tubes; {Автор Поляков А.Е.} Var X1,Y1,X2,Y2,A,B,C:LongInt; Procedure Init; {И н и ци али заци я} Var F:Text; Begin Assign(F,'input.txt');ReSet(F); ReadLn(F,A,B,C); ReadLn(F,X1,Y1); ReadLn(F,X2,Y2); Close(F) End; Function TestLocation:Boolean; {Прове рка м е стон ахожд е н и я зад ан н ы хточе к Возвращ ае т True, е сли точки расп оложе н ы с од н ой сторон ы , и False в п роти вн ом слу чае } Begin
TestLocation:=(A*X1+B*Y1+C)*(A*X2+B*Y2+C)>0 End; Function Dest(X,Y:Double):Double; {Вы чи сле н и е д ли н ы ве ктора} Begin Dest:=Sqrt(Sqr(X)+Sqr(Y)) End; Procedure Proj(X,Y:Double;Var TX,TY:Double); {Вы чи сле н и е п рое кци и точки (X,Y) н а п рям у ю } Begin TX:=(-C*A+Sqr(B)*X-A*B*Y)/(Sqr(A)+Sqr(B)); TY:=(-C*B-A*B*X+Sqr(A)*Y)/(Sqr(A)+Sqr(B)); End; Function FindDifferentSideDest(Var tx1,Ty1,Tx2,ty2:Double):Double; {Ре ш е н и е зад ачи д ля слу чая 1} Var D:Double; Begin Proj(X1,Y1,Tx1,Ty1); D:=Dest(TX1-X1,TY1-Y1); Proj(X2,Y2,Tx2,Ty2); FindDifferentSideDest:=D+Dest(TX2-X2,TY2-Y2) End; Procedure FindPoint(PX,PY,X,Y,D:Double;Var TX,TY:Double); {Н ахожд е н и е коорд и н ат точки н а п рям ой, и з которойточка (x,y) ви д н а п од у глом 30 град у сов}
Var TX1,TX2,TY1,Ty2,Sq:Double; Begin Sq:=sqrt(3)*D/Sqrt(Sqr(A)+Sqr(B)); TX1:=PX+B*sq;TY1:=PY-A*Sq; TX2:=PX-B*Sq;TY2:=PY+A*Sq; PX:=Dest(TX1-X,Ty1-Y); PY:=Dest(TX2-X,Ty2-Y); If PxT) or (D1>T) Then If D1>D2 Then Begin Tx1:=x2;ty1:=Y2;Tx2:=Px2;Ty2:=Py2;Res:=D2+T End
Else Begin Tx1:=x1;ty1:=Y1;Tx2:=Px1;Ty2:=Py1;Res:=D1+T End; {С лу чай2 б} T:=Dest(LX1-LX2,LY1-LY2)/2; T:=T/sqrt(3);PX1:=Dest(Lx1-X1,Ly1-Y1);PY1:=Dest(Lx2-X2,Ly2Y2); If (2*T < PX1) and (2*T < PY1) and (Dest(Lx2-X1,Ly2-Y1)T Then Begin Res:=T; If (A*PX1+B*PY1+C)*(A*X2+B*Y2+C)>0 Then Begin Tx2:=Px1;Ty2:=Py1 End Else Begin Tx2:=Px2;Ty2:=Py2 End; Tx1:=(Lx1+Lx2)/2;Ty1:=(Ly1+Ly2)/2 End End; FindOneSideDest:=Res End; Procedure Done; {Вы вод ре зу льтатов} Var F:Text;Tx1,Ty1,tx2,ty2,D:Double;
Begin Assign(F,'output.txt');ReWrite(F); If not TestLocation Then D:=FindDifferentSideDest(Tx1,Ty1,Tx2,Ty2) Else D:=FindOneSideDest(Tx1,Ty1,Tx2,Ty2); WriteLn(F,D:1:4); WriteLn(F,Tx1:1:4,' ',Ty1:1:4); WriteLn(F,Tx2:1:4,' ',Ty2:1:4); Close(F) End; Begin Init; Done End. Задача6. "Т елебаш ня" Задач а бы ла пре д ло же на на о бщ е униве рсит е т ско й о лим пиад е по про г рам м иро ванию, по свящ ённо й д ню ро жд е ния факульт е т а П М М (м арт 2001). Н иже приво дит ся ре ш е ние по бе дит е ля о лим пиады , в наст о ящ е е вре м я ст уд е нт а 4 курса факульт е т а П М М ВГУ М ихаил а М ихай л о вича Ш ир яева 1. У слови е зад ачи . В ре зу льтате п ожара п олн остью сгоре ла те ле ви зи он н ая баш н я город а О блом ова, и всё н асе ле н и е город а осталось бе з те ле ви д е н и я. Чтобы восстан ови ть те ле ве щ ан и е в кратчайш и е сроки , м э р город а расп оряд и лся разм е сти ть п е ре д атчи ки н а кры ш ахн е которы хд ом ов. О д н ако си ту аци я осложн яе тся н али чи е м в город е н е скольки хн е боскрёбов, влад е льцы которы ху стан ови ли у се бя н а кры ш е ан те н н у сп у тн и ковойси сте м ы See++ и п оэ том у н е
д аю т согласи я н а у стан овку там п е ре д атчи ков. Б оле е того, э ти н е боскрёбы являю тся п ре град ойн а п у ти расп ростран е н и я си гн ала, п оэ том у у стан овки од н ого п е ре д атчи ка м оже т оказаться н е д остаточн о. М э р хоче т у стан ови ть м и н и м альн ое коли че ство п е ре д атчи ков так, чтобы зон ы расп ростран е н и я си гн ала п окры вали ве сь город , и склю чая, возм ожн о, те рри тори ю , зан и м ае м у ю у п ом ян у ты м и вы ш е н е боскрёбам и . Город О блом ов п ре д ставляе т собойп рям оу гольн и к кварталов. Все кварталы и м е ю т форм у квад рата равн ойп лощ ад и , а ш и ри н а у ли ц н е зн ачи те льн а п о сравн е н и ю с разм е рам и квартала. К ажд ы й н е боскрёб зан и м ае тп олн остью од и н квартал. К ажд ы й квартал (кром е н е боскрёбов) и м е е т е д и н стве н н у ю те ле ви зи он н у ю ан те н н у точн о в це н тре , и счи тае тся охваче н н ы м те ле ве щ ан и е м , е сли су щ е ству е ткакой-н и бу д ь п е ре д атчи к, которы й н аход и тся в п рям ой ви д и м ости от ан те н н ы . Пе ре д атчи ки м огу т расп олагаться только точн о в це н тре квартала. С и гн ал расп ростран яе тся строго п о п рям ой. Если н а п у ти от п е ре д атчи ка к ан те н н е си гн ал ли ш ь касае тся н е боскрёба, си гн ал д оход и тд о ан те н н ы . Д ру ги х н е боскрёбов в город е н е т. К вартал, в котором у стан овле н п е ре д атчи к, счи тае тся охваче н н ы м те ле ве щ ан и е м . Програм м а д олжн а н айти м и н и м альн ое коли че ство н е обход и м ы х п е ре д атчи ков и у казатьм е ста и хразм е щ е н и я. Вход н ойфайл: INPUT.TXT Вы ход н ойфайл: OUTPUT.TXT Вре м я те сти рован и я: 20 се к/те ст Вход н ы е д ан н ы е :
Пе рвы м и зад аю тся д ва чи сла от 1 д о 14, которы е оп ре д е ляю т коли че ство кварталов в город е с зап ад а н а восток п о оси x и с ю га н а се ве р п о оси y соотве тстве н н о. Д але е и д е т чи сло от 1 д о 195, зад аю щ е е коли че ство кварталов, зан яты хн е боскрёбам и , п осле че го п е ре чи сляю тся п ары x, y коорд и н ат кварталов. К оорд и н аты кварталов отсчи ты ваю тся от1. Все чи сла во вход н ы х д ан н ы х разд е ляю тся п рои звольн ы м коли че ством п робе льн ы х си м волов. В город е су щ е ству е т хотя бы од и н квартал(д ом м э ра), н е являю щ и йся н е боскрёбом . Ре зу льтат Програм м а д олжн а н ап е чатать м и н и м альн ое н е обход и м ое чи сло п е ре д атчи ков, п осле че го п е ре чи сли ть коорд и н аты кварталов, в которы хон и д олжн ы бы тьу стан овле н ы . 2. Алгори тм ре ш е н и я. Алгори тм осн ован н а ре ку рси и . Н а кажд ом е ё ш аге н а карту стави тся ан те н н а и вы чи сляю тся кварталы , охваче н н ы е ве щ ан и е м . Если д о все х кварталов д оход и т си гн ал, то расп оложе н и е ан те н н зап ом и н ае тся, п ри у слови и , что д о э того н е н айд е н о расп оложе н и е с м е н ьш и м чи слом ан те н н . Д ля хран е н и я и н форм аци и о расп оложе н и и ан те н н , н е боскрёбов и кварталов, охваче н н ы х ве щ ан и е м , и сп ользу ю тся м н оже ства. К ром е того, и н форм аци я о расп оложе н и и н е боскрёбов д у бли ру е тся в м асси ве , что п озволяе ту скори тьработу п рограм м ы . 3. Програм м н ая ре али заци я program Town; {Автор - Ш и ряе в М .М .} const Nmax=14; {м акс. чи сло кварталов п о гори зон тали <=16} Mmax=14;
{п о ве рти кали <=16}
{м акс. чи сло кварталов}
Lmax=Nmax*Mmax; type TNum=1..Lmax; TSet=set of TNum; TRec=record
{ти п и н д е ксов кварталов} {ти п м н оже ства кварталов} {коорд и н аты квартала}
x,y:integer end; TArr=array[TNum]of TRec; var neb, ant:TSet; arr_neb:TArr; n,m, neb_num, ant_num:integer;
{м н оже ство н е боскрёбов} {м н оже ство ан те н н } {м асси в н е боскрёбов} {чи сло кварталов п о гори зон тали и ве рти кали } {чи сло н е боскрёбов} {чи сло ан те н н }
function GetIndex(x,y:integer):integer;{и н д е кс квартала} begin GetIndex:=(y-1)*Nmax + x end; procedure GetCoord(a:integer;var x,y:integer); {п ои ск коорд и н ат квартала} begin x:=(a-1) mod Nmax + 1; y:=(a-1) div Nmax + 1 end;
procedure Load;{загру зка карты } var f:text; i:integer; begin neb:=[]; Assign(f,'input.txt');Reset(f); read(f,n,m,neb_num); for i:=1 to neb_num do with arr_neb[i] do begin read(f,x,y); neb:=neb+[GetIndex(x,y)] end; Close(f) end; procedure Save;{зап и сьчи сла и расп оложе н и я ан те н н } var f:text; i,x,y:integer; begin Assign(f,'output.txt');Rewrite(f); writeln(f,'Чи сло ан те н н :'); writeln(f,ant_num); writeln(f,'К оорд и н аты ан те н н :'); for i:=1 to Lmax do if i in ant then begin
GetCoord(i,x,y); writeln(f,x,' ',y) end; Close(f) end; function Wave(a1,a2:integer):boolean; {п роход и тли волн а м е жд у кварталам и a1 и a2} const eps=0.01;{д оп у сти м ое отклон е н и е оту гла квартала} half=0.5-eps; var x1,y1,x2,y2,x,y,{коорд и н аты кварталов a1, a2 и п рове ряе м ого н е боскрёба} i,t:integer; k{коэ ффи ци е н тн аклон а п рям ой},p1,p2{точки п е ре се че н и я с н е боскрёбом }:real; begin Wave:=true; GetCoord(a1,x1,y1); GetCoord(a2,x2,y2); if x1=x2 then begin if y1>y2 then begin t:=y1; y1:=y2; y2:=t end;
for i:=1 to neb_num do with arr_neb[i] do if (x=x1)and(y1<=y)and(y<=y2)then begin Wave:=false; Exit end end else if y1=y2 then begin if x1>x2 then begin t:=x1; x1:=x2; x2:=t end; for i:=1 to neb_num do with arr_neb[i] do if (y=y1)and(x1<=x)and(x<=x2)then begin Wave:=false; Exit end end else begin k:=(y2-y1)/(x2-x1); for i:=1 to neb_num do with arr_neb[i] do begin k:=(y2-y1)/(x2-x1); p1:=k*(x-0.5-x1)+y1; {м ожн о зад е тьу гол} if (y-half
k:=(x2-x1)/(y2-y1); p1:=k*(y-0.5-y1)+x1; if (x-half
{п остави тьан те н н у new_a н а карту map} var x,y:integer; begin if not Cover(map,new_a) then for x:=1 to n do for y:=1 to m do begin new_a:=GetIndex(x,y); if not(new_a in map)and not(new_a in neb) then begin vspom:=vspom+[new_a]; inc(num); Step(map,new_a); vspom:=vspom-[new_a]; dec(num) end end else if num
begin a:=GetIndex(x,y); if not(a in neb) then begin vspom:=[a]; num:=1; Step([],a) end end end; begin Load; Think; Save end.
Работа вы п олн е н а в рам ках Фе д е ральн ойце ле войп рограм м ы «И н те граци я» п о н ап равле н и ю «Воссозд ан и е сту д е н че ски х н ау чн ы хш коли оли м п и ад » (п рое ктР0054). И зд ае тся п ри фи н ан совойп од д е ржке О О О ПФ «Д жу д и ».
Авторы : д оц. О .Ф.У скова, д оц. О .Д .Горбе н ко, п роф. А.И .Ш аш ки н
О ли м п и ад н ы е зад ачи п о п рограм м и рован и ю . Л у чш и е ре ш е н и я. Часть 1.: У че бн ое и зд ан и е / О .Ф.У скова, О .Д .Горбе н ко, А.И .Ш аш ки н – Ворон е ж: О О О ПФ «Д жу д и », 2001 – 76 с. О тп е чатан о в О О О ПФ «Д жу д и », ти раж. 200 э кз.