Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения: Учебное издание. Часть 6

Подождите немного. Документ загружается.

Артемов М .А. – профессор факультета прикладной математики ,

информатики и механики ;

Леденева Т .М ., профессор, председатель научно-методического совета

факультета ПММ;

Ускова О .Ф ., доцент кафедры МО ЭВМ ВГУ ;

Гудович И.С., к .ф .-м .н ., президент Воронежского отделения МОО

"Женщины в науке и образовании";

Перелыгина З.Н. – зав.лабораторией ВГУ ;

Гришаев О.В. – помощник проректора по общим вопросам .

Студенческий директорат:

- Поляков Андрей (магистрант второго года обучения, соросовский

студент, неоднократный победитель межвузовских студенческих

олимпиад , призер четверть-финала мирового первенства по

программированию, отличник учебы ),

- Ефремов Максим (магистрант второго года обучения, победитель

факультетской студенческой олимпиады , отличник учебы ),

- Мхитарян Лусине (магистрант второго года обучения, победитель

университетской студенческой олимпиады),

- Вахтин Алексей (аспирант факультета компьютерных наук,

победитель факультетской студенческой олимпиады ),

- Якубенко Андрей (магистрант второго года обучения, неоднократный

победитель межвузовских студенческих олимпиад , призер четверть-

финала мирового первенства по программированию, отличник учебы ).

Спонсоры региональной студенческой олимпиады по программированию

Ректорат Воронежского госуниверситета

Косметическая фирма NINELLE (Испания)

ЗАО "РЕЛЭКС", г.Воронеж

Издательское предприятие РадиоСофт

ООО «О CS-Юг»

Компания RELAX-US (США)

Косметическая фирма «Лонда Косметик», Германия

Газета «Компьютерра» , региональный выпуск

так , что его два размера определяли размер основания, и третий размер

являлся высотой. Задачей являлось построение башни наибольшей высоты ,

размещая один блок над другим. Однако каждый вышестоящий блок

должен располагаться (лежать) на блоке с большим основанием как по

ширине, так и по длине. Вашей задачей является построение такой башни

из заданного набор блоков.

Входные и выходные данные

Входной файл INPUT.TXT содержит один или несколько тестовых

примеров. Первая строка содержит число n определяющее количество

различных типов блоков, n <= 30. Каждая из следующих n строк содержит

три целых числа , которые являются размерами блока. Ввод заканчивается

нулем в качестве числа n.

Для каждого теста напечатайте одну строку с номером теста и

максимальной высотой.

Пример входных данных

10 20 30

6 8 10

5 5 5

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

7 7 7

31 41 59

26 53 58

97 93 23

84 62 64

Результаты олимпиады в номинациях

Номинация "Информатика как профилирующая дисциплина"

ФИО Учебное заведение Итог

Мухоедов Дмитрий ПММ 21

Гайдай Виктор Александрович ПММ 20

Мамедов Эмин Фархад оглы ПММ 17

Просин Сергей ПММ 16

Андриянов Дмитрий Иванович БелГТУ 16

Пузанок Алексей Иванович БелГТУ 14

Коршиков Алексей Вячеславович БелГТУ 12

Сорокин Андрей ПММ 12

Коржов Николай Евгеньевич ПММ 12

Ларин Игорь ПММ 11

Щербаков Евгений Анатольевич; ПММ 10

Гурова Мария Владимировна ПММ 10

Сидорова Марина ПММ 10

Тузов Сергей ПММ 10

Петров Константин Владимирович ПММ 9

Барабаш Владимир Вячеславович ПММ 8

Матюшевский Кирил ПММ 8

Сидоренко С.В. ПММ 8

Фирсов Максим Юрьевич ПММ 8

Бойченко Анастасия Игоревна ПММ 8

Погореленко Владимир ПММ 7

Скрипченков Денис ПММ 7

Ястреб Олег Игоревич ПММ 7

Беленко Павел Викторович ФКН 6

Годунов Денис Витальевич ПММ 6

Головков Александр Вячеславович БелГТУ 6

Лепендин А.В. ПММ 6

begin

assign(input, inf);

reset(input);

assign(output, outf);

rewrite(output);

read(n);

for n1:=1 to n do

begin

getWord; { Пропускаем BEGIN }

maxStn:=0;

looper(0, 1);

outAnswer(n1);

end;

close(input);

close(output);

end.

Задача «Вавилонская башня»

Возможно, вы слышали легенду о Вавилонской башне. В наше

время многие детали этой истории забыты . Однако в целях образования, мы

вспомним некоторые детали .

Жители Вавилона имели в своем распоряжении n типов различных

строительных блоков. Каждый тип представлял собой параллелепипед с

соответствующими размерами Xi,Yi,Zi. Блок можно было переворачивать

Новиченко Андрей Валеревич БелГТУ

Прудников Владимир Евгеньевич ПММ 6

Булгаков Игорь Александрович ФКН 6

Хорпяков Михаил Юрьевич ФКН 6

Жукова Анна ПММ 6

Сахинов Константин Владимирович БелГТУ 5

Стрельникова Елена ПММ 5

Лобачев Руслан Владимирович БелГТУ 4

Усунов Александр Витальевич ПММ 4

Зензина Ксения Андреевна ПММ 4

Ситало Алексей Юрьевич БелГТУ 3

Матвеев Николай Александрович ПММ 3

Останин Дмитрий Александрович ФКН 3

Павлов Леонид ПММ 3

Дудин Алексей Николаевич БелГТУ 2

Михайлов Никита Владимирович БелГТУ 2

Потапов Николай ПММ 2

Свиридов Виталий ПММ 8

Кравченко Виталий Сергеевич ПММ 1

Носарев Михаил Александрович БелГТУ 1

Жукова Анна Александровна ПММ 6

Стрельникова Елена ПММ 5

Номинация "Информатика - общеобразовательная дисциплина"

ФИО Учебное Сумма

заведение баллов

Карпюк Дмитрий Александрович ВВАИИ 12

Коршиков Алексей Вячеславович БелГТУ 12

Черниенко Василий Валерьевич Украина, Сев. ХМТ 11

Братков Дмитрий Иванович ВИРЭ 6

Гаршин Игорь ВВАИИ 6

Козлова Ольга СТИ МИСиС 6

end;

{ Выводим в файл ответ в соответсвии с условием задачи }

procedure outAnswer(pNumber: integer);

var i: integer;

procedure out(i: integer);

begin

if (i=0) then

write(p[i])

else

begin

if (p[i]>1) then write(p[i],'*');

write('n');

if (i>1) then write('^', i);

end;

p[i]:=0;

end;

begin

writeLn('Программа #', pNumber);

write('Время=');

out(maxStn);

for i:=maxStn-1 downto 0 do

if (p[i]<>0) then begin write('+'); out(i); end;

writeLn; { После каждой программы выводится чистая строка }

end;

Лавский Николай Михайлович СТИ МИСиС

Малашенко Олег Валериевич Стар.Оск . Т И6

Тищенко Иван СТИ МИСиС 6

Якушев Александр Борисович геогр. фак 6

Сахинов Константин Владимирович БелГТУ 5

Рашитов СТИ МИСиС 4

Гусев Борис Леонидович ВГТУ 4

Глазкова Елена Николаевна ВГТА 3

Пашенцева Евгения Сергеевна ВГТА 3

Ситало Алексей Юрьевич БелГТУ 3

Зотова Александра Евгеньевна геогр. 2

Инкогнито 2

Михайлов Никита Владимирович БелГТУ 2

Молодкин Дмитрий ВВАИИ 2

Шуваев Ярослав ВГТА 2

Жокин Андрей Юрьевич ВВАИ 1

Плешкова Оксана Игоревна геогр.фак 1

Ходос СТИ МИСиС 1

Номинация " Физико-математические специальности"

ФИО Учеб. зав. Сумма баллов

Логунов Сергей мат.фак . 11

Cвиридов Андрей Александрович физ.фак 6

Номинация "Студентки"

ФИО Учеб.зав. Сумма баллов

Гурова Мария Владимимровна ПММ 10

Сидорова Марина ПММ 10

Бойченко Анастасия Игоревна ПММ 8

Козлова Ольга СТИ МИСиС 6

Жукова Анна ПММ 6

Стрельникова Елена ПММ 5

{

Увеличивается степень полинома. Знание ее облегчает вывод , в частности

время работы программы BEGIN END

}

if (maxStn<stn) then maxStn:=stn;

repeat

s:=getWord;

if (s='LOOP') then

begin

s:=getWord;

if (s='n') then { Переходим на следующий уровень вложенности }

looper(stn+1, mul)

else { Если встретили LOOP <n[k]>, то его "тело " будет выполняться

<n[k]> раз, а с учетом предыдущих вложенностей

LOOP <n[1]> ... LOOP <n[k-1]> (<n1>*...*<nk-1>=mul),

то mul*<nk> раз

}

looper(stn, mul*strToInt(s))

end

else

if (s='OP') then {Изменяем коэффициент с учетом <n[1]*..*n[k-1]>}

p[stn]:=p[stn]+mul*strToInt(getWord)

else

endd:=(s='END') or (eof); { Встретили END - выходим из процедуры }

until endd;

Бондаренко Мария Александровна биол.-почв.фак . 5

Зензина Ксения Андреевна ПММ 4

Глазкова Елена Николаевна ВГТА 3

Пашенцева Евгения Сергеевна ВГТА 3

Зотова Александра Евгеньевна геогр. фак 2

Плешкова Оксана Игоревна геогр. фак 1

Номинация "Естественно-географические специальности"

ФИО Учебное Сумма

заведение баллов

Вахтин Сергей Александрович геогр. фак . ВГУ 7

Якушев Александр Борисович геогр . фак . ВГУ 6

Бондаренко Мария Александровна биол.-почв.фак .ВГУ 5

Зотова Александра Евгеньевна геогр. фак . ВГУ 2

Плешкова Оксана Игоревна геогр. фак . ВГУ 1

Номинация "Технические и военные вузы "

ФИО Учебное заведение Сумма баллов

Андриянов Дмитрий Иванович БелГТУ 16

Пузанок Алексей Иванович БелГТУ 14

Карпюк Дмитрий Александрович ВВАИИ 12

Коршиков Алексей Вячеславович БелГТУ 12

Черниенко Василий Валерьевич Украина, Северодо- 9

нецкий ХМТ

Братков Дмитрий Иванович ВИРЭ 6

Гаршин Игорь ВВАИИ 6

Головков Александр Вячеславович БелГТУ 6

Козлова О . СТИ МИСиС 6

Лавский Николай Михайлович СТИ МИСиС 6

Малашенко Олег Валериевич Стар.Оск . Т И 6

Новиченко Андрей Валеревич БелГТУ 6

read(c);

end;

getWord:=s;

end;

{ stn - текщая степень вложенности

mul - коэффициент }

{ Рассмотрим как они должны меняться при рекурсивном вызове looper и

как

влияют на коэффициент при n^stn.

p[i] - коэффициент P(n) при n^stn.

1. ... LOOP <n1> OP <n2> ... END OP <n3> ...

p[i]=p[i]+<n1>*(<n2>+... ) + <n3>

2. ... LOOP <n1> LOOP n LOOP <n2> OP <n3> END OP <n4> END ... END

При вычислении p[i+1] уже должен будет учитываться <n1>:

p[i+1]=p[i+1]+<n1>*(<n2>*<n3>+<n4>)

Роль "накопленого" множителя и выполняет mul.

}

procedure looper(stn, mul: UINT);

var endd: boolean;

s: string;

begin

endd:=false;

Тищенко Иван СТИ МИСиС

Сахинов Константин Владимирович БелГТУ 5

Лобачев Руслан Владимирович БелГТУ 4

Рашитов СТИ МИСиС 4

Гусев Борис Леонидович ВГТУ 4

Глазкова Елена Николаевна ВГТА 3

Пашенцева Евгения Сергеевна ВГТА 3

Ситало Алексей Юрьевич БелГТУ 3

Дудин Алексей Николаевич БелГТУ 2

Михайлов Никита Владимирович БелГТУ 2

Молодкин Дмитрий ВВАИИ 2

Шуваев Ярослав ВГТА 2

Жокин Андрей Юрьевич ВВАИ 1

Носарев Михаил Александрович БелГТУ 1

Ходос СТИ МИСиС 1

Номинация "ВГУ - 85 лет"

ФИО Факультет Сумма баллов

Мухоедов Дмитрий ПММ 21

Гайдай Виктор Александрович ПММ 20

Мамедов Эмин Фархад оглы ПММ 17

Просин Сергей ПММ 16

Сорокин Андрей ПММ 12

Коржов Николай Евгеньевич ПММ 12

Ларин Игорь ПММ 11

Логунов Сергей Мат.фак . 11

Тузов Сергей ПММ 10

Щербаков Евгений Анатольевич ПММ 10

Гурова Мария Владимимровна ПММ 10

Сидорова Марина ПММ 10

Петров Константин Владимирович ПММ 9

Барабаш Владимир Вячеславович ПММ 8

function strToInt(s: string): UINT;

var i, x, ff: UINT;

begin

x:=0;

ff:=1;

for i:=length(s) downto 1 do

begin

x:=x+(ord(s[i])-ze)*ff;

ff:=ff*10;

end;

strToInt:=x;

end;

{ Чтение следующего оператора из файла }

function getWord: string;

var i: integer; s: string; c: char;

begin

repeat

read(c);

until (c in ss) or (eof);

s:='';

while (c in ss) do

begin

s:=s+c;

Матюшевский Кирил ПММ

Сидоренко С.В . ПММ 8

Фирсов Максим Юрьевич ПММ 8

Бойченко Анастасия Игоревна ПММ 8

Свиридов Виталий ПММ 8

Погореленко Владимир ПММ 7

Скрипченков Денис ПММ 7

Ястреб Олег Игоревич ПММ 7

Вахтин Сергей Александрович геогр .фак . 7

Cвиридов Андрей Александрович Физфак 6

Беленко Павел Викторович ФКН 6

Годунов Денис Витальевич ПММ 6

Лепендин А.В. ПММ 6

Прудников Владимир Евгеньевич ПММ 6

Якушев Александр Борисович геогр . фак 6

Булгаков Игорь Александрович ФКН 6

Хорпяков Михаил Юрьевич ФКН 6

Жукова Анна Александровна ПММ 6

Стрельникова Елена ПММ 5

Бондаренко Мария Александровна биол.-почв.фак . 5

Стрельникова Елена ПММ 5

Усунов Александр Витальевич ПММ 4

Зензина Ксения Андреевна ПММ 4

Матвеев Николай Александрович ПММ 3

Останин Дмитрий Александрович ФКН 3

Павлов Леонид ПММ 3

Зотова Александра Евгеньевна геогр .фак . 2

Потапов Николай ПММ 2

Кравченко Виталий Сергеевич ПММ 1

Плешкова Оксана Игоревна геогр . фак 1

Решение

Автор решения - Мухоедов Дмитрий , студ . 3 курса кафедры МО ЭВМ

факультета ПММ, абсолютный победитель олимпиады .

{ Предполагается , что в задаваемой программе нет ошибок }

type

UINT = 0..maxLongInt;

TArr = array[0..10] of UINT; { deg P(n)==10 => максимум 11

коэффициентов }

const

inf = 'input.txt';

outf = 'output.txt';

{ Все остальные символы в программе появляться не могут }

ss : set of char = ['B','E','G','I','N','O','P','L','D', 'n', '0'..'9'];

ze = ord('0');

var

p : TArr; { Массив, в котором будем хранить коэффициенты полинома }

maxStn: UINT; { Максимальная степень полинома }

n, n1: UINT;

{ Преобразование содержимого строки в неотрицательное целое число }

Избранные задачи и решения

Задача «Считаем сложность»

Инструменты для анализа сложности алгоритмов очень важны при

разработке эффективных программ. Алгоритм , который работает линейное

время, обычно намного быстрее, чем алгоритм использующий

квадратичное время решения для той же задачи и его использование

конечно предпочтительней.

Обычно, одним из возможных методов определения времени работы

алгоритма, является нахождение зависимости времени работы алгоритма

от размера n, который может определять количество хранимых объектов,

количество точек в полигоне и т.д. Эту непростую задачу подсчета

хотелось бы автоматизировать для простейших программ, т.к . для сложных

это не вполне возможно. Наши программы будут очень простыми , и их

построение будет определено следующими правилами.

• < Программа > ::= "BEGIN" < Список операторов > "END"

• < Список операторов > ::= < Оператор > | < Оператор > < Список

операторов >

• < Оператор > ::= < LOOP- Оператор > | < OP- Оператор >

• < LOOP- Оператор > ::= < LOOP-Заголовок > < Список

операторов > "END"

• < LOOP-Заголовок > ::= "LOOP" < число > | "LOOP n"

• < OP- Оператор > ::= "OP" < число >

Время выполнения программы определяется следующим образом :

выполнение каждого OP-оператора происходит столько раз, сколько

указано его параметром . Список операторов заключенный в цикл LOOP

столько раз, сколько указано параметром цикла , т.е . либо указанной

константой или n раз. Время выполнения списка операторов равно сумме

времен для каждого оператора, входящего в список. Общее время

выполнения обычно зависит от n.

Входные данные

Входной файл (или ввод с клавиатуры ) начинается с указания на отдельной

строке количества программ k, которые будут введены в соответствии с

указанными правилами . Пробелы и символы конца строки могут появится в

любом месте программы , но не внутри ключевых слов и числовых

параметров. Максимальная глубина вложенности операторов LOOP равна

10.

Выходные данные

Для каждой программы выводится ее номер, как показано в примере . Затем

выводится время ее работы в виде полинома, степень которого не больше

чем 10. Печать полинома должна быть организована привычным способом

в форме ``Время = a*n^10+b*n^9+ . . . +i*n^2+ j*n+k'', при этом

слагаемые с нулевыми коэффициентами пропускаются , а множитель 1 не

выводится . После каждой программы выводится чистая строка.

Пример входных данных

BEGIN

LOOP n

OP 4

LOOP 3

LOOP n

OP 1

END

OP 2

END

OP 1

END

OP 17

END

BEGIN

OP 1997 LOOP n LOOP n OP 1 END END

END

Пример выходных данных

Программа #1

Время = 3*n^2+11^n+17

Программа #2

Время = n^2+1997