М И Н И СТ Е РСТ В О О Б РА ЗО В А Н И Я РО ССИ Й СК О Й Ф Е Д Е РА Ц И И
} fclose(in);
В О РО Н Е Ж СК И Й ГО СУ Д А РСТ В Е Н Н ЫЙ У Н И В Е РСИ Т Е Т
} // Function name // Description
: writeFile : writes output.txt file
// Return type // Argument
: void : int iRepeatMove
void writeFile(int iRepeatMove) {
О .Ф .У скова О .Д .Гор бенко
FILE *out; if ((out = fopen("output.txt", "wt")) == NULL) { fprintf(stderr, "Cannot open output file.\n");
О ЛИ М П И А Д Н ЫЕ З А Д А ЧИ П О П РО ГРА М М И РО В А Н И Ю . ЛУ ЧШ И Е РЕ Ш Е Н И Я Часть8
exitprog(); } else У чебное издание
{ if (iRepeatMove == MAXMOVES + 1) { fprintf(out, "Н и чья.\n"); } else { int iPlayerWin = iRepeatMove % 2 + 1; fprintf(out, "Иг р ок %ld в ы й г р ал. Х од %ld", iPlayerWin, iRepeatMove ); }
В О РО Н Е Ж – 2004
} fclose(out);
56
ББ К 32.97 У Д К 681.3
// Function name // Description
: exitprog : Waits while user presses Enter key
// Return type
: void
void exitprog() {
О ли мпи адны е задачи по пр ог р амми р ов ани ю. Лучш и е р еш ени я. В в ос ьми час тях. Час ть 8.: У чебное и здани е/ О .Ф .У с к ов а, О .Д .Гор бенк о – Вор онеж : Вор онеж с к и й г ос удар с тв енны й уни в ер с и тет, 2004 –с .74 Сбор ник с ос тав лен по матер и алам Всер ос си й с к ой с туденческ ой олимпи ады «Инфор маци онное модели р овани е и сов р еменны е к омпьютер ны е технолог и и»
scanf("%1c"); exit(1); }
// Function name // Description
: readFile : Reads file input.txt
// Return type ББК 32.97 У Д К 681.3
: void
void readFile() { FILE *in;
Печатаетс япо р ек омендаци и р едак ционно-и здательск ог о с ов ета фак ультета пр ик ладной математи к и , инфор мати к и и механик и Вор онежск ог о г ос уни вер си тета Р ецензент– к анди датфизи к о-математи чес к и х наук , доцент Л.С.М и лов ск ая
if ((in = fopen("input.txt", "rt")) == NULL) { fprintf(stderr, "Cannot open input file.\n"); exitprog(); } else
ISBN 5-815-047-0 © Вор онеж ск и й уни в ер с и тет © О .Ф .У ск ов а, О .Д .Гор бенк о
{ fscanf(in, "%ld", &n); char chr; for (int i=0; i < n * 2 ; i++) { fscanf(in, "%ld %ld %c", &aMoves[i][0], &aMoves[i][1], &chr); aMoves [i][2] = (chr=='+') ? true : false; }
55
Output.txt, в к отор ом к аждаяс тр ок а с одер ж итр езультаточер едной иг р ы . Пр имер в ходны х данны х 2 11+ 22+ 2212+ Пр имер в ы ходны х данны х Иг р ок 2 в ы и г р ал. Х од 3 2 11+ 22+ 12+ 22Пр имер в ы ходны х данны х Н и чья */ #include <stdio.h> #include <stdlib.h> #define NMAX 51 #define MAXMOVES 101 int n; char aMoves[2*NMAX][3]; //array for reading player moves from file bool aField[NMAX][NMAX]; //field on move i bool aField2[NMAX][NMAX]; //field on moves i+1, i+2... int iMinFirstRepeatFound;
54
П РЕ Д И СЛО В И Е И з д ание п од г от овле но по м ат е риалам Все российск ой ст уд е нче ск ой олим п иад ы «И нф орм ационное м од е лирование и совре м е нны е к омп ьют е рны е т е хнолог ии», п ровод им ой в соот ве т ст вии с п рик аз ом Минист е рст ва образ ования Российск ой Фе д е рации № 1187 от 25.03.2003 г од а. О но м оже т б ы т ь т ак же п оле з но ш к ольник ам ст арш их к лассов, ст уд е нт ам и учит е лям инф орм ат ик и об щ е образ оват е льны х и п роф ильны х уче бны х з аве д е ний. В п е рвой част и рассмат ривались з ад ачи п ре д ш е ст вовавш их олим п иад п о инф ормат ик е раз личног о уровня (ф ак ульт е т ск их, вуз овск их, м е жвуз овск их, ре г иональны х, ф е д е ральны х). Не к от оры е з ад ачи п риве д е ны с ре ш е ниями, в основном раз работ анны ми ст уд е нт ам и ф ак ульт е т а п рик лад ной м ат е м ат ик и и м е ханик и Вороне жск ог о униве рсит е т а, ст авш ими в свое вре мя п риз е рами эт их олим п иад . Во вт орой част и п ом им о з ад ач, п ре д ложе нны х на олим п иад ах раз личног о уровня, бы ли п ре д ст авле ны м ат е риалы п е рвог о (з аочног о) т ура ш к олы -олим п иад ы . В т ре т ье й част и п ре д ст авле ны мат е риалы Вт орой от к ры т ой ре г иональной ст уд е нче ск ой ш к олы - олимп иад ы п о п рог рамм ированию и к омп ьют е рному м од е лированию. Че т ве рт ая част ь д оп олняе т их анализ ом ре з ульт ат ов п е рвог о т ура и лучш им и ре ш е ниями п обе д ит е ле й п е рвог о т ура. В п ят ой част и п ре д ст авле ны ре з ульт ат ы вт орог о т ура Вт орой от к ры т ой ре г иональной ст уд е нче ск ой ш к олы -олим п иад ы по п рог рамм ированию и к омп ьют е рному м од е лированию и из бранны е ре ш е ния з ад ач. В ш е ст ой част и п од ве д е ны ит ог и Ре г иональной ст уд е нче ск ой олим п иад ы по п рог рам мированию, п освящ е нной 85-ле т ию Вороне жск ог о г осуниве рсит е т а. Се д ьм ая част ь п од г от овле на п о м ат е риалам п е рвог о т ура Т ре т ье й от к ры т ой ре г иональной ст уд е нче ск ой ш к олы -олим п иад ы по п рог рамм ированию и к омп ьют е рному м од е лированию. Наст оящ ая восьм ая част ь п освящ е на з ад ачам , к от оры е п ре д лаг ались на т ре т ье м т уре Все российск ой ст уд е нче ск ой олим п иад ы «И нф орм ационное м од е лирование и совре м е нны е к омп ьют е рны е т е хнолог ии», к от орая вп е рвы е п ровод илась в г .Вороне же в 2003 г од у.
3
В о ро не ж с к о м у го с у дарс т ве нно м у
Задача3. Ф иш ки
у ниве рс ит е т у – 85 л е т
А в тор р еш ени я – член ж юр и , член О лимпи й с к ог о с ов ета, аспи р ант фак ультета ПМ М ВГУ А ндрей Я куб енко
Создани е и с танов ление Вор онежс к ог о уни вер си тета тес но с в язано с с удьбой Ю р ьев ск ог о (Д ер птск ог о) унив ер с и тета, отк р ы тог о ещ е в 1802 г оду по ук азу импер атор а А лек сандр а I. В мар те 1918 г ., к ог да пос ле ок к упаци и Э с тонии в ой с к ами к ай зер ов ск ой Гер мании местны е в ласти пов ели лини ю на пр ев р ащ ени е Ю р ьев ск ог о (Д ер птс к ог о) уни в ер с итета в немецк ое учебное зав едение, уни вер си тет ок азалс я в к р ити ческ ом полож ении . В и юле и с ентябр е 1918 г . изД ер пта (тепер ь Тар ту) с пеци альны ми поездами в Вор онеж пр ибы ло 39 пр офесс ор ов , 45 пр еподав ателей , 43 челов ек а обс луж и в ающ ег о пер с онала и ок оло 800 студентов . 12 ноябр я1918 г ода в Вор онеж ск ом г ос удар с тв енном уни вер с итете на четы р ех фак ультетах - медицинс к ом, физик о-математи чес к ом , и стор и к офи лолог ическ ом и юр и ди чес к ом - начали с ь учебны е занятия. Ж и знес пос обность уни вер с итета пр ов ер и ла Вели к ая О течес тв енная в ой на 1941-1945 г г . В пер в ы е же дни на фр онт уш ли почти все с туденты , более 60 пр еподав ателей . 25 янв ар я1943 г . Вор онеж бы л ос в обож ден отфаш и стск и х захв атчик ов, а уж е в ав г усте началас ь р еэ вак уаци яуни вер с и тета. Сег одня на 16 фак ультетах обучаетс я с в ы ш е 18 ты с яч студентов, с луш ателей и аспир антов . Ф ак ультет ПМ М ос нов ан в 1969 г оду на базе математи к омехани чес к ог о фак ультета. В ег о с оздании пр и ни мали участи е и зв ес тны е учены е пр офес сор а М .А . К р ас нос ельск и й , С.Г. К р ей н, Д .Д . Ив лев . Н а базе фак ультета бы ли пр ов едены тр и О тк р ы ты х р ег иональны х с туденческ и х олимпи ады по пр ог р амми р ов ани ю и к омпьютер ному моделир ов ани ю, и в пер в ы е пр ов одитс я Вс ер ос си й ск аяолимпи ада.
/* Иг р а с фи ш к ами пр оис ходитна поле N на N к леток (в пр имер е ни же N=4). В ней учас тв уют дв а и г р ок а. Пер в ы м счи таетс яиг р ок , совер ш ающ ий пер в ы й
ход. Во в р емяи г р ы и г р ок мож етли бо помести ть чер ную фи ш к у
в любое место
доск и , ли бо снять с ущ еств ующ ую, что пр и водит к
р азли чны м с хемам р ас станов к и . Ес ли очер едная полученная с хема (и ли ее р азвор от на 90, 180, 270 г р адус ов ) пов тор яетс я в о в р емя и г р ы , то и г р ок получи в ш и й так ую с хему пр ои г р ы вает, а др уг ой иг р ок в ы иг р ы вает. Иг р а зак анчи в аетс яв ничью после 2N ходов , ес ли не бы ло повтор яющ и хсяс хем в ходе иг р ы . Р асс мотр им в к ачес тв е пр имер а с ледующ и е 5 с хем : .O.O
. .O.
....
O...
O.O .
..O.
.O..
O..O
. OO .
.O..
..O.
.O..
.O O.
O..O
.O..
.O..
O .O.
...O
....
..O.
Ес ли пер ваяс хема бы ла получена р анее, то любаяи з 3 с ледующ и х с хем будетзавер ш ать и г р у, а пос ледняянет. Входны е данны е Во в ходном фай ле Input.txt к аж дая и г р а из с ер ии и г р опис ы ваетс я набор ом с тр ок : пер ваяс одер ж и т р азмер поля(2<=N<=50), в с ледующ и х 2N с тр ок ах с одер жатс яходы , изк отор ы х в озможно не в се нужны . К аж ды й ход с остоити зк оор динатк в адр ата (от1 до N) и следующ ег о
П О Л О Ж ЕН И Е
чер ез пр обел сим вола ‘+’ и ли ‘-‘ , к отор ы й означает установк у и ли снятие
о В с е ро с с ийс к о й с т у де нче с к о й о л им пиаде по инф о рм ат ик е
фи ш к и соответств енно. Вс е ходы пр ав и льны е. Вв од данны х зак анчи ваетс я
2003 го да
нулем. Вы ходны е данны е
О БЩ ИЕ ПО ЛО Ж ЕН ИЯ
4
Вы ходны е данны е должны
бы ть помещ ены
53
в
тек стов ы й
фай л
while(s[0]!='#') { strcpy(prog2[p2ns++],s); fscanf(fi,"%s",&s); } // strcpy(prog2[p2ns++],"end_of_2"); maxp1i=0; maxp2i=0; maxq=0; int q=0,n=0; int i,j; for(i=0;i
maxq) { maxq=q; maxp1i=i; maxp2i=j; } } for (i=0;i<maxq;i++) { fprintf(fo,"%s ", prog1[maxp1i+i]); }
Всер ос сий ск ая студенческ ая оли мпиада по и нфор мати к е пр ов одитс я Вор онежс к и м г ос удар с твенны м уни в ер с итетом в с оответс тв ии с Пр ик азом М и нобр азов ани яР Ф № 1187 от25.03.2003 г . О лимпиада напр авлена на р азви тие твор ческ ой ак ти в нос ти студентов , ор иентаци ю учащ ей с ямолодежи на р еш ени е задач и нфор мати зации научны х и с следовани й в с фер е естес тв енны х наук , а так же на в ы яв ление наи более талантли в ы х студентов в облас ти инфор маци онног о и математичес к ог о моделир ов ани яфизи ческ и х, хими чес к и х, би олог и ческ и х, э к олог и чес к и х, г еолог ическ и х, г еог р афическ и х пр оцес с ов , пр оек ти р ов ани я и р азр аботк и с оответс тв ующ и х пр ог р аммны х пр одук тов , ис пользов ани я сетев ы х и мультимеди й ны х к омпьютер ны х технолог ий , а так же в облас ти и нфор маци онног о моделир ов ани яв ли нг в истик е, юр и с пр уденции . М атер и алы оли мпи ады (нов ости , с пис к и участник ов , задани я тур ов , р езультаты и др .) р азмещ аютс я на с тр ани цах Web-с ай та www.ru-studolimp.nm.ru . ПО Р Я Д О К ПР О ВЕД ЕН ИЯ О лимпиада пр оводится в дв а э тапа. Пер в ы й - в телек оммуник аци онном р ежи ме (25 сентябр я 2003 г ода в 15 часов ), втор ой (ос нов ной ) - на лабор атор ной базе Вор онежск ог о уни вер с итета (ноябр ь 2003 г ода). В олимпи аде мог ут пр инять учас тие с туденты любы х к ур с ов любы х в узов Р ос с ий ск ой Ф едер ации . О тк р ы ти е пер вог о э тапа оли мпи ады намечено на 25 с ентябр я2003 г ода. О н будет пр оводитьс яв телек оммуни к аци онном р ежи ме, пр инять участи е в нем мог утв се ж елающ и е. К о втор омуэ тапу, к отор ы й будетпр оходи ть в Вор онеже, будутдопущ ены победи тели пер вог о э тапа. П р едус мотр ена р абота дв ух с ек ций : - с ек ци япр ог р амм ир ов анияи к омпьютер ног о модели р ов ания; - с ек ци япр и к ладног о пр ог р аммног о обеспечени я. Итог и оли мпиады будутподв оди тьс япо номи нациям: - пер вок ур с ник и ; - с туденты , для к отор ы х и нфор мати к а является пр офи ли р ующ ей дисциплиной ; - с туденты , для к отор ы х и нфор матик а являетс я общ еобр азовательной дисциплиной ;
fclose(fi); fclose(fo); }
52
5
- с туденты техни ческ и х в узов ; - с туденты в оенны х в узов ; - с туденты юр и ди ческ и х и г уманитар ны х специ альностей ; - с тудентк и . Вс тупительны й в знос дляучастияв олимпиаде не тр ебуетс я. В пер в ом э тапе мог утпр и нять участие в се желающ и е. К участи ю во в тор ом э тапе будут допущ ены с туденты , пок азав ш и е лучш и е р езультаты в пер в ом э тапе. Р еш ени е о допуск е к участи ю в о в тор ом тур е пр инимаетс я ор г к омитетом олимпи ады . У час тни к и оли мпиады пр ослуш ают лек ци и ведущ и х учены х по с овр еменны м пр облемам наук и и пр имут участи е в р аботе к р уг лог о стола "К омпьютер ны е технолог ии в обр азов ани и ". Т очная дата пр ов едени я в тор ог о э тапа оли мпи ады опр еделяетс я ор г к оми тетом и ог лаш аетс я чер ез СМ И и в Интер нете на сай те www.ru-stud-olimp.nm.ru .
for i := words3 downto 1 do write (ws3[i],' '); writeln; until w = '.'; end. Пр и в едем так же р еш ение, пр едлож енное участник ом олимпи ады Б аб анины м
Д м ит рием ,
студентом
техни ческ ог о уни в ер с и тета. #include <stdio.h> #include <string.h> int main() {
ПО Д ВЕД ЕН ИЕ ИТ О ГО В И Н А ГР А Ж Д ЕН ИЕ ПО БЕД ИТЕЛЕЙ
FILE*fi,*fo; char prog1[100][31], prog2[100][31];
Подв едени е и тог ов Вс ер ос сий ск ой студенческ ой олимпи ады по инфор матик е пр ов одитс яор г к омитетом оли мпиады . О р и г и нальны е р еш ени я будут опублик ованы в с бор ни к е "О ли мпиадны е задачи по пр ог р ам мир ов ани ю. Лучш ие р еш ени я". Победители оли мпиады наг р аждаютсяг р амотами и пр изами . Н аш и р ек в и зиты : 394693 Вор онеж , У ни в ер ситетск ая пл., 1. Кафедр а математи ческ ог о обес печени я Э ВМ фак ультета пр и к ладной математик и , инфор матик и и механи к и (ауд.8). О р г к омитет Всер осси й с к ой студенчес к ой олимпи ады по инфор матик е. E-mail: [email protected] URL: www.ru-stud-olimp.nm.ru Т елефоны : (0732) 789-698, 789-266
char s[31]; int p1ns=0, p2ns=0; int maxp1i, maxp2i; int maxq; fi=fopen("input.txt","r"); fo=fopen("output.txt","w"); fscanf(fi,"%s",&s); p1ns=0; while(s[0]!='#') { strcpy(prog1[p1ns++],s); fscanf(fi,"%s",&s); } // strcpy(prog1[p1ns++],"end_of_1"); p2ns=0; fscanf(fi,"%s",&s);
6
51
Т амбовс к ог о
г ос удар с тв енног о
while true do begin В С ЕРО С С ИЙС КАЯ С ТУДЕНЧЕСКАЯ О Л ИМ П ИАДА
if W = '#' then break;
«ИНФ О РМ АЦ ИО ННО ЕМ О ДЕЛ ИРО В АНИЕИ С О В РЕМ ЕННЫ Е
inc (words2);
КО М П Ь Ю ТЕРНЫ ЕТЕХ НО ЛО ГИИ» 2003 ГО ДА:
ws2[words2]:=w;
Ц ИФ РЫ И Ф А КТЫ
readword; end; В
readln;
течение
сентябр я – ноябр я 2003 уни в ер си тете
пр оходи л
г ода
тр ети й
в
тур
Вор онежс к ом
READWORD;
г ос удар с твенном
Всер ос сий ск ой
for i := 1 to words2 do begin
с туденчес к ой оли мпи ады по инфор мати к е «Инфор мационное модели р ов ание
for j := 1 to words1 do begin
и с ов р еменны е к омпьютер ны е технолог и и» (пр ик аз М инв уза Р Ф № 1187 от 25.03.03). О ли мпи ада в к лючала дв а э тапа. в пер в ом (заочном) э тапе, к отор ы й
t[i,j] := 0;
пр оходи л в телек оммуник аци онном р еж и ме 25 – 26 сентябр я 2003 г ода,
end; end;
мог ли пр и нять учас ти е в се желающ и е студенты любы х в узов Р осс и и и любы х
for i := 1 to words2 do begin
фор м обучения, сор ев нов алос ь ок оло 700 студентов из 169 в узов наш ей
for j := 1 to words1 do begin
с тр аны . Победители
if ws2[i] = ws1[j] then begin
пер вог о э тапа - 55 и ног ор одни х с тудентов
(и з
К али нинг р ада, Волог ды , М оск в ы , К азани , Чебок сар , К ир ова, Сар анс к а, Я р ос лав ля, Волг ог р ада, Т улы , Т амбова, Р ос това-на-Д ону, Владими р а,
t[i,j]:=max(i-1,j-1)+1;
М аг ни тог ор ск а, Белг ор ода, Санк т-Петер бур г а, Ст. О ск ола, Пензы , Т омс к а,
end;
Став р ополя, О р енбур г а, М и чур инск а, М и нск а) и 45 в ор онеж ск и х с тудентов
end;
Вор онежск ог о
г ос удар ственног о
унив ер си тета,
Вор онежс к ог о
end;
(из
i := words2+1;
г ос удар с твенног о
техни чес к ог о
j := words1+1;
г ос удар с твенног о
педаг ог и чес к ог о
m := max(i-1,j-1);
г ос удар с твенной технолог ичес к ой ак адеми и , Вор онежс к ог о г ос удар с тв енног о
words3 := 0;
ар хи тек тур но-с тр ои тельног о унив ер с и тета, Вор онежск ой г ос удар с тв енной
while m <> 0 do begin
меди ци нск ой ак адемии , Вор онеж ск ог о института М ВД Р Ф , Вор онежс к ог о
Вор онежс к ог о
уни вер с итета,
в оенног о
Вор онежс к ог о
в оенног о
ws3[words3] := ws2[im];
авиаци онног о инженер ног о инс ти тута) - бы ли пр и г лаш ены
на втор ой
i := im;
(ос нов ной ) э тап. О н пр оходи л 20 – 23 ноябр я 2003 г ода в Вор онеж ск ом
j := jm;
уни в ер с итете.
m := max(i-1,j-1);
К оличество учас тни к ов -студентов пр едстав лено в табли це. № Вузы
50
р адиоэ лек тр оник и ,
Вор онеж ск ой
inc (words3);
end;
института
уни вер с итета,
7
втор ог о
(основ ног о)
э тапа
К ол-в о
1
К алининг р адск ий г ос удар ственны й уни в ер с и тет
3
2
Волог одс к и й г ос удар ств енны й уни в ер с итет
2
4
М ос к ов ск ая г ос удар с тв енная пр ибор ос тр оени яи и нфор матик и К азанск ий г ос удар ственны й уни в ер си тет
5
Чув аш с к и й г ос удар с тв енны й уни вер с итет
3
ак адеми я
max_ : byte; begin max_ := 0;
3
for i2 := 1 to m do begin
2
for j2 := 1 to n do begin
1
if t[i2,j2] > max_ then begin
7
Чув аш с к и й г ос удар с тв енны й педаг ог ическ ий уни вер с итет М ос к ов ск аяг ос удар с твеннаяналог ов аяак адемия
1
8
Вятск ий г ос удар ственны й уни вер си тет
3
9
М ор дов с к ий г ос удар ственны й уни в ер ситет
3
10
Я р ослав ск и й г ос удар ств енны й уни в ер с итет
1
end;
11
Волг ог р адс к и й г ос удар с тв енны й уни в ер с итет
1
max := max_;
12
Т ульс к и й г ос удар с тв енны й уни вер с итет
2
13
Т амбовск ий г ос удар с твенны й техни чес к и й уни вер си тет
6
14
Д онск ой г ос удар ственны й техни чес к ий уни в ер ситет
1
15
Влади мир ск и й г ос удар ств енны й уни в ер с итет
1
16
М аг нитог ор с к и й г ос удар ств енны й уни в ер с итет
2
17
Бр янс к и й г ос удар с тв енны й техни ческ и й уни в ер с итет
1
repeat
1
words1 := 0;
6
max_ := t[i2,j2];
1 im := i2; jm := j2; end; end;
end; begin assign (input, 'input.txt'); reset (input); assign (output, 'output.txt'); rewrite (output); readword;
1
22
М и чур и нск ий г ос удар ственны й педаг ог ическ ий уни вер с итет Белг ор одс к ая г ос удар ственная технолог и ческ ая ак адеми я Санк т-Петер бур г ск ий г ос удар ств енны й политехни чес к и й унив ер си тет Стар оос к ольс к ий фили ал М оск ов с к ог о г ос удар ственног о и нститута с тали и с плавов Пензенс к ий г ос удар с твенны й уни вер с и тет
23
Т омск ий г ос удар ств енны й уни в ер ситет
1
24
Став р опольск ий г ос удар с тв енны й уни в ер ситет
2
end;
25
О р енбур г ск и й г ос удар ственны й унив ер си тет
2
readln;
26
М и нск и й г ос удар ств енны й уни в ер с итет
1
18 19 20 21
2
while true do begin if W = '.' then exit; if W = '#' then break;
4 3
inc (words1); ws1[words1]:=w; readword;
ReadWord; words2 := 0;
8
49
фак ультет пр и к ладной математи к и , инфор мати к и и механи к и математи чес к ий фак ультет
if eof (input) then ch := _eof else if eoln (input) then begin ch := _eoln; readln; end else read (ch); end; procedure readword; begin 28
repeat nextch; until not (ch in [_eoln, ' ', '
']);
w := '';
29 30
if Ch = '#' then begin
31
w := ch; end; if Ch = '.' then begin w := ch; exit;
фак ультетк омпьютер ны х наук
2
фи зи чес к и й фак ультет
2
фак ультетг еог р афи и и г еоэ к олог и и
2
би олог о-почв енны й фак ультет
3
юр и ди чес к и й фак ультет
1
фак ультетж ур нали стик и
2
э к ономи чес к и й фак ультет
3
Вор онежс к и й уни в ер с итет
while not (ch in [_eoln, _eof, ' ', ' ']) do begin w := w+ch;
г ос удар с тв енны й
Вор онежс к ая г ос удар с твенная ак адеми я Вор онежс к и й г ос удар с тв енны й с тр оительны й уни в ер ситет
педаг ог ичес к ий технолог и ческ ая ар хитек тур но-
Вор онежс к аяг ос удар ств еннаямедици нск аяак адеми я
2 2 1
34
Вор онежс к и й в оенны й инс титутр ади оэ лек тр оник и
2
35
Вор онежс к и й институт
2
в оенны й
ави ационны й
техничес к ий
3
33
Всег о
end;
2
Вор онежс к и й г ос удар с тв енны й уни в ер с итет Вор онежс к и й инс титутМ ВД Р Ф
32
exit;
12
5 3
инженер ны й
100 учас тник ов . О ргк о м ит е т
Пр едседатель ор г к оми тета – БО Р ИСО В Ив ан Иванов ич, р ек тор Вор онежс к ог о г ос уни вер си тета, док тор филос офс к и х наук , пр офес с ор ;
nextch;
Зам. пр едс едателя- Ш А Ш К ИН А лек с андр Ив анови ч, дек ан фак ультета
end;
ПМ М , док тор фи зи к о-математи ческ и х наук , пр офес сор ;
end;
ТО ЛСТ О БР О В А лек с андр Пав лови ч, доцент, пр ор ек тор Вор онеж ск ог о function max (m, n : integer) : byte;
г ос уни вер си тета по и нфор мати зации ; А ЛГА ЗИН О В Э дуар д К онстантинови ч, дек ан фак ультета
var
48
9
к омпьютер ны х наук , док тор физик о-математи чес к и х наук , пр офес с ор ; БЛИЗН Я К О В Н ик олай М и хай лови ч, начальник отдела научны х ис следований , доцент;
if (nres > 0) then for k := 0 to nres-1 do write(fo, res[k], ' '); writeln(fo); b := ReadTest;
А Н Т ИПО В Сер г ей А натольев ич, р ек тор ВО ИПКР О , док тор фи зи к оматемати чес к и х наук , пр офесс ор ;
end; close(fi); close(fo);
У СК О ВА О льг а Ф едор овна, доцентк афедр ы математичес к ог о
end. Св ой в ар и ант пр едложил В ячеслав Ёж кин, студент Волог одс к ог о
обес печени яЭ ВМ ВГУ , к анди даттехни чес к и х наук ; ГО Р БЕН К О О лег Д анилов и ч, зав .к афедр ой математи чес к ог о
г ос удар с твенног о педаг ог и чес к ог о уни вер с итета, заняв ш и й в тор ое место по
обес печени яЭ ВМ ВГУ , к анди датфи зик о-м атематичес к и х наук
и тог ам олимпи ады .
Д А Н ЬШ ИН Бор ис Ив анови ч, ди р ек тор к омпани и «Инфор мсв язьЧер ноземье»
{Поис к мак с . подпос ледов ательнос ти , не обязательно встр ечаю щ ей с яв и с ходны х
ЛА ПЫ ГИН Д ми тр ий Р удольфови ч, зам. г енер альног о ди р ек тор а ЗА О "Р ЕТ", г .Вор онеж
тек с тах целик ом (подр яд) } const _max=30;
Ж ю ри Пр едс едатель ж юр и
- ГО Р БЕН К О
О лег
_maxwords=100; Д ани лови ч, зав . к афедр ой
математи чес к ог о обеспечени я Э ВМ ВГУ , к анди дат фи зик о-математи ческ и х наук .
_eof=#13; _eoln=#10; type
Зам.пр едс едателя- У СК О ВА О льг а Ф едор овна, доцентк афедр ы
tWord = string[_max];
математи чес к ог о обеспечени яЭ ВМ ВГУ , к андидаттехническ и х наук . Члены ж юр и :
ws1, ws2, ws3 : array[1.._maxwords] of tword;
Т Ю К А ЧЕВ Н ик олай А р к ади еви ч, зав .к афедр ой пр ог р амми р ов ани я и инфор маци онны х технолог и й , к анд. фи з.-мат.наук , доцент; к анди датфизи к о-математи чес к и х наук , доцент; М и хаи л
Влади мир ов ич,
Вади м
М итр офанови ч,
w : tword; i, j, i2, j2 : integer;
пр еподаватель
к афедр ы
пр ог р ам мир ов ани яи инфор маци онны х технолог ий ВГУ ; М ЕЛЬН ИК О В
words1, words2, words3 : integer; Ch : char;
М А Х О Р Т О В Сер г ей Д митр иев ич, доцентматематическ ог о фак ультета, БА К ЛА Н О В
var
пр еподаватель
im, jm : integer; t : array[1.._maxwords, 1.._maxwords] of byte;
к афедр ы
m : byte;
математи чес к ог о обеспечени яЭ ВМ ВГУ ; procedure nextch; begin
10
47
О л им пийс к ий с о ве т :
inc(no); k1 := k1+1;
- Поляк ов А ндр ей (аспи р ант пер вог о г ода обучени я, сор осов ск ий студент,
k2old := k2;
неоднок р атны й победи тель меж в узовс к и х с туденчес к и х олимпиад, пр и зер
k2 := tk+1;
четв ер ть-фи нала ми р овог о пер в енств а по пр ог р аммир овани ю , отли чник
FindWord(k1, k2);
учебы ),
k2 := k2old;
-
dec(no);
Ефр емов
М ак с им
(аспи р ант пер в ог о
г ода
обучени я, победи тель
фак ультетск ой с туденчес к ой оли мпиады , отли чник учебы ),
end else begin
- М хи тар ян Луси не (ас пи р антк а пер вог о г ода обучени я, победи тель
if (no > nres) then begin
уни в ер с итетск ой студенчес к ой олимпи ады ),
res := o;
- Вахтин А лек сей (ас пир ант фак ультета к ом пьютер ны х наук , победи тель
nres := no;
фак ультетск ой с туденчес к ой оли мпиады ),
end;
- Я к убенк о А ндр ей
inc(k1);
победи тель меж в узовс к и х с туденчес к и х оли мпи ад, пр изер четв ер ть-фи нала
end;
(аспи р ант пер вог о г ода обучения, неоднок р атны й
ми р овог о пер в енс тв а по пр ог р аммир овани ю, отли чник учебы );
end;
-
end;
Плахотны й Влади ми р (студент 4 к ур са фак ультета ПМ М , пос тоянны й
учас тник олимпиад).
var
П о рядо к и про грам м а про ве де ния
b : boolean; k : byte;
Тр ети й тур Вс ер осс ий с к ой с туденческ ой оли мпи ады пр оходил в дв а
begin
э тапа в
сентябр е – ноябр е 2003 г ода. Пер в ы й
э тап пр ов оди лс я в
clrscr;
телек оммуник аци онном р ежи ме 25-26 сентябр я 2003 г ода, в тор ой – на
assign(fi, 'input.txt');
лабор атор ной базе Вор онежс к ог о г ос унив ер с итета 20-23 ноябр я2003 г ода.
assign(fo, 'output.txt');
У частник ам олимпи ады бы ло пр едложено 4 задания, с уть к отор ы х в
reset(fi); rewrite(fo);
р азр аботк е инфор маци онной модели пос тав ленной пр облемы , р азр аботк а на
b := ReadTest;
пр ог р аммир ов ани як онк р етной опер аци онной с р еды .
ее основ е алг ор и тма р еш ения и с оздание пр ог р амм ы в одной и з с и стем while b do begin
Пр ог р амма и р ег ламентпр оведени яолимпиады следующ и е
nres := 0;
20 ноя бр я , четвер г Д еньзаездаучастников
no := 0;
Пр ожи в ание и ног ор одни х участни к ов
- в общ еж ити и Вор онежс к ог о
FindWord(0, 0);
46
11
областног о и нс титута пов ы ш ени я к в алифи к ации р аботни к ов обр азов ани я
end;
(ВО ИПК Р О , ул. Бер езов аяР ощ а, 54): 4-мес тны е номер а, стоимость одног о
end;
места - 60 р ублей в с утк и . Пр оезд к ВО ИПКР О (до ос танов к и "Бер езовая
ReadTest := true;
Р ощ а"): от
end; Ц ентр альног о
ав тов ок зала
автобус
-
№ 9к с ;
end;
из центр а г ор ода (к и нотеатр "Спар так ") - автобус ы № 9к с , 9а, мар ш р утное так с и
№
3,25а,
36,
42,
50,
70а
(наи более
подходящ и й );
function FindWordInT2(st : wword; start : byte) : byte;
от железнодор ож ног о в ок зала - ав тобус № 9а, мар ш р утное так си № 19;
var i : byte;
отЛев обер ежног о ав товок зала - мар ш р утное так с и № 16а.
begin
Спи ск и участник ов находилис ь у в ахтер а инсти тута и к оменданта.
FindWordInT2 := 255;
У частни к ов олимпиады , пр и езжающ и х поездами и з М оск в ы
for i := start to n2-1 do
М ос к в у), в стр ечали
(и ли чер ез
пр едстав ители ор г к оми тета 21 ноябр я с ав тобус ом.
У частни к и бы ли достав лены к мес тупр ожи вани я.
if (st = t2[i]) then begin FindWordInT2 := i;
21 ноя бр я , п я тница(ауд.435 г л.кор п .)
break;
10:00 – 11:00 Э к с к ур с ияв м узей р едк ой к ниг и
end;
11:00 – 12:00 Р ег истр аци яи ног ор одни х учас тник ов оли мпи ады
end;
12:00 – 12:30 О бед (для иног ор одни х участник ов – за с чет ор г к оми тета)
procedure FindWord(k1, k2 : byte);
12:00 – 12:30 Р ег и стр аци явор онеж ск и х участни к ов
var tk, k2old : byte;
12:30 О ткр ы тие втор ог о этап а Вр учение сер ти фи к ата участия и
begin
с ув енир ов .
write(k1, ' ');
11:00 – 12:45 Вы с тав к а-пр одаж а к ни г
к омпьютер ной
тематик и
издательс к ог о дома «Питер »(дляучастни к ов оли мпиады с к и дк а 20%)
while (k1 <= n1) do begin if (k1 <= n1-1) then begin
12:45 – 13:15 Р ас пр еделение учас тник ов по к омпьютер ны м к ласс ам
tk := FindWordInT2(t1[k1], k2);
13:15 – 13:30 Знак омс тв о участни к ов с о с в оими р абочими местами
while (k1 <= n1-1) and (tk = 255) do begin
13:30 – 17:00 Р абота над олимпи адны ми заданиями
inc(k1);
17:10 – 17:30 У жи н (для и ног ор одни х участник ов – за с чет
tk := FindWordInT2(t1[k1], k2);
ор г к оми тета)
end;
18:00 – 22:00 О тк р ы тое тести р ов ание р еш ени й учас тни к ов
в пр ис утс тви и
end; if (k1 <= n1-1) then begin
22 ноя бр я , суббота(ауд.480 нов.кор п .)
12
o[no] := t1[k1];
45
9:00 – 9:30 Зав тр ак
(для иног ор одни х участник ов – за с чет
ор г к омитета)
function ReadTest : boolean;
9:30 – 12:30 О бзор ная э к ск ур с и я по г .Вор онеж у (оплачи ваетс я
var
ор г к омитетом)
ch : char; p : ^ttext;
12:30 – 13:30 Р азбор оли мпи адны х заданий
k : byte;
13:30 Подведение и тог ов олимпи ады , наг р аж дени е победи телей , зак р ы ти е олимпиады .
begin
14:30 О бед (дляи ног ор одни х участни к ов – за с четор г к омитета)
for k := 0 to 100 do begin
15:00 Э к с к ур си яв музей и стор и и ВГУ
t1[k] := ''; t2[k] := '';
15:40 Зак р ы тие олимпиады . Подведение и тог ов к онк ур с ов на лучш ую
end; k := 0; p := @t1;
э мблему олимпи ады , пр и ветс тв ие к ом анды , э к спр ес с -опр ос а. Пр ив етс тв ие
read(fi, ch);
с понс ор ов участник ам и пр изер ам оли мпи ады .
while (ch in [' ', #10, #13]) do read(fi, ch);
23 ноя бр я , воскресенье
if (ch = '.') then begin
Д ень отъезда участник ов
ReadTest := false;
О с но вны е ит о ги о л им пиады
end else begin while (not eof(fi)) and (p <> nil) do begin
По итог ам олимпиады в ы яв лены наи более талантли в ы е студенты ,
while ((ch in [' ', #10, #13]) and (not eof(fi))) do read(fi, ch);
с пос обны е э ффек ти в но р еш ать задачи и нфор мационног о модели р ования с
if (ch = '#') and (p = @t1) then begin
пр именением сов р еменны х к омпьютер ны х технолог ий . Н еобходимо отметить
p := @t2; n1 := k;
в ы с ок ий
k := 0;
с ор евновав ш и хсястудентов и отс утстви е чи сто нулев ы х р езультатов .
read(fi, ch)
ур овень подг отовк и
по пр ог р амми р ованию
у больш инств а
Ф инанс овая поддер жк а ми нистер ств а обр азования
end else if (ch = '#') and (p = @t2) then begin
Р Ф (пр ик аз
№ 2730 от 25.06.03), р ек тор ата Вор онеж ск ог о г ос уни в ер ситета, фак ультета
n2 := k;
пр ик ладной математик и , инфор м ати к и и механик и , спонс ор с к ая помощ ь
break;
р азли чны х ор г ани заци й позв олили наг р ади ть вс ех участник ов ос нов ног о
end else begin
э тапа. Каж ды й изни х получи л:
while not (ch in [' ', #10, #13]) do begin p^[k] := p^[k]+ch;
1.
Сер тифи к ат, подтвер ж дающ ий ег о учас ти е в о Вс ер ос сий с к ой
олимпи аде.
read(fi, ch);
2.
end;
К ни г у пр оф. К ар пачева М .Д . «Вор онежс к и й
уни вер с итет»,
и зданную к 85-лети ю ВГУ , к отор ое отмечалось в э том г оду(цена 120 р уб).
inc(k);
44
13
У чебное
3.
пос оби е,
и меющ ее
г р иф
М инв уза
РФ
readln(st);
«П р ог р аммир ов ани е на Паск але: задачник »(ав тор ы – пр еподаватели к афедр ы
if st[1]='#' then exit;
математи чес к ог о обеспечения Э ВМ фак ультета ПМ М ВГУ
val(st,n,er);
У ск ова О .Ф .,
Бак ланов М .В., Вор онина И.Е., Гор бенк о О .Д ., Вощ и нск аяГ.Э ., М ельник ов
rec(1);
В.М ., О г ар к ова Н .В. (цена 65 р уб)).
work;
4.
Ж ур нал с ди ск ом «Д омаш ний к омпьютер »(цена 55 р уб).
end;
5.
К ни г и и здательств а «БХ В–Петер бур г » и и здательск ог о дома
BEGIN
«П итер -Вор онеж » (цена 80 – 250 р уб).
init;
6.
О тк р ы тк и с ви дами г . Вор онежа
7.
Д и ск еты
work; END.
К р оме тог о, 36 участник ов в ер хней части и тог ов ой таблицы бы ли наг р аж дены с пециальны ми пр изами .
Н и же пр и в оди тс я р еш ение с тудента 4 к ур са фак ультета ПМ М ВГУ
Пер в ы е тр и места заняли с туденты изр азны х г ор одов . А бсолютны м победителем
олимпи ады
стал
Задача2. В ы бор ы
Чер ны х Сер г ей
из Калининг р адск ог о
уни в ер с итета. О н набр ал 21 балл. Н а втор ое мес то в ы ш ли семь студентов: Си дор енк о Станис лав (Вор онежс к и й г ос унив ер с итет) – 17 баллов , Ежк и н
Д м ит рия В ы ро ст ко ва, победителяТ р етьей отк р ы той р ег и ональной ш к олы олимпи ады
по пр ог р амми р ов ани ю и
с типендиатинфор маци онной к омпани и «Инфор мс в язь-Чер ноземье» {
Вячес лав (Волог одс к и й педуни в ер с итет) – 16 баллов , М и хай лов А нтон
Vyrostkov Dmitry Andreevich
(К алини нг р адск и й
4 kurs, AMM, VSU
г ос уни в ер с итет) – 16
баллов , Луг ов ов
А лек с андр
(М оск ов ск аяг ос удар ств еннаяак адеми япр и бор ос тр оенияи инфор матик и ) – 14 баллов , Х адиев К ами ль (К азанс к и й г ос уни вер с и тет) – 14 баллов , Ш итов А ндр ей
(Чуваш с к ий
Task #2 }
г ос уни вер си тет) – 14 баллов , Ш аталов М и хаи л
(Вор онежск и й г ос уни в ер с итет) – 13 баллов . Пять студентов
зав оев али
uses crt;
тр етье место: Соломатин А лек сей
type
(Вор онежск и й г ос уни в ер с итет) – 12 баллов , Белиц А лек сандр (Вятск и й
wword = string[32];
г ос уни в ер ситет)
– 11
ttext = array [0..100] of wword;
г ос уни в ер ситет)
–
11
баллов ,
Вы р остк ов
Д ми тр ий
(Вор онеж ск и й
Свир идов
А ндр ей
(Вор онеж ск и й
баллов ,
var
г ос уни в ер ситет) – 10 баллов , Ли зин Сер г ей (М ор дов ск и й г ос уни в ер с итет) – 9
t1, t2, res, o : ttext;
баллов .
n1, n2, nres, no : byte; Н аш и г енер альны е с понс ор ы ЗА О «Р ет-к омпьютер ы » (г енер альны й
ди р ек тор
к омпьютер ному модели р овани ю,
В.М . К олы хали н),
К омпани я
14
fi, fo : text;
«Инфор мс в язь-Чер ноземье»
43
end.
(г енер альны й
Пр едлаг аем так ж е ознак оми ться с р еш ением участник а олимпи ады
пр едстав ительств о
Б елиц А лександра, с тудента Вятс к ог о г ос удар ственног о уни в ер с итета
ди р ек тор
Б.И. Д аньш и н),
к ор пор аци и
Ц ентр ально-Чер ноземное
«Пар ус » (г енер альны й
ди р ек тор
А .В.
А знаур ьянц) в к ачес тв е пр и зов победи телям – вор онежс к им студентам
{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T+,V+,X+,Y+}
пр едос тав и ли ежемес ячны е именны е с типенди и в течени и 2003–2004
{$M 64000,0,655360}
учебног о г ода. Пр и зов бы ло дос таточно мног о. Изв ес тны е к омпьютер ны е (и
const inf='input.txt';
не тольк о к омпьютер ны е) фир мы пос тар али сь наг р адить бук в ально к аж дог о
outf='output.txt';
учас тник а тр етьег о тур а. Э то ЗА О Н ПП «Р елэ к с », О О О «Э к спер т», О О О
q:array[1..8] of longint=(9,180,2700,36000,450000,5400000,63000000,
«Бур ут», О О О «OCS-Ю г », О О О «М онитор -Сер вис », г азета «К омпьютер р а-
720000000);
Р ег и он», и здательск и й дом «Питер -Вор онеж», О О О «Э нфор с », и здательств о «БХ В–Петер бур г », К ос мети чес к и е фир мы
var st:string;
«Ninelle» (Испани я), «Лонда
n:longint;
К олор » (Гер мани я), «Ю ник осмети к » (Санк т-Петер бур г ), р ек тор ат ВГУ , О О О
s:longint;
«Ш к ола-Инфо».
procedure init; Учас т ие ве ду щ их у че ны х и с пе ц иал ис т о в
begin assign(input,inf);
В р аботе ор г к омитета и жюр и пр иняли учас ти е в едущ и е учены е и
assign(output,outf); reset(input);
с пециалис ты в области и нфор маци онног о, математи ческ ог о модели р ов анияи
rewrite(output);
с овр ем енны х
к омпьютер ны х
технолог ий :
пр ор ек тор
Вор онежс к ог о
end;
г ос удар с твенног о педаг ог и ческ ог о уни вер си тета, зав едующ ий
procedure rec(i:integer);
и нфор матик и и методик и пр еподавани я математик и , пр оф. А .С. Потапов ,
begin
пр ор ек тор
ВГУ
к афедр ой
по инфор мати зации доц. А .П. Т олстобр ов , дир ек тор
if (n-q[i]>=0)and(i<9) then begin n:=n-q[i]; s:=s+q[i] div i; rec(i+1);end
р ег и ональног о
else
С.Е. Ландсбер г , ди р ек тор Вор онежск ог о областног о и нс титута пов ы ш ени я
begin
к валифи к ации р аботни к ов обр азования пр оф. С.А . А нти пов , ди р ек тор ЗА О
if n mod i = 0 then writeln(s+n div i) else writeln('Impossible');
центр а
Ф едер ации
Интер нет
О бр азов ани я,
пр оф.
Н ПП «Р елэ к с », к анд. техн. наук Б ой ченк о И.А ., дир ек тор к омпании «Инфор мс в язь-Чер ноземье» Б.И. Д аньш ин, зам . г енер альног о дир ек тор а ЗА О
end;
«Р ет-к омпьютер ы »Д .С. Лапы г ин.
end; Procedure work;
О с о бе нно с т и в организ ац ии и про ве де нии о л им пиады
var er:integer; begin
Во-пер в ы х, пр ов едени е тр етьег о тур а в дв а э тапа, пер в ы й и зк отор ы х -
s:=0;
42
15
телек оммуник аци онны й ,
позв оли ло
не
тольк о
без дополни тельны х
фи нанс ов ы х затр ат значи тельно р ас ш и р и ть г еог р афи ю учас тни к ов , но и
begin
обес печило возможнос ть участи я в нем в сем ж елающ и м студентам,
Assign(f, 'input.txt');
незави сим о от с пециальнос ти и ур ов ня подг отовк и . В в узы Р ос с ии бы ло
Assign(fout, 'output.txt');
р азослано с в ы ш е 300 пи сем обы чной почтой и ок оло 200 – по э лек тр онной
Reset(f);
почте.
Rewrite(fout); Втор ая особенность с в язана с
инфор маци онны м
обеспечением
олимпи ады :
while not eof(f) do begin
- ос вещ ени е хода олимпи ады на в еб-сай те www.ru-stud-olimp.nm.ru ;
n := 1;
- р епор таж об олимпи аде на телев и дени и (к анал Т Н Т, студи я
p := 9;
«Губер ни я») и на Вор онеж ск ом г ос удар ств енном р ади о (пр ог р амма «Д иалог и
res := 0;
о г лав ном»); - публик аци я матер и алов об оли мпиаде в печатны х СМ И (г азеты
{$I-} Readln(f, inp); {$I+}
«М олодой к оммунар », «Вор онеж с к ое обозр ени е», «Вор онежск ий к ур ьер »,
if IOResult <> 0 then Break;
«К омпьютер р а-р ег ион», «Р ос си й ск ая г азета», «Вор онежск ий уни вер си тет»,
while comp(inp, n, p) do {inp > n*p do}
«М оё», «К амелот»).
begin
Т р етьяос обенность – пр ов едени е с целью популяр и зации олимпи ады
res := res + p;
э к спр ес с -опр ос а. Н ак ануне с ор ев новани яс р еди с тудентов в ор онежск и х в узов и участник ов втор ог о э тапа III тур а олимпи ады
бы ли р аспр ос тр анены
for i := 1 to n do inp := inp - p; {
inp := inp - n*p;}
с пециальны е анк еты , в к отор ы х нужно бы ло ук азать тр и г ор ода и з
Inc(n);
пр едложенног о
p := p * 10;
спи ск а, пр едстав ители
к отор ы х с танут победителями
олимпи ады .
end;
Четвер таяос обеннос ть так же с пос обств ует популяр и заци и олимпи ады с р еди студентов . Э то – к онк ур с пр и в етствий учас тник ам оли мпи ады . В э том
if inp mod n = 0 then begin
мер опр и яти и мог ли пр и нять учас ти е в се ж елающ и е, а не тольк о с туденты .
res := res + (inp div n);
Победу одер жала студентк а 2 к ур с а фак ультета пр ик ладной математи к и ,
Writeln(fout, res);
инфор матик и и механи к и (ПМ М ) Вор онежс к ог о уни в ер ситета Стр ы г ина
end
Ек атер и на за сти хи , отр ы в ок и зк отор ы х пр и в еден ни ж е:
else Writeln(fout, 'Impossible');
Н а Вс ес р ос с ий ск ой олимпи аде по и нфор матик е
end;
Собр алис ь вс е лучш ие с туденты , и не тольк о математик и .
Close(fout);
Сег одняв бор ьбув с тупили
Close(f);
16
41
Студенты мног и х в узов Р осси и
else
Сор ев нуютс яг ор ода:
out<<"Impossible";
Вор онеж , П енза, Волог да,
fgets(C, 15, in); }
Р остов , Калини нг р ад, К азань,
fclose(in);
Влади мир , Волг ог р ад, Р язань…
return 0;
Студенты Си би р и и Петр ог р ада…
}
Самы х лучш и х ж дет наг р ада. Пятая ос обенность – пр ив лечение к пр ов ер к е р абот студенчес к ог о
Студент 1 к ур са фак ультета ПМ М ВГУ М их аилШ ат ало в пр едлаг ает с в ой в ар иантр еш ени я
дир ек тор ата и О лимпий с к ог о с ов ета, с остав к отор ы х фор ми р ов алс я и з победи телей пр едш ес тв ующ и х оли мпиад. Подведени е и тог ов
{ Shatalov M.I. }
основ ног о э тапа олимпиада по нес к ольк им
{ VGU, Voronezh }
номи нациям , учиты в ающ и м с пециальнос ти с тудентов , - ш естаяос обенность
{ PMM, 1 kurs }
тр етьег о тур а. Более тог о, ж юр и подв одило итог и и
в номи нации
«Студентк и », что спос обс твовало пов ы ш ению интер еса с туденток к э той олимпи аде.
var
Седьмая ос обенность с ос тоит в том , что по матер и алам олимпи ады
n, p, res, inp, i: Longint;
подг отовлен с бор ник «О лимпиадны е задачи по пр ог р амми р ованию. Лучш ие
f, fout: Text;
р еш ени я», к отор ы й в ы ходит к ак 8 час ть в с ер и и с бор ни к ов по матер и алам function comp(a, b, c: Longint): Boolean;
пр еды дущ и х оли мпи ад. Э то учебное издани е бес платно р ас пр ос тр аняетс я
var fl: Boolean;
с р еди учас тни к ов будущ и х оли мпиад. О дна и з основ ны х иннов аци й нас тоящ ей олимпиады – отк р ы тая (в
begin fl := false;
пр ис утств ии участник ов ) пр ов ер к а р абот, что обес печи в ает г лас нос ть и
while (b <> 0) and (a > c) do
объек ти внос ть в оценк е р езультатов . Э то – восьмаяособеннос ть оли мпи ады . Следует отметить, что без фи нансовой
поддер жк и М ини стер ств а
a := a - c;
обр азования Р осс и й с к ой Ф едер аци и (пр ик аз №
2730 от 25.06.2003 г .) и
b := b - 1;
с понс ор ск ой
begin
помощ и
фир м и
ор г ани заци й
к омпани я «Инфор мс в язь-Чер ноземье», О О О
end;
(ЗА О
«Р ет-к омпьютер ы »,
«Э к с пер т», О О О
«OCS-юг »,
О О О «Ш к ола-и нфо», ЗА О Н ПП «Р елэ к с », О О О «Бур ут», О О О «М они тор if (b=0) and (a>0) then fl := true;
с ер в ис », Ц ентр ально-чер ноземное пр едс тав ительс тво к ор пор аци и «П ар ус»,
comp := fl;
и здательств о БХ В-Петер бур г , О О О
«Питер -центр », г азета «К омпьютер р а-
р ег и он», к осметическ ие фи р мы «Лонда-К олор » (Гер мани я), «Ю ник осметик »
end;
40
17
(Санк т-Петер бур г ), О О О «Э нфор с») пр оведени е э тог о в ажног о молодеж ног о
#include <stdlib.h>
мер опр и яти ябы ло бы нев озможно.
#include <stdio.h>
Ф рагм е нт ы из о т з ы во в у час т ник о в о б о л им пиаде
unsigned long N, d, i, S; char C[15];
«… Пи ш ет Вам Н и к и та Вай нер (М аг нитог ор с к и й ГТУ ), учас тни к
int newline=0;
ос новног о тур а Вс ер ос с ий с к ой с туденчес к ой оли мпиады по инфор мати к е. Х очу поблаг одар ить ор г к оми тет за безупр ечное пр ов едени е с ор евнов ани я
main()
так ог о ур ов ня. О тдельны х слов
{
зас луж и вают пр ев ос ходное
(и , что
немалов ажно, бесплатное) питание и пунк туальное с облюдени е пр ог р аммы ,
FILE *in;
что в моей пр ак тик е – впер в ы е. Позв олю себе ск азать за в сех участник ов , что
in=fopen("input.txt", "r");
пр ек р ас ное в печатление пр оизвела не тольк о олимпи ада, но и с ам г ор од
ofstream out("output.txt");
Вор онеж , пок и дать к отор ы й ни мне, ни мои м нов ы м знак омы м не хотелос ь.
fgets(C, 15, in);
Ис к р енне надеюс ь, что Вс ер ос сий ск ая с туденчес к ая олимпиада получит в
while (C[0]!='#') {
с ледующ ем г одусв ое пр одолж ени е в г .Вор онеже… »
N=atol(C);
«… Спаси бо за помощ ь и с одей с тв ие! Д умаю с так и м подходом к
i=1;
пр облем ам участни к ов олимпиада с к аж ды м г одом будет тольк о пов ы ш ать
d=9;
с в ой
S=0;
ав тор итети пр естиж .
while (N>=i*d){
С ув ажением , А нтон М и хай лов (Калининг р адс к ий уни в ер ситет).»
N-=i*d;
«…
S+=d;
даже если не с танеш ь пр изер ом, вс е р ав но участие в так ой
олимпи аде захв аты в ает…
Э то к ак с пор т. Ви к тор Гай дай (Вор онеж ск и й
d*=10;
уни в ер с итет)»
i++; } if (newline) out<<endl; Учас т ник и вт о рого (о с новно го ) эт апа
newline=1;
Ино го ро дние у час т ник и Ег ор ов Д .А . М оск ва
Захар ов А .В. Тамбов
Ив анов С.Ю . К и р ов
К олес ов
Белиц А .Б. К ир ов
М аг нитог ор с к
18
if (N%i==0) { S+=N/i; П.А .
out<<S; }
39
Вор онежс к и е участник и begin
Вы р остк ов Д . ВГУ , ПМ М
Гай дай В. ВГУ , ПМ М
assign(input,'input.txt');assign(output,'output.txt');
К ли нск и х А . ВГУ , ПМ М
Соломатин А . ВГУ , Ф К Н
reset(input);rewrite(output);
Ш аталов М . ВГУ , ПМ М
Си дор енк о С. ВГУ , ПМ М
readln(input,s);
Сор ок и н А . ВГУ , ПМ М
Св ир и дов А . ВГУ , физ.фак .
{Ц и к л по в ходны м данны м}
Я стр ебО . ВГУ , ПМ М
А знаур ьянц
while s<>0 do
Толубаев
А.
ВГУ ,
ВГУ , мат.фак . К р ячк ов М . ВГУ , ПМ М
фи з.фак .
begin
А.
i:=1;q:=1;
Лар ин И. ВГУ , П М М
Ш естопалова Е. ВГУ , ПМ М
{Ц и к л дляопр еделени як оли чес тва остав ш и хс язнак ов пос ле
Гур ов а М . ВГУ , ПМ М
Си дор ова М . ВГУ , ПМ М
нумер ации в с ех 1,2,3,...,(i-1)-значны х с тр ани ц}
Вахтин С. ВГУ , г еог р .
Зуев А . ВВИР Э Безр одны й А . ВВИР Э
фак .
while q<>0 do begin
К озлов Ю . ВИ М ВД Р Ф
Ив анни к ов М . ВГТ У
q:=gen(i);
Ф р олов А . ВИ М ВД Р Ф
Чер ник ов В. ВГТ У
If (q>0) and (s-q>0) then begin s:=s-q;inc(i) end
Д енисов А . ВГА СУ Гаш к ов М . ВГПУ
else q:=0; end;
Cпо нс о ры В с е ро с с ийс к о й с т у де нче с к о й о л им пиады
{Пр ов ер к а пр ави льнос ти нумер ации}
ЗА О "Р ЕТ ", г .Вор онеж (Генер альны й дир ек тор -
if (s mod i)<>0 then writeln('impossible')
Владим ир М и хай лов и ч К олы хали н, в ы пус к ник фак ультета ПМ М ВГУ )
else begin s:=s div i; writeln(s+round(exp((i-1)*ln(10)))-1); end; readln(input,s); end; close(input);close(output); end. Ещ е
один
вар и ант р еш ения пр едложен
Н икит о й
(М аг нитог ор с к ий техни чес к ий уни в ер ситет)
К осмети ческ аяфи р ма NINELLE, Ис пания(Бр енд-менеджер к омпани и по Ц ЧЭ Р - Галина Ив анов а) ЗА О "Р ЕЛЭ К С", г .Вор онеж (Генер альны й дир ек тор - Иг ор ь А лек сеев ич Бой ченк о, к анд.техн.наук , в ы пуск ник фак ультета ПМ и А СУ ВГУ ) В ай неро м
О О О «Э к с пер т»(Д ир ек тор – Сер г ей Д митр и ев и ч М ахор тов , к анди датфиз.-мат. наук , в ы пуск ник фак ультета ПМ М ВГУ ) О О О «БУ Р У Т »(Генер альны й ди р ек тор – К олы хали н Вик тор
//Vainer Nikita Igorevich //Magnitogorskiy Gosudarstvenniy Tehnicheskiy Universitet #include
М и хай лови ч) О О О "OCS-Ю г " (Д и р ек тор - Иг ор ь Ю р ьев и ч Батуев , в ы пуск ни к фак ультета ПМ М ВГУ )
38
19
К омпани я«Инфор мс в язь – Чер ноземье» (Генер альны й дир ек тор -
begin
Бор ис Ив анови ч Д аньш ин, в ы пус к ни к фак ультета ПМ М ВГУ )
M:=(L+R) shr 1; K:=NumOfChars(M);
Ц ентр ально-Чер ноземное пр едстави тельс тв о к ор пор ации «Пар ус »(Генер альны й ди р ек тор - А лек с андр
if KK0 then R:=M-1 else Break;
Владими р ов и ч А знаур ьянц, в ы пуск ник фак ультета ПМ М ВГУ )
end; if K=K0 then WriteLn(M) else WriteLn('Impossible');
О О О «М онитор -Сер в и с» (Генер альны й дир ек тор - О лег
end;
Петр ов и ч М ахначев , в ы пус к ник фак ультета ПМ М ВГУ )
Close(Input);
Ф ир ма Лонда К олор , Гер мания (М енеджер по к лючев ы м
Close(Output);
к ли ентам – О льг а Ф р олов а)
end.
Газета «К омпьютер р а-Р ег и он» (Главны й р едак тор издательск ог о дома – Светлана К олес ник ова)
Пр и в едем р еш ение э той же задачи члена жюр и , члена О лимпий с к ог о
О О О «Питер -центр » (Генер альны й ди р ек тор Вор онежск ог о
с овета, ас пи р анта фак ультета ПМ М Вор онеж с к ог о г ос уни вер с итета А ндрея
фили ала – Д митр и й Вик тор ови ч Ш и ш к и н)
По ляко ва
Издательс тв о к омпьютер ной ли тер атур ы BHV-Пи тер (Д ир ек тор Вади м А лек с андр ов и ч Сер г еев )
program BookPages;
К осмети чес к аяфир ма Unicosmetic, Санк т-П етер бур г (Д и р ек тор Вор онежск ог о пр едстав ительс тв а – М и хаи л Сер г ееви ч Чир к о, к анд.фи з-
{Ф унк ци я, опр еделяющ ая чис ло знак ов , необходимое длянумер ации в сех i-значны х с тр ани ц}
мат.наук , в ы пус к ник фак ультета ПМ М ВГУ ) О О О «Э нфор с »(Д и р ек тор – Д митр и й Любк ин, в ы пуск ник
function gen(i:integer):longint;
фак ультета ПМ М )
var j:integer;
О О О Н ПП "Ш К О ЛА -ИН Ф О " (Д ир ек тор - К онс танти н Ю р ьев ич
k:longint; begin
Татар к ов , в ы пус к ни к фак ультета ПМ М ВГУ )
k:=9; Ит о го вая т абл иц а о л им пиады С е к ц ия 1. «П рограм м иро вание и к о м пью т е рное м о де л иро вание » №
Ф ИО
Гор од
1 Чеpны х Сеpг ей Владими pови ч
К алининг р ад
2 Ёжк и н Вячес лав Сер г еев ич
Волог да
Сумма М ес то баллов 21 1 16
for j:=1 to i-1 do If MaxLongInt div 10 > k then k:=k*10 else k:=0; if MaxLongInt div i >k then gen:=k*i else gen:=0 end;
2 var i:integer;
Си дор енк о Стани с лав 3 Владленови ч
Вор онеж
20
16
2
s,q:longint;
37
MaxTenDegree:=1;
4 Луг ов ов А лек сандр Э дуар дови ч
М ос к в а
14
2
CurLen:=1;
5 Х ади ев К амиль Р ав илеви ч
К азань
14
2
Result:=0;
6 Ш итов А ндр ей Н ик олаев и ч
Чебок сар ы
14
2
Ndiv10:=N div 10;
7 Ш аталов М и хаи л Иг ор ев и ч
Вор онеж
13
2
8 Соломатин А лек с ей Ив анов и ч
Вор онеж
12
3
9 Бели ц А лек с андр Бор ис ови ч
К и р ов
11
3
10 Вы р ос тк ов Д митр ий А ндр ееви ч
Вор онеж
11
3
11 М и хай лов А нтон А натольев ич
К алининг р ад
11
3
while MaxTenDegree<=Ndiv10 do begin OldTenDegree:=MaxTenDegree; MaxTenDegree:=MaxTenDegree*10; Inc(Result,(MaxTenDegree-OldTenDegree)*CurLen);
Св ир и дов А ндр ей
Inc(CurLen);
3
end;
12 А лек сандр ови ч
Вор онеж
10
NumOfChars:=Result+(N-MaxTenDegree+1)*CurLen;
13 Ли зи н Сер г ей Н ик олаеви ч
Сар анск
9
Я р ослав ль
8
М ос к в а
8
4
16 Лар и н Иг ор ь А лек с андр ови ч
Вор онеж
8
4
17 М и нин Владимир Н ик олаеви ч
Волг ог р ад
8
4
18 А знаур ьянц А лек сандр
Вор онеж
8
4
Ви ног р адов Вик тор А лек сандр ови ч 15 Ег ор ов Д ени с А лек сеев и ч
end;
14
var S:string; K0,K,L,R,M,N:LongInt; Code:Integer;
3 4
Вор онеж
7
Assign(Input,'INPUT.TXT');
К ар пуш ин А ндр ей А лек сандр ови ч 20 К улеш ов А ндр ей А лек с андр ов и ч
Т ула
7
5
Assign(Output,'OUTPUT.TXT');
21 Пунин Н ик олай Геннадиев ич
Тамбов
7
5
Reset(Input);
22 Бабани н Д митр ий Владими р ов ич
Т амбов
6
5
ReWrite(Output);
23 Гаш к ов М ак сим А лек сандр ов и ч
Вор онеж
6
5
24 А к и мов Иг ор ь Н и к олаевич
Сар анск
6
5
25 Гай дай Ви к тор А лек с андр ович
Вор онеж
6
5
26 Сор ок и н А ндр ей Иг ор еви ч
Вор онеж
6
5
Val(S,K0,Code);
27 Т итк ов А лек с ей Валер ьеви ч
Т амбов
5
6
L:=1;
28 Захар ов А лек с ей Влади мир ови ч
Т амбов
5
6
R:=250000000;
29 К олес ов Павел А лек с андр ов ич
М аг ни тог ор ск
5
6
while L<=R do
30 Безр одны й А лек с ей Н и к олаеви ч
Вор онеж
4
7
begin
19
while not SeekEOF do begin ReadLn(S); if S[1]='#' then Break;
36
21
5
31 Гольцов Иг ор ь Ю р ьеви ч
М ос к ва
4
7
32 Гур ьев Д ми тр ий А ндр ееви ч
Чебок сар ы
4
7
Д ев етьяр ов Владими р Ви к тор ов ич 34 Зуев А лек сандр Сер г ееви ч
Вятк а
4
Вор онеж
4
7
35 Чер ни к ов Вячеслав Н и к олаеви ч
Вор онеж
4
7
36 К ор ж ов Н ик олай Евг еньев ич
Вор онеж
5
6
37 Пи с ар ев с к и й Сер г ей Ю р ьеви ч
Вор онеж
3
8
38 Д енис ов А лек сандр Сер г еевич
Вор онеж
3
8
39 Ив анник ов М ак си м Иг ор ев ич
Вор онеж
3
8
40 Ив анов Д ми тр и й А лек с андр ов и ч
Сар анск
3
8
3
8
3
8
33
41 К алинк ин Вади м Ю р ьеви ч 42 К озлов Ю р и й Стани с лав ов и ч
Р остов -на-Д ону Вор онеж
7
С целы х чисел р азделенны х пр обелами , к отор ы е пр инимают значени я{3,6,9 и ли 12}. О с тав ш иес ястр ок и (и х B ш тук ) опис ы в ают к оманды . В к аж дой и з э ти х с тр ок с одер жатьс я номер а часов , к отор ы е пер еводятся на 3 часа впер ед данной к омандой . В ы хо д ны ед а нны е В в ы ходной фай л output.txt должны бы ть помещ ены номер а к оманд чер ез пр обел, к отор ы е необходи мо пос ледов ательно пр и мени ть, чтобы в ы с тавить в се час ы на 12 часов . Если последов ательность к оманд оты с к ать нев озм ожно, то с ледует в ы дать "Р еш ения нет". Ес ли вс е час ы и значально пок азы в ают 12 час ов , то нужно в ы дать "П ер евод час ов не тр ебуетс я". В с лучае, к ог да р еш ений неск ольк о, необходим о в ы вести пер вое р еш ение в алфави тном пор ядк е. Н апр и мер , ес ли тр ебуемы й пер ев од час ов дос ти г аетс я на пос ледов ательностях к оманд 0 2 1 и 0 1 2, то в в ы ходном фай ле долж но с одер ж атьс япоследнее. П ример вхо д ны хд а нны х
43 Лог унов Сер г ей
Вор онеж
3
8
44 Самонин М и хаил Н ик олаеви ч
Тамбов
3
8
45 Ф р олов А лек сей А ндр еев и ч
Вор онеж
3
8
52 9 9 12 6 6 0134 34
46 Щ ер бак ов Евг ени й А натольев и ч
Вор онеж
3
8
П ример вы хо д ны хд а нны х
47 Р ак чеев Д ени с Ви тальевич
К алининг р ад
2
8
01
48 Вай нер Н ик ита Иг ор ев и ч
М аг нитог ор с к
6
5
49 Д емидов Ив ан Ив анови ч
Вор онеж
1
9
50 К озин Евг ени й Вячес лав ов и ч
М ос к ва
1
9
Вор онеж
1
51
Т олубаев А лек с ей К онстанти нови ч
9
Н оми нация«Студентк и »
Из бранны е ре ш е ния Задача1. К ниж ны е стр аницы Н и же пр и води тс я р еш ени е абс олютног о победи теля олимпи ады с тудента м атематичес к ог о
фак ультета К алини нг р адс к ог о
уни в ер си тета
Сергея Черны х
1 Гур ов а М ар и я
Вор онеж
6
1
2 Си дор ова М ар и на
Вор онеж
5
2
{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T+,V+,X+,Y+}
3 Паш енцев а Ев г ени я
ВГТ А
2
3
{$M 65520,0,655360} function NumOfChars(N:LongInt):LongInt; var MaxTenDegree,OldTenDegree,CurLen,Result,Ndiv10:LongInt; begin
22
35
–
2
Сек ци я2. «Пр и к ладное пр ог р аммное обес печени е» 11+
Ф ИО
М есто учебы
Белобр одс к ий
22+
А .А .
12+
К ув ай цев
22-
О .Ю .
0
Захар ов А .В. А леев а Е.П.
П рим ер вы хо д ны хд а нны х Иг р ок 2 в ы и г р ал. Х од 3
Гур ьев Д .А .
Н и чья Задача№ 4 "Синх р онизация часов" Р ас с матр ив аетс яг р уппа с ос тоящ аяи зС (1<=C<=11) ш тук час ов . Все они им еют ли ш ь часов ую стр елк у, к отор аямож ет пок азы вать тольк о с ледующ ее в р емя: 3 часа, 6, 9 и 12 час ов . Сущ ес тв ует B (0<=B<=11) р азличны х к оманд дляпер ев ода часов . Д ей с тв и е к аждой к оманды с ос тои тв пер ев оде нек отор ой подг р уппы часов на 3 час а в пер ед. Тр ебуется най ти наименьш ую последов ательность к ом анд, в р езультате пр и менения к отор ы х в се час ы будутпок азы в ать 12 час ов . Н апр имер , р ассмотр им г р уппусостоящ ую из5 часов . О пи ш ем 2 к оманды дляпер ев ода час ов пр и помощ и с ледующ ей таблицы Н о мер а ча с о в 0 1 2 3 4 Н а ча л ьны ес о с то яния 9 9 12 6 6 +3 +3 +3 +3 Ко ма нда 0 +3 +3 Ко ма нда 1 Ес ли пр и мени ть пос ледовательно нулев ую и пер в ую к оманды , то вс е час ы будутпок азы в ать 12 час ов .
Д р аг ун Д .А . К озин Е.В. Ж ук ов П.Ю . Илина Е.П. К аплан Г.Л. К ар пов В.С. М ус тафин Э .У . Четв ер г ов а О .А .
В хо д ны ед а нны е В пер в ой с тр ок е в ходног о фай ла input.txt с одер жатс ядв а целы х числа C и B, р азделенны х пр обелами . С - э то к оли честв о час ов (1<=С <=11), а B – к оли чес тв о к оманд. Вс е нумер аци и начинаютс яс нуля. Втор аяс тр ок а опи с ы в аетначальны е позици и час ов . Э та с тр ок а с остоити з
34
Вор онежск и й г ос удар ственны й уни в ер с итет, э к оном.фак . О р енбур г с к и й г ос удар с тв енны й уни в ер с итет, ф-ти нфор мационны х технолог ий Т амбов ск и й г ос удар ств енны й техни чес к ий уни в ер ситет, ф-тА Х П Т амбов ск и й г ос удар ств енны й техни чес к ий уни в ер ситет, э к ономи чес к и й ф-т Чув аш ск ий г ос удар ственны й педаг ог и чес к и й уни вер си тет, физмат.ф-т Б елг ор одск и й г ос удар ств енны й технолог ическ ий уни вер с итет М оск овс к аяг ос удар ств енная ак адемияпр и бор ос тр оени яи и нфор матик и , ф-тТ СИИ Став р опольс к ий г ос удар с тв енны й уни в ер с итет, г еог р аф.ф-т Т амбов ск и й г ос удар ств енны й техни чес к ий уни в ер ситет, э к ономи чес к и й ф-т Став р опольс к ий г ос удар с тв енны й уни в ер с итет, г еог р аф.ф-т Всер ос сий ск аяг ос удар ственная налог оваяак адемия, М ос к в а Б елг ор одск и й г ос удар ств енны й технолог ическ ий уни вер с итет Вятс к и й г ос удар ств енны й уни в ер с итет, Ф ПМ Т
Сумма баллов 14
М ес то
14
1
9
2
13
2
13
2
13
2
3
3
6
3
3
4
6
5
9
5
11
5
5
6
Задания 1 эт апа т ре т ье го т у ра о л им пиады 1. Секция алг оритм изацииип р ог р ам м ир ования
23
1
З адач а (общ ая для всех ном инаций )
то и г р ок получи в ш и й так ую с хему пр ои г р ы в ает, а др уг ой и г р ок в ы и г р ы вает. Иг р а зак анчи вается вни чью пос ле 2N ходов , ес ли не бы ло повтор яющ и хс я с хем в ходе и г р ы . Р ас смотр им в к ачеств е пр имер а с ледующ и е с хемы :
"П ом ог исп елеологу" Вы попали в тр ехмер ную пещ ер уи в ам необходи мо най ти к р атчай ш ий путь к в ы ходу. Пещ ер а пр едстав ляет с обой к уб, в к отор ом есть пр оходы . Пер емещ ение в любом напр ав лении (в вер х, в низ, впр ав о, в лев о, в пер ед, назад) зани мает р ов но одну минуту. Пер емещ атьс я по диаг онали и чер ез с тены пещ ер ы не р азр еш аетс я. Возмож ен ли в ы ход и зтак ой пещ ер ы и если «да», то ск ольк о в р емени в ам понадобитс я? В хо д ны ед а нны е Входной фай л INPUT.TXT с ос тои тизопи с аний неск ольк и х пещ ер . О пи с ани е к аждой пещ ер ы начи наетс яс о с тр ок и с тр емяцелы ми чис лами L, R и C ( в с е чи сла не больш е 30). L – к оли честв о ур ов ней в пещ ер е, R, C – к оли чес тв о с тр ок и к олонок в плане к аж дог о э таж а. Д алее следуют L блок ов данны х, к ажды й и зк отор ы х пр едстав ляет R с тр ок , содер жащ и х C с имв олов . К ажды й с и мв ол опис ы в аетячей к упещ ер ы . Стены обозначены симв олом ‘#’, а ячей к и г де пр оход р азр еш ен ‘.’ (точк ой ) . Н ачальнаяпози ци яук азы в аетс яс имв олом ‘S’, а в ы ход с и мволом ‘E’. Пос ле опис ани як аж дог о ур овняпещ ер ы с ледует р овно одна пус таястр ок а. Вв од зав ер ш аетс ястр ок ой , с одер ж ащ ей тр и нуляв к ачеств е L, R, C. В ы хо д ны ед а нны е К аждой пещ ер е в в ы ходном фай ле OUTPUT.TXT должна с оответствовать одна с тр ок а. Ес ли Вы наш ли в ы ход, то ви д стр ок и следующ ий : Вы ш ли за x ми нут. г де x к р атчай ш ее в р емя, за к отор ое в озможен в ы ход. Ес ли в ам не удалось най ти в ы ход, напечатай те стр очк у: Лов уш к а! П рим ер вхо д ны хд а нны х
Ес ли пер в ая с хема бы ла получена р анее, то любаяи з 3 с ледующ и х с хем будетзавер ш ать и г р у, а пос ледняянет. В хо д ны ед а нны е Во в ходном фай ле Input.txt к аж дая иг р а из с ер и и и г р опис ы ваетс я набор ом с тр ок : пер ваяс одер ж и т р азмер поля(2<=N<=50), в с ледующ и х 2N с тр ок ах содер жатсяходы , изк отор ы х в озм ожно не вс е нужны . К ажды й ход с ос тои т и з к оор ди нат к вадр ата (от 1 до N) и с ледующ ег о чер ез пр обел с и мв ола ‘+’ и ли ‘-‘ , к отор ы й означает ус тановк у и ли с нятие фи ш к и с оответс тв енно. Все ходы пр ав ильны е. Вв од данны х зак анчи ваетс янулем . В ы хо д ны ед а нны е Вы ходны е данны е должны
бы ть помещ ены
в тек с тов ы й
Output.txt , в к отор ом к аж даяс тр ок а содер житр езультаточер едной иг р ы .
345 П ример вхо д ны хд а нны х
S.... .###. 2
.##.. ###.#
11+ 22+
##### #####
22-
##.## 12+
24
33
фай л
П рим ер вхо д ны хд а нны х
##...
Чтобы пр и мер не р ассматр и в алс я к ак аг итаци я за тог о или и ног о к анди дата, пр едлаг ается най ти наи больш ую общ ую подпос ледов ательность с лов в дв ух тек с тах на немецк ом язы к е.
##### ##### #.###
die einkommen der landwirte
####E
sind fuer die abgeordneten ein buch mit sieben siegeln 133 um dem abzuhelfen
S##
muessen dringend alle subventionsgesetze verbessert werden
#E# ###
# die steuern auf vermoegen und einkommen
000 П ример вы хо д ны хд а нны х
sollten nach meinung der abgeordneten
Вы щ ли за 11 ми нут. Лов уш к а!
nachdruecklich erhoben werden dazu muessen die kontrollbefugnisse der finanzbehoerden
З адачи п о н о м ин ац ия м И нфор м атикакак п р офилир ую щ ая дисц ип лина «В одители-болтуны »
dringend verbessert werden # . П рим ер вы хо д ны хд а нны х die einkommen der abgeordneten muessen dringend verbessert warden Задача3. "И г р асфиш кам и" Иг р а с фи ш к ами пр оис ходи т на поле N на N к леток (в пр и мер е ни же N=4). В ней участв уют дв а и г р ок а. Пер в ы м счи тается и г р ок , с овер ш ающ ий пер в ы й ход. Во в р емя иг р ы и г р ок может ли бо поместить чер ную фи ш к у в любое место доск и , ли бо с нять с ущ еств ующ ую, что пр и в оди т к р азли чны м с хем ам р ас становк и . Ес ли очер едная полученная с хема (и ли ее р азвор отна 90, 180, 270 г р адусов ) повтор яетс яв о вр емяи г р ы ,
32
В к аж дом г ор оде есть общ ес тв енны й тр анспор т. Н а к аж дом мар ш р уте автобус дви жетс япо к ольцу, и к аж даяли ни яимеет, по к р ай ней мер е, дв е останов к и . Н ек отор ы е лини и и меют общ ие остановк и . К ог да дв а и более в оди теля в стр ечаютс я на одной остановк е, они обменив аютс я с в ои ми нов остями , и с э тог о в р емени к аж ды й и зни х знает и с в ои новос ти , и чужие. Вс е в одители начинают дв и жени е на лини ях в одно и тоже в р емя. К ажды й автобус вс е в р емяс ов ер ш ает поездк и по одной и той же лини и . Р азличны е автобус ы на одной лини и с тар туют, возмож но, на р азли чны х остановк ах в начале дня. А в тобус ы р аботаюточень синхр онно. Вр емянеобходим ое, чтобы доехать от одной ос танов к и до др уг ой одинак ово дляв с ех ос танов ок и вс ех лини й . Известно, что в г ор оде n ав тобус ны х лини й (0 < n < 20), d водителей (и так же d автобусов ) (0 < d < 30) пр онум ер ов анны х чис лами от1 до d, и s автобусны х останов ок (0 < s < 50), пр онумер ов анны х от1 до s. Води тели хотятзнать, можетли к аж ды й изни х узнать в нек отор ое вр емяв сю и нфор маци ю, к отор аяи звестна ег о к оллег ам. Н апи ш и те пр ог р амму, к отор ая поможетотв ети ть на э тотв опр ос .
25
В хо д ны ед а нны е
60
Входной фай л содер жит блок и с тр ок . Каж ды й блок , ис к лючая пос ледний , опис ы вает оди н г ор од. В пер в ой стр ок е блок а целы е чис ла n, d и s р азделяем ы е одним пр обелом. Следующ и е 2n стр ок и опис ы в ают n ав тобус ны х лини й (2 с тр ок и на к аж дую лини ю) по с ледующ и м пр ави лам: в пер в ой стр ок е и дут номер а ос танов ок , р азделенны е пр обелом. О становк и пер ечис лены в пор ядк е, по к отор ом уав тобус объезжаети х. После пос ледней ос танов к и в списк е ав тобус следует к пер в ой . Втор ая с тр ок а опис ы вает, с к ак и х остановок начинают дв и жение ав тобус ы в начале дня. О пи с ани е с остоити зпар si, di, г де s i – номер остановк и и di – номер водителя. Все чи сла s i, di на с тр ок е р азделены одни м пр обелом. Пос ледний блок с одер жи т одну с тр ок у, с остоящ ую и зтр ех нулей «0 0 0».
# П ример вы хо д ны хд а нны х 10 11 34 Impossible
В ы хо д ны ед а нны е Задача2. "В ы бор ы 2003" Вы ходной фай л с одер жи тстр ок и , соотв етств ующ и е блок ам во в ходном фай ле. Стр ок а «Д а», ес ли с оотв етс тв ующ ий блок в фай ле в хода опи с ы в ает с и туаци ю, к ог да к аж ды й в одитель будетзнать в нек отор ое в р ем явс е нов ос ти отс вои х к оллег . Иначе с тр ок а содер жит«Н ет». Д ляпос ледней стр ок и в ходног о фай ла, с оответств ующ аяс тр ок а в ы ходног о не фор мир уетс я. П рим ер вхо д ны хд а нны х 2 3 5 1 2 3 1 1 2 2 2 3 4 5 2 3 0 0 0 П рим ер вы хо д ны хд а нны х Да
Чер езнеск ольк о недель в наш ей стр ане состоятс яв ы бор ы . К ажды й депутат, учас тв уя в пр едв ы бор ной к ампани и , в ы дви г ает с в ою пр ог р амму. Вес ьма непр осто опр еделить р азли чия и с ходс тв а ср еди так и х пр ог р амм . Ваш а задача с оздать пр ог р амму для фор мальной оценк и «похожести» поли ти чес к и х пр ог р амм к анди датов . «Похожес ть» пр ог р амм мож но фор мально оцени ть, най дянаи больш ую общ ую подпос ледовательность слов , пр ис утств ующ ую в к аж дой пр едв ы бор ной пр ог р амме. В хо д ны ед а нны е
И нфор м атикакак общ еобр азовательная дисцип лина(вклю чая тех нические ивоенны е вузы ) "П р я м оуг ольник"
Входной фай л Input.txt с ос тоит из неск ольк и х тес тов . Тес т пр едстав ляет с обой набор и з дв ух тек с тов , зак анчи в аются стр ок ой , с одер ж ащ ей тольк о с имв ол #. Т ек с т - последовательнос ть с тр очны х с и мв олов , р азделенны х одни м или неск ольк ими пр обелами без знак ов пунк туаци и . Известно, что в с лов е - меньш е 30 с имв олов и что к аж ды й тек с т с одер жи тне больш е 100 слов . Симв ол ‘.’ (точк а) в начале стр ок и яв ляетс япр изнак ом к онца фай ла. В ы хо д ны ед а нны е
Д ана пос ледов ательность N*8 в ещ ественны х чи сел. О чер едная вос ьмер к а чи сел опр еделяет к оор ди наты вер ш и н четы р ехуг ольник а на плоск ос ти , пр ичем пор ядок с ледов ани я к оор ди нат в ер ш и н отвечает обходу в ер ш и н четы р ехуг ольник а ли бо по час ов ой стр елк е, ли бо пр оти в час ов ой стр елк и . Т р ебуетс я в ы бр ать в ос ьмер к у чи сел, к отор ы е опр еделяют в ер ш и ны пр ямоуг ольни к а. О пр едели ть, ск ольк о так и х в осьмер ок чи сел можно в ы бр ать.
26
Д ля к аж дог о теста необходимо получить пос ледов ательнос ть с лов , пр едстав ляющ и х наи больш ую общ ую подпос ледов ательнос ть слов , с одер ж ащ уюс я в к аж дом из дв ух тек стов . Если так и х пос ледов ательностей неск ольк о необходим о най ти тольк о одну. Слов а пос ледов ательности должны бы ть в ы ведены в одной с тр ок е и р азделены одним пр обелом.
31
Н ай ти в ос ьмер к у чисел, к отор ой с оотв етств ует пр ямоуг ольни к с мак с имальной площ адью. Вы чи слени япр ои зводить с заданной точностью Е.
2) Сохр анение фор м ул. 3) Р асполож ение и с ходны х данны х и р еш енияна одном э к р ане.
Задания 2 эт апа т ре т ье го т у ра о л им пиады
Вы ходной фай л OUTPUT.TXT долж ен содер жать в пер в ой стр ок е чи с ло в озмож ны х в ос ьмер ок чис ел, во в тор ой – пер в ую изтак и х в ос ьмер ок чи с ел, с оответс тв ующ и х пр ямоуг ольни к у, в тр етьей - в осьмер к у чи с ел, с оответс тв ующ и х пр ямоуг ольни к ус мак с имальной площ адью.
Задача1 " К ниж ны естр аницы " Р ас с матр и в аютс я к ни г и с пос ледов ательной нумер аци ей Пер ваястр аница в к аж дой к ни г е и меетномер 1.
Входной фай л INPUT.TXT с одер ж итв пер в ой с тр ок е чис ла N и Е, в к аж дой и зN пос ледующ и х стр ок – по в осемь чи сел.
стр аниц.
Ск ольк о знак ов потр ебуетс я, напр и мер , для нумер ации к ни г и из 10 с тр аниц? Пр и нумер ации с тр аниц с пер в ой по дев ятую будети спользовано 9 знак ов , а пр и нумер ации дес ятой с тр аницы – 2 знак а. Так им обр азом, получаетс я11 знак ов . А налог и чно дляк ни г и из 34 с тр ани ц потр ебуется59 знак ов . Т р ебуетс ясоздать пр ог р амму для опр еделени як оличес тв а стр ани ц в к ни г е по заданному чи слу знак ов или в ы вода сообщ ени я «Impossible» в с лучае, ес ли чи сло стр аниц опр еделить невозмож но. В хо д ны ед а нны е
П ример вхо д ны хд а нны х: 2 0.00001 1131 3313 1131 4413 П ример вы хо д ны хд а нны х(дляпр и в еденног о в ы ш е в ходног о фай ла): 1 1131 3313
К аждая стр ок а в ходног о тек стов ог о фай ла Input.txt с оотв етс тв ует одной к ни г е и с одер жит целое чис ло N (1<=N<=2 000 000 000), задающ ее чи сло знак ов . Си мв ол # в начале с тр ок и яв ляетсяпр и знак ом к онца фай ла.
1131 3313 Ю р идическиеиг ум анитарны е сп ециальности
В ы хо д ны ед а нны е Вы ходны е данны е - к оли честв о стр ани ц в к ни г е и ли с тр ок а с тек стом «Impossible» - должны помещ атьс я в тек с тов ы й фай л Output.txt. К аж дое в ы ходное значение должно р азмещ атьс яв отдельной с тр ок е. П рим ер вхо д ны хд а нны х 11
"А иБ " Вв еденны й тек с тпр едс тавляет собой пр едложени е, в к отор ом в стр ечаетс я пер ечи слени е дв ух объек тов , с в язанны х союзом «и ». Т р ебуетс я поменять местами с лов а, с оеди ненны е э ти м с оюзом. Н апр и мер , тек с т «А и Б с идели на тр убе»пос ле пр еобр азованиядолж ен иметь в и д «Б и А с идели на тр убе». Пер вокур сникиЗадача"Т еатр "
13
В театр е N мест, пр онумер ов анны х целы ми чис лами от1 до N. Н ек отор ы е и з зр ителей опоздали на спек так ль, поэ тому пос ле тр етьег о звонк а те зр ители , к отор ы е и мели би леты на неудобны е места, пер есели на более удобны е.
59
30
27
О поздав ш ие зр ители , к отор ы е пр и ш ли уже пос ле тр етьег о звонк а, сади лис ь на пер в ое попав ш еес яс в ободное мес то.
Студентки
В антр ак те один изопоздав ш и х зр ителей р еш и л сесть на с в ое мес то. Если ег о место до э тог о бы ло занято, то тот, к то там си дел, пер ес ажи валс яна с вое место. Ес ли и там к то-то уж е с идел, то и э тотзр итель так ж е в ы нуж ден бы л в ер нутьс яна св ое место. И так далее.
В эт о й но мина ции м о жно вы бра т ь за д а чи, пред ло женны е в д ругих но мина циях, и о т веча ющ ие сво ей специа льно ст и.
Пос к ольк у в театр попали тольк о зр ители , им ев ш и е на р ук ах би леты , то начав ш ий ся в антр ак те пр оцесс пер ес ажи вания зр и телей обязательно зак анчив алс я. Н еобходимо подс читать, с к ольк о челов ек в р езультате так ог о пер ес ажи вани ябы ли в ы нуж дены поменять св ои места.
Задание 1.
Т р ебуетс яс оздать пр ог р аммудляв ы чис лени як оли чес тв а зр ителей , поменяв ш и х с в ои места из-за опоздани яодног о зр ителя. Ф о рм а т вхо д ны хд а нны х: Входной фай л INPUT.TXT с ос тои тизтр ех стр ок . В пер в ой стр ок е с одер жи тсяцелое чис ло N (N<=30000) — к оли честв о меств зале. Втор аястр ок а с одер жит пос ледов ательнос ть и зN целы х чис ел, р азделенны х пр обелами , г де пер в ое чи сло опр еделяет номер мес та в би лете у зр и теля, к отор ы й занял мес то с номер ом 1, в тор ое - номер места в билете у зр и теля, к отор ы й занял место с номер ом 2, и так далее. Ес ли мес то бы ло с в ободно, то с оответств ующ ее чис ло р авно 0. В тр етьей с тр ок е содер житс я одно чис ло - номер мес та в билете у опоздав ш ег о зр ителя, к отор ы й в антр ак те р еш и л пер ес ес ть на с в ое место. Ф ор матв ы ходны х данны х: Вы ходной фай л OUTPUT.TXT должен с одер ж ать одно чис ло — к оли чес тв о зр ителей , поменяв ш и х с вои мес та в антр ак те, вк лючаяопоздав ш ег о зр и теля. П рим ер ф а йло в вхо д ны хи вы хо д ны хд а нны х: INPUT.TXT
OUTPUT.TXT
10
3
2. Секция п р икладногоп р ог р ам м ног ообесп ечения
Создать э мблему ш к олы -олимпиады к омпьютер номумодели р овани ю.
28
и
1) Р абота м ожетбы ть в ы полнена в любом р едак тор е. 2) Поми мо г р афическ и х э лементов э мблема должна с одер ж ать назв ани е или аббр ев иатур уназвани яоли мпи ады и г од пр ов едени я. Задание 2. Создать г и пер тек с тов ы й док умент, с одер ж ащ ий и нфор маци ю о автор е, ег о г р уппе и учебном заведени и , в к отор ом учитсяавтор . Тр ебов ания: 1) Д и зай нер с к ое р еш ение должно в к лючать фото автор а, фото г р уппы (подг р уппы ), р аботающ ей в к омпьютер ном к лас с е и фото здани яв уза. 2) Вс е фай лы должны с одер ж атьсяв одном к аталог е. Сс ы лк и должны бы ть относ ительны ми . Задание 3. Ср едс тв ами Excel создать фай л, содер жащ и й нахождени яопр еделителяматр ицы р азмер а 4×4.
1) Н али чие заг оловк ов .
4
пр ог р амми р овани ю
Тр ебов ания:
Тр ебов ания:
0253100000
по
29
р еш ени е задачи
} // Function name
: setField
// Description
: Sets or removes field from specified square,
// Description
: also checks input file for validity.
// Return type
: void
// Argument
: bool aF[NMAX][NMAX]
// Argument
: int x
// Argument
: int y
// Argument
: bool bMove
void setField(bool aF[NMAX][NMAX],int x, int y, bool bMove) { if (bMove) { if (aF[x][y]) { printf("Error: put on existing cell\n"); } else { aF[x][y] = true; } } else { if (!aF[x][y]) { printf("Error: remove from non-existing cell\n"); } else {
112
57
aF[x][y] = false; } } } // Function name
: checkFields
// Description
: Checks if two specified field arrays are one like
another // Return type
: bool
// Argument
: bool aField[NMAX][NMAX]
// Argument
: bool aField2[NMAX][NMAX]
bool
checkFields(bool
aField[NMAX][NMAX],
bool
aField2[NMAX][NMAX]) { int i,j; bool bResult = true; for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) { if (aField[i][j] != aField2 [i][j]) { bResult = false; return bResult; } } return bResult; }
// Function name // Description
: checkFields90 : Checks if two specified field arrays are like one
58
111
// Description
: another rotated by 90 degrees
// Return type
: bool
// Argument
: bool aField[NMAX][NMAX]
// Argument
: bool aField2[NMAX][NMAX]
bool
checkFields90(bool
aField[NMAX][NMAX],
bool
aField2[NMAX][NMAX]) { int i,j; bool bResult = true; for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) { if (aField[i][j] != aField2 [j][n-i+1]) { bResult = false; return bResult; } } return bResult; } // Function name
: checkFields180
// Description
: Checks if two specified field arrays are one like
// Description
: another rotated by 180 degrees
// Return type
: bool
// Argument
: bool aField[NMAX][NMAX]
// Argument
: bool aField2[NMAX][NMAX]
bool
checkFields180(bool
aField[NMAX][NMAX],
aField2[NMAX][NMAX]) {
110
59
bool
int i,j; bool bResult = true;
for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) { if (aField[i][j] != aField2 [n-i+1][n-j+1]) { bResult = false; return bResult; } } return bResult; } // Function name
: checkFields270
// Description
: Checks if two specified field arrays are one like
// Description
: another rotated by 270 degrees
// Return type
: bool
// Argument
: bool aField[NMAX][NMAX]
// Argument
: bool aField2[NMAX][NMAX]
bool
checkFields270(bool
aField[NMAX][NMAX],
bool
aField2[NMAX][NMAX]) { int i,j; bool bResult = true; for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) { if (aField[i][j] != aField2 [n-j+1][i])
60
109
{ bResult = false; return bResult; } } return bResult; } // Function name
: solutionFound
// Description
: founds minimal move where position repeats
// Return type // Argument
: void : int iMoveNumber
void solutionFound(int iMoveNumber) { if (iMoveNumber < iMinFirstRepeatFound) { iMinFirstRepeatFound = iMoveNumber; } } // Function name
: run
// Description
: start searching combinations
// Return type
: int
int run() { int iRepFirst = -1; int iRepSecond = -1; int i,j; int i1,j1; for ( i = 1; i <= n; i++ )
108
61
for ( j = 1; j <= n; j++ ) { aField[i][j] = false; } for ( i = 0; i < 2 * n-1; i++ ) { int x,y; bool bMove; x = aMoves[i][0]; y = aMoves[i][1]; bMove = (bool)aMoves[i][2]; //filling aField setField(aField,x,y,bMove); for ( i1 = 1; i1 <= n; i1++ ) for ( j1 = 1; j1 <= n; j1++ ) { aField2 [i1][j1] = aField [i1][j1]; } for (j = i+1; j < n * 2; j++) { int x2,y2; bool bMove2; x2 = aMoves[j][0]; y2 = aMoves[j][1]; bMove2 = (bool)aMoves[j][2]; setField (aField2,x2,y2,bMove2);
62
107
if (aField2[x2][y2] == aField [x2][y2]) { if (checkFields(aField, aField2)) { solutionFound( j+1 ); //printf("FOUND: %ld, %ld\n", i+1,j+1); } } if (aField2[x2][y2] == aField [y2][n-x2+1]) { if (checkFields90(aField, aField2)) { solutionFound( j+1 ); //printf("FOUND90: %ld, %ld\n", i+1,j+1); } } if (aField2[x2][y2] == aField [n-x2+1][n-y2+1]) { if (checkFields180(aField, aField2)) { solutionFound( j+1 ); //printf("FOUND180: %ld, %ld\n", i+1,j+1); } } if (aField2[x2][y2] == aField [n-y2+1][x2]) { if (checkFields270(aField, aField2)) {
106
63
solutionFound( j+1 ); //printf("FOUND270: %ld, %ld\n", i+1,j+1); } } } } return 1; } // Function name
: main
// Description // Return type
: main finction : void
void main() { readFile(); iMinFirstRepeatFound = MAXMOVES + 1; run(); writeFile(iMinFirstRepeatFound); //exitprog(); } Вар иант р еш ения пр едлож и л А ндрей Ш ит о в, с тудент Чув аш с к ог о г ос уни в ер ситета. {Ш итов
А ндр ей
Н и к олаеви ч.
Чуваш с к ий
г ос удар с тв енны й
уни в ер с итет.}
const nmax=50; type matrix=array [1..nmax,1..nmax] of 0..1;
64
105
var n,move:integer; f,ff:text; a:array [1..nmax*2] of ^matrix; procedure print(m:integer); var i,j:integer; begin for j:=1 to n do begin for i:=1 to n do write(a[m]^[i,j]:3); writeln; end; end; function eq(m:integer;var tmp:matrix):boolean; var i,j:integer; begin eq:=true; for j:=1 to n do for i:=1 to n do if a[m]^[i,j]<>tmp[i,j] then begin eq:=false; exit; end; end; procedure rotate(m:integer;var tmp:matrix); var i,j:integer; begin for i:=1 to n do for j:=1 to n do tmp[i,n-j+1]:=a[m]^[j,i];
104
65
a[m]^:=tmp; end;
function check(move:integer):boolean; var m,i:integer; tmp:^matrix; begin new(tmp); check:=false; for m:=1 to move-1 do begin for i:=1 to 4 do begin rotate(m,tmp^); if eq(move,tmp^) then begin check:=true; exit; end; end; end; dispose(tmp); end; procedure body; var i,j,x,y:integer; c,tmp:char; z:boolean; begin for i:=1 to nmax*2 do new(a[i]); assign(f,'input.txt'); reset(f); assign(ff,'output.txt'); rewrite(ff);
66
103
while true do begin readln(f,n); if n=0 then break; for j:=1 to n do for i:=1 to n do a[1]^[i,j]:=0; z:=false; for move:=1 to 2*n do begin if move>1 then a[move]^:=a[move-1]^; readln(f,x,y,tmp,c); if z then continue; case c of '+':a[move]^[x,y]:=1; '-':a[move]^[x,y]:=0; end; if check(move) then begin z:=true ; writeln(ff,'Иг р ок ',(move mod 2)+1,' в ы и г р ал. Х од ',move); end; end; if not z then writeln(ff,'Н и чья'); end; close(f); close(ff); for i:=1 to nmax*2 do dispose(a[i]); end; begin body; end.
102
67
А в тор следующ ег о р еш ени я э той ж е задачи – пр изер оли мпиады , с тудент математи чес к ог о фак ультета
Калини нг р адск ог о г ос уни в ер ситета
А нт о н М их ай ло в, заняв ш и й в тор ое место. {$APPTYPE CONSOLE} uses SysUtils; const SIZE_MAX = 50; type TFld = array[1..SIZE_MAX, 1..SIZE_MAX] of Boolean; procedure Rotate(var Fld: TFld; Len: Byte); var Buf: TFld; i,j: Byte; begin for i := 1 to Len do for j := 1 to Len do Buf[j,Len-i+1] := Fld[i,j]; Fld := Buf; end; function Comp(A,B: TFld; Len: Byte): Boolean; var i,j: Integer; begin for i := 1 to Len do for j := 1 to Len do if A[i,j] <> B[i,j] then begin Comp := false; Exit; end; Comp := true; end;
68
101
var Arr
: array[1..2*SIZE_MAX] of TFld;
CurStep : Byte; Game N
: Boolean; : Byte ;
X,Y
: Byte;
Ch
: Char;
i
: Integer;
F,N,W,S,E : TFld; var FI, FO: Text; begin Assign(FI, '.in'); Assign(FO, '.out'); Reset(FI); Rewrite(FO); while true do begin Read(FI, N); if N = 0 then Break; Game := true; for i := 1 to 2*N do begin Read(FI, X,Y); Read(FI, Ch); // Чи таем пр обел Read(FI, Ch); // Чи таем значени е if Game then begin for i := 1 to
100
69
if Ch='+' then end; end; end; Close(FI); Close(FO); end. Пр едлаг аем так же ознак омитьс яс в ар иантом р еш ени яэ той же задачи , пр едложенны м
А лександро м
Л уго во вы м ,
с тудентом
М оск ов ск ой
г ос удар ственной ак адемии пр и бор ос тр оени яи инфор мати к и . program test3; {$APPTYPE CONSOLE} uses SysUtils,Classes; type tpole=array[1..50,1..50]of boolean; Ppole=^Tpole; var list:TList; function Ncomparemap(current,into:Ppole;n:byte):bOoleaN; var temp1,temp2,temp3,temp4:boolean; i,j:integer; begin temp1:=true; temp2:=true; temp3:=true;
70
99
temp4:=true; for i:=1 to n do for j:=1 to n do begin if (current^[i,j]<>into^[i,j])then temp1:=false; if current^[i,j]<>into^[j,n-i+1]then temp2:=false; if current^[i,j]<>into^[n-i+1,n-j+1]then temp3:=false; if current^[i,j]<>into^[n-j+1,i]then temp4:=false; if not(temp1 or temp2 or temp3 or temp4) then break; end; result:=not(temp1 or temp2 or temp3 or temp4); end; var A,B:PPOLE; i,j,k:byte; n:byte; fi,fo:textfile; s:string; x,y:byte ; h:char; res:boolean; begin assignfile(fi,'input.txt'); assignfile(fo,'output.txt'); rewrite(fo); reset(fi); new(a); list:=TList.Create; repeat
98
71
readln(fi,n); if n>0 then begin while list.Count>0 do begin b:=list[0]; list.Delete(0); Dispose(b); end; for i:=1 to n do for j:=1 to n do a^[i,j]:=false; k:=1; while k<=2*n do begin readln(fi,s); x:=StrToIntDef(copy(s,1,pos(' ',s)-1),1); delete(s,1,pos(' ',s)); y:=StrToIntDef(copy(s,1,pos(' ',s)-1),1); delete(s,1,pos(' ',s)); h:=s[1]; new(b); for i:=1 to n do for j:=1 to n do b^[i,j]:=a^[i,j]; b^[x,y]:=h ='+'; res:=true; if list.Count>0 then for i:=1 to list.Count do begin if not Ncomparemap(b,list[i-1],n) then begin res:=faLSE;
72
97
break; end; end; if not res then begin if odd(k) then writeln(fo,'Winner 2 in turn# ',k,'.') else writeln(fo,'Winner 1 in turn# ',k,'.'); //writeln(k); for i:=k+1 to 2*n do readln(fi,s); break; end else list.Add(b); inc(k); for i:=1 to n do for j:=1 to n do a^[i,j]:=b^[i,j]; end; if res then writeln(FO,'Ne4ia.'); end; until n=0; closefile(fi); closefile(fo); end. Интер ес ное р еш ени е пр едложи л так ж е Кам иль Хадиев, с тудент К азанс к ог о г ос уни в ер с итета. {Hadiev Kamil Ravilevich. Kazanskiy Gosudarstvenniy Universitet} {$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T+,V+,X+,Y+} {$M 65521,0,655360} const maxl=1 shl 29;
96
73
maxw=50*2; type arr=array[-4..400,1..maxw div 4]of longint; var Was:array[-4..400,1..maxw div 4]of longint; was1:array[1..3]of ^arr; a:array[1..50,1..50]of byte; Was0,i,j,hod,x,y:longint; n,Turn:integer; lose:boolean; ac:char; procedure setWas(z,x,y:longint); var i,j:longint; begin if x>maxw div 4 then begin x:=x-maxw div 4; i:=x div (maxw div 4)+1; j:=x mod (maxw div 4); if j=0 then begin dec(i); j:=(maxw div 4); end; was1[i]^[z,j]:=y; end else was[z,x]:=y; end; function GetWas(z,x:longint):longint; var i,j:longint; begin if x>maxw div 4 then begin x:=x-maxw div 4; i:=x div (maxw div 4)+1; j:=x mod (maxw div 4); if j=0 then begin
74
95
dec(i); j:=(maxw div 4); end; GetWas:=was1[i]^[z,j]; end else GetWas:=was[z,x]; end; procedure es; var l,w:longint; begin l:=1; inc(Was0); w:=1; for i:=1 to n do for j:=1 to n do begin if a[i,j]=1 then SetWas(Was0,w,GetWas(Was0,w)+l); l:=l shl 1; if l>maxl then begin l:=1; inc(w); end; end; l:=1; inc(Was0); w:=1; for i:=1 to n do for j:=1 to n do begin if a[j,n-i+1]=1 then SetWas(Was0,w,GetWas(Was0,w)+l); l:=l shl 1;
94
75
if l>maxl then begin l:=1; inc(w); end; end; l:=1; inc(Was0); w:=1; for i:=1 to n do for j:=1 to n do begin if a[n-i+1,n-j+1]=1 then SetWas(Was0,w,GetWas(Was0,w)+l); l:=l shl 1; if l>maxl then begin l:=1; inc(w); end; end; l:=1; inc(Was0); w:=1; for i:=1 to n do for j:=1 to n do begin if a[n-j+1,i]=1 then SetWas(Was0,w,GetWas(Was0,w)+l); l:=l shl 1; if l>maxl then begin l:=1; inc(w); end; end;
76
93
end; function yes(x:longint):boolean; var i,w:integer; begin yes:=true; for i:=Was0-3 to Was0 do begin for w:=1 to maxw do if (GetWas(x,w)<>GetWas(i,w)) then begin yes:=false; break; end; if GetWas(x,w)=GetWas(i,w) then begin yes:=true; exit; end; end; end; procedure init; begin fillchar(a,sizeof(a),0); Was0:=0; fillchar(was,sizeof(was),0); for i:=1 to 3 do fillchar(was1[i]^,sizeof(was1[i]^),0); Turn:=1; lose:=false; hod:=0; while not lose and (hod<2*n) do begin inc(hod); Turn:=3-Turn; read(x,y,ac,ac);
92
77
if ac='+' then a[x,y]:=1 else a[x,y]:=0; es; if was0>4 then for i:=0 to Was0-4 do if yes(i) then begin lose:=true; break; end; if lose then break; end; end; procedure print; begin if lose then writeln('Igrok ',Turn,' vigral. Hod ',hod) else writeln('Nechya'); end; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); read(n); new(was1[1]); new(was1[2]); new(was1[3]); while n<>0 do begin init; print; for i:=hod to 2*n do readln; read(n);
78
91
end; close(input); close(output); end. Задача4. Синх р онизация часов С э той задачей полностью спр авилсяли ш ь дв а участник а оли мпи ады . Пр ив едем оба р еш ени я. Пер в ое - абс олютног о победителя оли мпи ады , с тудента м атематичес к ог о
фак ультета К алини нг р адс к ог о
уни в ер си тета
Сергея Черны х .
{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T+,V+,X+,Y+} {$M 65520,0,655360} type TClocks=array[0..11] of Integer; var B,C,Len,MinLen,NZeroes:Integer; Clocks:TClocks; Commands:array[0..10,0..10] of Boolean; Commands2:array[0..10,-1..10] of Integer; NUsed,MinNUsed:array[0..11] of Byte; DontChange:Boolean; var I,J,K:Integer; First:Boolean; begin Assign(Input,'INPUT.TXT'); Assign(Output,'OUTPUT.TXT'); Reset(Input); ReWrite(Output);
90
79
FillChar(Clocks,SizeOf(Clocks),0); FillChar(Commands,SizeOf(Commands),0); ReadLn(C,B); DontChange:=True; for I:=0 to C-1 do begin Read(Clocks[I]); Clocks[I]:=(Clocks[I] div 3) and 3; if Clocks[I]<>0 then DontChange:=False; end; if DontChange=False then begin ReadLn; for I:=0 to B-1 do begin Commands2[I,-1]:=0; while not EOLn do begin Read(J); Commands[I,J]:=True; Commands2[I,Commands2[I,-1]]:=J; Inc(Commands2[I,-1]); end; ReadLn; end; NZeroes:=0; for I:=0 to C-1 do if Clocks[I]=0 then Inc(NZeroes); Len:=0; MinLen:=MaxInt; FillChar(NUsed,SizeOf(NUsed),0); repeat
80
89
if (NZeroes=C)and(Len<MinLen) then begin MinLen:=Len; MinNUsed:=NUsed; end; K:=0; Inc(NUsed[K]); Inc(Len); for I:=0 to Commands2[K,-1]-1 do begin if Clocks[Commands2[K,I]]=0 then Dec(NZeroes); Clocks[Commands2[K,I]]:=(Clocks[Commands2[K,I]]+1) and 3; if Clocks[Commands2[K,I]]=0 then Inc(NZeroes); end; while NUsed[K]=4 do begin NUsed[K]:=0; Inc(K); Inc(NUsed[K]); if K=B then Break; for I:=0 to Commands2[K,-1]-1 do begin if Clocks[Commands2[K,I]]=0 then Dec(NZeroes); Clocks[Commands2[K,I]]:=(Clocks[Commands2[K,I]]+1) and 3; if Clocks[Commands2[K,I]]=0 then Inc(NZeroes); end; Dec(Len,3); end; until NUsed[B]<>0; if MinLen=MaxInt then WriteLn('ђ Ґ и Ґ -Ёп -Ґ в ') else First:=True;
88
81
for I:=0 to B-1 do for J:=1 to MinNUsed[I] do begin
доц. О .Д .Гор бенк о О ли мпи адны е задачи по пр ог р амм ир ов анию. Лучш и е р еш ения. В в осьми частях. Час ть 8.: У чебное издани е/ О .Ф .У с к ов а, О .Д .Гор бенк о – Вор онеж : Вор онежск и й г ос удар с твенны й уни в ер си тет, 2004 –с .74
if First then begin Write(I); First:=False; end else Write(' ',I); end; end else WriteLn('Џ Ґ ॢ® ¤зб® ў -Ґ в ॠЎг Ґ в бп'); Close(Input); Close(Output); end.
Втор ое р еш ение пр едложи л В ладим ир М инин, с тудент Волог одск ог о г ос удар ственног о педаг ог и чес к ог о унив ер с итета. program Project2; {$APPTYPE CONSOLE} uses SysUtils; var fl : Boolean; ncl, ncm, i, j : Integer; coms : Array[1..11, 0..11] of Integer; clocks : Array[1..11] of Integer; besti, ri : Integer; resh, best : array[1..11] of integer;
82
87
rewrite(f1);
Procedure Solve(c, ci, ri : Integer);
reset(f);
var
readln(f,n,p);
i : Integer;
readln(f,str);
fl : boolean;
readln(f,k);
begin
if p=0 then write(f1,str[k])
if (ri+1)
else
Resh[c] := ci;
begin
for i := 1 to coms[c, 0] do inc(clocks[coms[c, i]], ci);
num[p]:=k;
fl := true;
updates['A']:='BACD';
for i := 1 to ncl do begin
updates['B']:='CBDA';
if (clocks[i] mod 4)<>0 then fl := false;
updates['C']:='DCAB';
end;
updates['D']:='ADBC';
if fl then begin
for l:=p-1 downto 0 do num[l]:=(num[l+1]-1) div 4+1;
best := resh;
ch:=str[num[0]];
besti := ri;
for l:=1 to p do
end;
begin
if c < ncm then begin
s:=updates[ch];
for i := 0 to 4 do begin
ot:=(num[l]-1) mod 4+1;
Solve(c+1, i, ri+i);
ch:=s[ot];
end;
end;
end;
end;
for i := 1 to coms[c, 0] do dec(clocks[coms[c, i]], ci);
write(f1,ch);
end;
close(f);
end;
close(f1); readln;
begin
end.
assign(input, 'input.txt'); reset(input); assign(output, 'output.txt'); rewrite(output);
А в тор ы : доц. О .Ф .У ск ов а,
readln(ncl, ncm);
86
83
for i := 1 to ncl-1 do read(clocks[i]); readln(clocks[i]);
end; end.
for i := 1 to ncl do clocks[i] := clocks[i] div 3; Задача«К ар ап улька»
for i := 1 to nc m do begin
Задача пр едлаг алась в номинации «Студентк и ». Н и ж е пр и в одитс я
j := 0; while not seekeoln(input) do begin
р еш ени е, пр едс тав ленное в не к онк ур с а студентк ой 2 к ур с а фак ультета П М М ВГУ Л юдм ило й Тюнино й .
inc(j); read(coms[i, j]);
Program Karapulko;
inc(coms[i, j]);
{А лфав ит с тр аны К ар апульк о с остои тизс имволов A,B,C,D. О днажды
end;
наим удр ей ш ий П ур ан напи сал на Н аи дли нней ш ей стене умную надпи сь,
readln;
с ос тоящ ую и з N с имв олов , и зав ещ ал с в оему нар оду пос ле велик ой
coms[i, 0] := j;
К ар апс уляции к аж ды й мес яц заменять си мв ол A на BACD, B на CBDA, C на DCAB, D на ADBC.
end;
Сос тави ть пр ог р амму нахождени я K-г о си мв ола (слев а напр ав о) в
fl := true;
надпи с и ,
for i := 1 to ncl do begin if (clocks[i] mod 4) <> 0 then fl := false;
полученной
чер ез
P
мес яцев
ос ле
велик ой
К ар апс уляции .(0<=n<=100,0<=p<=100) Входной фай л в пер вой стр ок е с одер ж итчи с ла n и p, запи с анны е чер ез
end;
пр обел, в о в тор ой стр ок е - ис ходную умную надпи сь, а в тр етьей - чис ло k
if fl then begin writeln('Пер ев од час ов не тр ебуетс я');
(чи сла n, p, k - натур альны е).
exit; end;
var
besti := 50;
l,n,p:word;
for i := 0 to 4 do Solve(1, i, i);
K,ot:LongInt;
if besti < 50 then begin
str,s:string;
for i := 1 to ncm do begin
num:array[0..100] of integer;
for j := 1 to best[i] do begin
ch:char;
write(i-1, ' ');
f,f1:text;
end;
updates:array['A'..'D'] of string;
end;
begin
end else begin
assign(f,'tekst.txt');
writeln('Р еш ени янет');
assign(f1,'output.txt');
84
85
116
113
114
115
