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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

О .Ф.Ускова

О .Д .Горбенко

А . И . Шашкин

ОЛИМПИАДНЫЕ ЗАДАЧИ ПО ПРОГРАММИРОВАНИЮ .

ЛУЧШИЕ РЕШЕНИЯ

Часть 6

Учебное издание

ВОРОНЕЖ – 2003

36

ББК 32.97

УДК 681.3

Олимпиадные задачи по программированию. Лучшие решения. В

шести частях. Часть 6.: Учебное издание/ О .Ф .Ускова, О .Д .Горбенко,

А .И.Шашкин – Воронеж: Воронежский государственный университет, 2003

– 34 с.

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

интернет-олимпиады по программированию, посвященной 85-летию

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

ББК 32.97

УДК 681.3

Печатается по рекомендации редакционно-издательского совета

факультета прикладной математики , информатики и механики

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

Рецензент – кандидат физико-математических наук, доцент

Л .С.Миловская

ISBN 5-815-047-0

35

ПРЕДИСЛОВИЕ

Издание подготовлено по материалам Региональной

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

85-летию Воронежского госуниверситета, оно может быть

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

учителям информатики общеобразовательных и профильных

учебных заведений .

Организатором олимпиады является кафедра

математического обеспечения ЭВМ факультета прикладной

математики, информатики и механики Воронежского

госуниверситета.

В первой части рассматривались задачи предшествовавших

олимпиад по информатике различного уровня (факультетских,

вузовских, межвузовских, региональных, федеральных). Некоторые

задачи приведены с решениями, в основном разработанными

студентами факультета прикладной математики и механики

Воронежского университета, ставшими в свое время призерами

этих олимпиад . Во второй части помимо задач, предложенных на

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

первого (заочного) тура школы-олимпиады. В третьей части

представлены материалы Второй открытой региональной

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

компьютерному моделированию . Четвертая часть дополняет их

анализом результатов первого тура и лучшими решениями

победителей первого тура. В пятой части представлены

результаты второго тура Второй открытой региональной

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

компьютерному моделированию и избранные решения задач.

Настоящая шестая часть подводит итоги Региональной

студенческой олимпиады по программированию , посвященной 85-

летию Воронежского госуниверситета.

Авторы : доц. О .Ф .Ускова,

доц. О .Д .Горбенко,

проф . А .И.Шашкин

Олимпиадные задачи по программированию. Лучшие решения. В шести

частях. Часть 6.: Учебное издание/ О .Ф .Ускова , О .Д .Горбенко,

А .И.Шашкин – Воронеж: Воронежский государственный университет, 2003

– 34 с.

3

34

Результаты 2 тура Первой открытой региональной

студенческой школы -олимпиады

по программированию и компьютерному моделированию

Открытая региональная студенческая школа - олимпиада по

программированию и компьютерному моделированию проводится в рамках

Федеральной целевой программы "Интеграция науки и образования",

направление 2.7 "Проведение научных конкурсов, школ и конференций для

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

научных организаций ", проект Т0140. Головная организация проекта -

Воронежский государственный университет.

Ф.И.О. участников Баллы

Колбешкин Дмитрий Михайлович 11

Просин Сергей Александрович 10

Гайдай Виктор 8

Некрасов Станислав Юрьевич 8

Мухоедов Дмитрий Сергеевич 7

Гладышев Олег Викторович 6,5

Выростков Дмитрий Андреевич 6

Затворницкий Александр Петрович 6

Клинских Антон Александрович 6

Громов Станислав Андреевич 5

Корниенко Станислав Альбертович 5

Ширяев Михаил Михаилович 5

Бурнаев Константин Евгениевич 4

Новиков Александр Васильевич 4

Минаков Сергей 4

Хауи Мария 3

Абросимов Александр 2

Исаева Татьяна Михайловна 2

Катов Михаил Викторович 2

Мавлеткулов Андрей Леонидович 2

Тищенко Иван Иванович 2

found := false;

min := N;

while (min < 109) and (not found) do

begin

{проверяем только четные числа }

if min mod 2 = 0 then

begin

{находим число делителей}

if CountDividers(min) = N then

found := true;

end;

inc(min);

end;

if found then Result := min - 1

else Result:=0;

end;

begin

Assign(f,'Input.txt');

reset(f);

ReadData(f,N);

M := CountMinNum(N);

close(f);

AssignFile(f,'Output.txt');

rewrite(f);

if M > 0 then writeln(f,'Min men num -> ' + IntToStr(M))

else writeln(f,'Invalid variant num! ');

close(f);

end.

4

33

Белобродский Андрей Андреевич 1

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

Воронина Татьяна Ивановна 1

Гашков Максим Александрович 1

Гриднев Александр Николаевич 1

Десятов Алексей Дмитриевич 1

Докучав Михаил Юрьевич 1

Заколодяжный Юрий Викторович 1

Иванов Олег Олегович 1

Козлов Юрий Станиславович 1

Козлова Ольга Викторовна 1

Колесников Максим Александрович 1

Лесников Дмитрий Вячеславович 1

Малашенко Олег П 1

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

Пронин Сергей Сергеевич 1

Рышков Евгений Валерьевич 1

Семернин Сергей Павлович 1

Сувейкэ Евгений Георгиевич 1

Тузов Сергей 1

Чулюков Алексей Владимирович 1

Якунин Максим Сергеевич 1

Белоусова Юлия Владимировна 0,5

Вознюк Дмитрий Леонидович 0,5

Домбровская Ольга Валерьевна 0,5

Иванников Максим Игоревич 0,2

Иванов Андрей Васильевич 0,2

Кадимов Олег Нариманович 0,2

Карпюк Дмитрий Александрович 0,5

Комова Анна Анатольевна 0,2

Курин Михаил Сергеевич 0,5

Куропаткин Андрей Сергеевич 0,5

Логунов Сергей Иванович 0,2

Михалин Роман Валерьевич 0,2

Решение

program task1;

{$APPTYPE CONSOLE}

{Автор решения - студент 3 курса факультета компьютерных наук

Булгаков Игорь, победитель олимпиады .

Алгоритм основан на поиске четного числа обладающего количеством

делителей совпадающим с количеством способов построения участников.}

uses

SysUtils;

var

f : Text;

M,N : integer;

procedure ReadData(var f : Text; var N :integer);

begin

while not eof(f) do

readln(f,N);

end;

function CountDividers(N : integer) : integer;

var i : integer;

count : integer;

begin

count := 0;

for i := 1 to N do

if (N mod i = 0) then inc(count);

Result := count;

end;

function CountMinNum(N : integer) : integer;

var min : integer;

found : boolean;

begin

5

32

Неумывакин Сергей Сергеевич 0,2

Окунев Александр Иванович 0,5

Перов Сергей Николаевич 0,2

Савельев Константин Эдуардович 0,2

Хаустов Дмитрий Васильевич 0,2

Номинация "ПЕРВОКУРСНИКИ"

ФИО ВУЗ Баллы

Коржов Николай Евгеньевич ВГУ 13

Десятов Андрей Дмитриевич ВГУ 12

Сидоренко Станислав ВГУ 10

Владленович

Глухов Артем Леонидович ВГУ 8

Логунов Сергей Иванович ВГУ 7

Писаревский Сергей Юрьевич ВГТУ 6

Андрейчиков Василий Андреевич ВГУ 5

Колесник Артем Валерьевич ВГТА 5

Ларин Игорь Александрович ВГУ 5

Хлопков Андрей ВГУ 5

Дураков Роман Александрович ВГПУ 3

Архипова Ирина Николаевна ВГУ 1

Безродный Алексей Николаевич ВИРЭ 0

Вощинская Елена Сергеевна ВГУ 0

Лучкин Алексей Юрьевич ВГУ 0

Родионов Дмитрий Александрович ВГУ 0

Итоги Второй открытой региональной студенческой

школы – олимпиады по программированию и

компьютерному моделированию

Проект «Открытая региональная студенческая школа–олимпиада

по программированию и компьютерному моделированию», разработанный

в рамках направления 2.7 «Проведение научных конкурсов, школ и

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

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

какое минимальное число участников М ему для этого понадобится .

Например, для случая N=3 потребуется пригласить всего четыре человека,

которые могут выстроиться в 1, 2 и 4 колонны . Если же для некоторых N

потребуется более 10

9

человек, то режиссер должен отказаться от

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

невозможно.

Требуется написать программу, которая решает пocтaвлeнную перед

режиссером задачу , т.е . для заданного количества способов построения N

определяет минимальное количество участников шоу .

Технические требования :

Имя входного файла : INPUT.TXT

Имя выходного файла : OUTPUT. ТХТ

Ограничение по времени тестирования: 5 секунд па каждый тест.

Формат входных данных:

Входной файл INPUT.TXT содержит одно натуральное число N

(N<=1000), определяющее количество необходимых режиссеру способов

построения участников.

Формат выходных данных:

Выходной файл OUTPUT.ТХТ должен содержать число M, равное

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

осуществления N способов построения в процессе шоу . Если найденное

число М превосходит 10

9

, то выходной файл должен содержать только

число 0.

Примep файлов входных и выходных данных:

INPUT. Т XT OUTPUT.TXT

5 16

6 12

24 360

6

31

конференций для студентов, аспирантов, молодых преподавателей и

сотрудников вузов и научных организаций» федеральной целевой

программы «Государственная поддержка интеграции высшего образования

и фундаментальной науки» в течение двух лет становился победителем

грантов программы (в 2001 г. регистрационный номер Р0054 и в 2002 г.

регистрационный номер Т0140). Головной организацией при проведении

школы–олимпиады выступал Воронежский государственный университет.

Список соисполнителей школы – олимпиады в 2002 г. несколько изменился

и значительно расширился . Если в 2001 году соисполнителями были

Вычислительный центр им. А.А. Дородницына РАН и Воронежский

государственный педагогический университет (ВГПУ ), то в 2002 году

соисполнителями помимо ВГПУ являлись Воронежская государственная

технологическая академия, Федеральный научно–производственный центр

«Воронежский НИИ связи», Воронежский региональный центр

информатизации высшей школы , центр правовой информатики

Министерства юстиции РФ по Воронежской области .

Результаты командного зачета по итогам обоих туров:

1 место ПММ ВГУ

2 место СТИ МИС и С

3 место ВГТА

4 место ФКН ВГУ

5 место матфак ВГУ

6 место ВГТУ

7 место ВГПУ

Максимальное количество баллов, которое можно было набрать во втором

туре в основной номинации – 30 баллов. С результатом 27 баллов первое

место уверенно занял студент 3 курса факультета ПММ Выростков

Дмитрий. Он выиграл основной приз школы – олимпиады – именную

стипендию компании «Информсвязь-Черноземье». Он получил также

специальный приз ЗАО «Рет» , как отличник учебы , показавший лучший

результат. На 2-ое место с результатом 22 балла вышел студент 2 курса

ПММ Просин Сергей, победитель Первой школы – олимпиады . Он

награжден одним из основных призов олимпиады – цифровым

фотоаппаратом от ООО «OCS-

Юг». Второкурсник факультета ПММ

build[i,j,k,l] := (

(blocks[i,(k+1) mod 3] >

blocks[j,(l+1) mod 3]) and

(blocks[i,(k+2) mod 3] >

blocks[j,(l+2) mod 3])

) or (

(blocks[i,(k+1) mod 3] >

blocks[j,(l+2) mod 3]) and

(blocks[i,(k+2) mod 3] >

blocks[j,(l+1) mod 3])

);

{ Очищаем массив used - до начала строительства не использован ни

один блок }

for j := 0 to N do

used[j] := FALSE;

{ Начальная высота башни - нуль }

HCurr := 0;

{ Ставим первым блок "земля " и вызываем Recursion для решения теста

}

writeln (f_out, 'Тест ', test, ': максимальная высота = ',

Recursion (0,0));

{ Переход к следующему тесту }

inc (test);

end;

until N = 0;

{ Завершение работы }

close (f_in);

close (f_out);

END.

Задача "Шоу "

В процессе разработки сценария открытия олимпиады главный режиссер

задумал небольшое шоу с перестроением его участников в различное число

колонн ровно N способами . Для достижения наибольшего эффекта нужно

7

30

Сидоренко Станислав (результат 22 балла ) и студент СТИ МИС и С

Малашенко Олег (результат 17 баллов), занявшие 3 место , получили

музыкальные колонки от ЗАО «Рет» . Четвертое место поделили студент 3

курса ПММ Гайдай Виктор (результат 15 баллов), получивший от

президента фирмы RelaxUs (США) А.В . Пешкова (выпускника ПММ)

книгу «Ethical Hacking» объемом 720 страниц и пятикурсник ВГТА,

постоянный участник олимпиад по информатике Затворницкий Александр

(результат 12 баллов), получивший наушники от «OCS-Юг» .

Среди студенток места распределились следующим образом :

Бойченко Анастасия 3 курс ПММ – 1 место ;

Орлова Александра 3 курс ПММ – 2 место ;

Козлова Ольга СТИ МИС и С – 3 место .

Лучшим среди иногородних студентов был Малашенко Олег (17 баллов),

первое место среди студентов технических вузов занял Затворницкий

Александр (12 баллов), среди студентов военных вузов на первое место

вышел Гаршин Игорь (3 балла ).

Результаты второго тура в основной номинации:

Ф .И.О . Уч.заведение Факультет, Сумма

курс баллов

Выростков Дмитрий ВГУ ПММ 3 27

Малашенко Олег СТИ МИСиС ПМ 2 17

Виктор Гайдай ВГУ ПММ 3 15

Соломатин Алексей ВГУ ФКН 1 5,5

Лагунов Сергей ВГУ МАТ 2 5

Ларин Игорь ВГУ ПММ 2 5

Погореленко Владимир ВГУ ПММ 2 5

Просин Сергей ВГУ ПММ 2 22

Сидоренко Станислав ВГУ ПММ 2 18

Мухоедов Дмитрий ВГУ ПММ 3 4

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

Барабаш Владимир ВГУ ПММ 2 5,5

Десятов Андрей ВГУ ФКН 2 8

Хорпяков Михаил 1

Аленин Сергей ВГПУ 0,5

{ Возвращаем найденную максимальную достижимую высоту }

Recursion := HBest;

end;

BEGIN

{ Инициализация файлов }

assign (f_in, NAME_IN);

assign (f_out, NAME_OUT);

reset (f_in);

rewrite (f_out);

test := 1;

repeat

{ Выполняем тесты по очереди }

read (f_in, N);

if N <> 0 then

begin

{ Заполняем массив blocks }

{ Для блока "земля " }

for k := 0 to 2 do

blocks[0,k] := 0;

{ Для всех остальных блоков }

for j := 1 to N do

for k := 0 to 2 do

read (f_in, blocks[j,k]);

{ По массиву blocks заполняем массив build }

{ Для блока "земля " }

for j := 1 to N do

for k := 0 to 2 do

for l := 0 to 2 do

build[0,j,k,l] := TRUE;

{ Для всех остальных блоков }

for i := 1 to N do

for j := 1 to N do

for k := 0 to 2 do

for l := 0 to 2 do

8

29

Андрейчиков Василий ВГУ ПММ 2 6

Беленко Александр ВГУ ПММ 2 0,5

Бойченко Анастасия ВГУ ПММ 3 3,5

Булгаков ВГУ ФКН 2 0,3

Иванников Максим ВГТУ ФАЭМ 2 3

Карпюк Дмитрий ВВАИИ 2 0,3

Козлова Оля СТИ МИСиС 2 0,5

Колесник Артем ВГТА 3 0,3

Коржов Николай ВГУ ПММ 2 1,5

Лавский Николай СТИ МИСиС 3 0,2

Матюшевский Кирилл ВГУ ПММ 2 0,2

Новаковский Сергей ВГПУ 0,5

Орлова Александра ВГУ ПММ 3 2

Полянский Владислав ВГУ ПММ 2 1

Пронин Сергей ВГУ ПММ 3 2

Сергеев Сергей ВГПУ 2 0,3

Скрипченков Денис ВГУ ПММ 2 1

Соколов Сергей ВГУ ПММ 3 0,2

Сорокин Андрей ВГУ ПММ 2 0,3

Стешенко Сергей ВГПУ 2 0,2

Тахиров Фируз ВГТА 3 0,2

Тищенко Иван СТИ МГИСиС ТУ 3 0,2

Токарчук Роман ВГПУ 2 0,2

Черников Вячеслав ВГТУ ФАЭМ 2 0,2

Шуваев Ярослав ВГТА 3 0,1

Результаты второго тура в номинации «Первокурсники»

Ф.И.О. Уч.заведение Факультет Сумма

баллов

Николаева Татьяна Евгеньевна ВГУ физ 0,3

Драпалюк Владимир Сергеевич ВГУ физ 5

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

Мамедов Эмин Фарад Оглы ВГУ ПММ 7

Соломатин Алексей Иванович ВГУ ФКН 10

used : array [0..N_MAX] of Boolean;

{ Какие блоки мы уже использовали при строительстве башни }

HCurr : LongInt;

{ Текущая высота башни }

{ Замечание: здесь мы условно вводим блок с номером 0 - это "земля ", он

имеет высоту 0 и на него можно класть всё что угодно }

function Recursion (NewBlock, Side : Byte) : LongInt;

{ Рекурсивная функция. Определяет, какой наибольшей высоты

башни можно достичь, если поставить сейчас на неё блок с номером

NewBlock так , что его высотой будет его сторона с номером Side }

var HBest, HNew : LongInt;

jj, kk : Byte;

begin

{ Ставим новый блок }

used[NewBlock] := TRUE;

HCurr := HCurr + blocks[NewBlock,Side];

{ Пробуем продолжать строительство - перебираем все дальнейшие пути

"достраивания" башни и определяем максимальную достижимую высоту

HBest }

HBest := HCurr;

for jj := 1 to N do

if not used[jj] then

for kk := 0 to 2 do

if build[NewBlock,jj,Side,kk] then

begin

HNew := Recursion(jj,kk);

if HNew > HBest then

HBest := HNew;

end;

{ Снимаем этот блок }

used[NewBlock] := FALSE;

HCurr := HCurr - blocks[NewBlock,Side];

9

28

Шалиткин Андрей Владимирович ВГУ ПММ 5

Негодяев Алексей Михайлович ВГПУ физмат 5

Ревенко Алена Валерьевна ВГПУ физмат 0,3

Каширин Александр Николаевич ВГПУ физмат 1

Ланцузский Михаил Михайлович ВГУ физ 0,3

Цепляев Константин Юрьевич ВГУ ФКН 2

Мамонов Дмитрий Сергеевич ВГУ ПММ 7

Свиридов Андрей Александрович ВГУ физ 5

Котов Сергей Александрович ВГУ ПММ 0,5

Результаты второго тура в секции прикладного программного обеспечения

Ф.И.О. Уч.заведение Сумма

баллов

Белобродский Андрей ВГУ 14

Янин Алексей ВГПУ 14

Павлов Леонид ВГУ 12,5

Новаковский Сергей ВГПУ 12,5

Коржов Николай ВГУ 11

Лущиков Алексей ВГПУ 11

Саввин Павел ВГТА 11

Стешенко Сергей ВГПУ 10

Фурсова Ирина ВГПУ 10

ИТОГИ РЕГИОНАЛЬНОЙ СТУДЕНЧЕСКОЙ

ОЛИМПИАДЫ ПО ПРОГРАММИРОВАНИЮ ,

посвященной 85-летию Воронежского госуниверситета

Оргкомитет олимпиады

Председатель - Запрягаев Сергей Александрович, профессор, первый

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

зам . председателя - Шашкин А.И., профессор, декан факультета

прикладной математики , информатики и механики ;

Горбенко О.Д . – зав. кафедрой МО ЭВМ ВГУ ;

33 83 27

0

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

Тест 1: максимальная высота = 40

Тест 2: максимальная высота = 21

Тест 3: максимальная высота = 28

Тест 4: максимальная высота = 342

Решение

{ Автор решения - Гайдай Виктор , студент 3 курса факультета ПММ

ВГУ , специализация: системное программирование, победитель

олимпиады .

(адрес ВГУ : г. Воронеж, Университетская площадь, 1)

Адрес электронной почты : sobol@male.ru }

const NAME_IN = 'Input.txt';

NAME_OUT = 'Output.txt';

{ Имена входного и выходного файлов }

N_MAX = 30;

{ Максимальное количество блоков }

var f_in, f_out : Text;

{ Входной и выходной файлы }

test : Byte;

{ Номер текущего теста }

N : Byte;

{ Количество блоков в тесте }

i, j, k, l : Byte;

blocks : array [0..N_MAX, 0..2] of LongInt;

{ Размеры блоков; стороны пронумерованы от 0 до 2 }

build : array [0..N_MAX, 1..N_MAX, 0..2, 0..2] of Boolean;

{ "Совместимость" блоков: build[i,j,a,b] = TRUE, если на i-й блок

разрешается ставить j-й блок так , что высотой первого будет его

сторона с номером a, а высотой второго - его сторона с номером b }

10

27

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

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