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

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

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

ФЕДЕРАЦИИ

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

О .Ф.Ускова

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

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

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

Часть 5

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

ВОРОНЕЖ – 2003

ББК 32.97

УДК 681.3

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

5.: Учебное издание/ О .Ф .Ускова, О .Д .Горбенко – Воронеж: ООО ПФ

«Джуди», 2003 – 80 с.

Работа выполнена в рамках Федеральной целевой программы

«Интеграция науки и высшего образования» по направлению 2.7

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

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

организаций» (проект Т0140).

Издается при финансовой поддержке ООО ПФ «Джуди».

ББК 32.97

УДК 681.3

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

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

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

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

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

ISBN 5-815-047-0

Работа выполнена в рамках Федеральной целевой программы

«Интеграция науки и высшего образования» по направлению 2.7 «Проведение

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

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

(проект Т0140).

Издается при финансовой поддержке ООО ПФ «Джуди».

Авторы :

доцент Ускова Ольга Федоровна,

доцент Горбенко Олег Данилович

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

Часть 5.: Учебное издание/ О .Ф .Ускова, О .Д .Горбенко – Воронеж: ООО ПФ

«Джуди», 2003 – 80 с.

Редактор Андрейчикова Л .А .

Отпечатано в ООО ПФ "Джуди". Тираж 200 экз.

Лицензия №ПЛД 37-25,

г.Воронеж, ул.Свободы , 75

ПРЕДИСЛОВИЕ

Издание подготовлено в рамках проекта Т0140 Целевой

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

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

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

научных организаций»". Оно ориентировано в основном на участников

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

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

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

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

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

Организаторами школы -олимпиады являются Воронежский

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

университет , Воронежская государственная технологическая

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

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

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

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

области.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ния числа m

на n слагаемых. Вот код на языке С из самой программы:

add=1; j=1;

While (j<=(n-1)) {

add=add*(m+j)/j;

j++; }

Воронежский университет , на базе которого проводится

школа-олимпиада, выражает признательность ООО ПФ "Джуди"

(директор Андрей Васильевич Андрейчиков), оказавшему серьезную

поддержку в издании этой книги.

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

ШКОЛЫ – ОЛИМПИАДЫ ПО ПРОГРАММИРОВАНИЮ И

КОМПЬЮТЕРНОМУ МОДЕЛИРОВАНИЮ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Без финансовой поддержки ФЦП «Интеграция» и областной

Администрации проведение школы–олимпиады было бы невозможно.

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

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

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

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

состязаний, включая внутривузовские и региональные.

4 201000000… -> 201110000…

4 200200000… -> 222200000…

4 200102000… -> 211112000…

4 200100200… -> 201110200…

5) Функции перебора

Функции перебора основаны на переборе всевозможных вариантов и

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

ряду.

Пусть UnKnowW – это число неизвестных “белых” блоков.

Перебор осуществляется следующим образом :

Перебор1.

Пусть UnKnowEmpty1 – это число белых клеток,

не входящих в полные

“белые” блоки плюс число не разгаданных белых клеток.

Все варианты рассматриваются путем рассмотрения всевозможных вариантов

разбиения числа UnKnowEmpty1 на UnKnowW слагаемых, не рассматривая

нулевые слагаемые и учитывая порядок. Эта функция учитывает при

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

одна “белая” клетка, но не учитывает “белые” клетки , не принадлежащие

полным “белым” блокам .

Перебор2.

Пусть UnKnowEmpty2 – это число не разгаданных белых клеток.

Все варианты рассматриваются путем рассмотрения всевозможных вариантов

разбиения числа UnKnowEmpty2 на UnKnowW слагаемых, рассматривая

нулевые слагаемые и учитывая порядок. Эта функция не учитывает при

построении вариантов, что между “черными” блоками должн

а быть хотя бы

одна “белая” клетка, но учитывает “белые” клетки , не принадлежащие

полным “белым” блокам .

6) Число вариантов.

Подсчет числа вариантов для функций перебора осуществляется функцией,

Как и первая, вторая региональная открытая студенческая школа –

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

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

телекоммуникационном режиме, в котором могли соревноваться все

желающие, приняло участие свыше 600 студентов Воронежской,

Волгоградской, Белгородской, Липецкой, Тульской, Тамбовской областей,

среди них более 200 студентов факультета ПММ ВГУ .

В отличие от прошлогодней олимпиады нынешняя имела две секции:

– секция программирования и информационного моделирования;

– секция прикладного программного обеспечения.

При проведении практической части первой секции школы – олимпиады

была задействована лабораторная база факультета ПММ ВГУ и

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

второй секции проходила в Воронежском государственном педагогическом

университете .

Все материалы школы–олимпиады (новости , порядок проведения обоих

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

результаты и др.) регулярно размещались на страницах WEB–сайта по адресу

WWW.t0140.fromru.com. Итоги основной секции программирования и

информационного моделирования подводились по номинациям :

«Первокурсники», «Студенты , для которых информатика является

профилирующей дисциплиной», «Студенты , для которых информатика

является общеобразовательной дисциплиной», «Иногородние студенты»,

«Студенты военных вузов», «Студентки».

По итогам обоих туров школы–олимпиады студенты факультета ПММ

ВГУ одержали убедительную победу. Среди 64 студентов, прошедших во 2-

ой тур в основной номинации, половина – это обучающиеся на факультете

ПММ, среди 26 первокурсников – 8 студентов ПММ.

Награждение студентов воронежских вузов, показавших хорошие

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

заседании международной конференции «Теория конфликтов и ее

приложения». Среди награжденных были студенты ВГТА (4 человека), ВГТУ

(4 человека), ВГПУ (7 человек), матфака ВГУ (2 человека), физфака ВГУ (2

человека) и студенты ПММ ВГУ И. Ларин, С. Сидоренко , В . Барабаш , Д .

Считаем сколько вариантов надо перебрать функции перебор1 (add1) и

перебор2 (add2) (пункт 6).

Если min(add1,add2)>MAX_TIMES, то переходим к пункту 2.

Если add1<add2, то применяем функцию перебор1, иначе – перебор2.

Если ходя бы один ряд был изменен, нет ошибки , и есть пустые клетки , то

переходим к пункту 1.

Если нет пустых клеток или ошибка, то переходим к пункту 6.

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

(T).

Если ко всем рядам уже применялись функции перебора или T>MAX_TIMES,

то выполняем следующие действия.

Запоминаем расположение пустых клеток.

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

T=1.

Пока нет ошибки и есть пустые клетки , вызываем функцию главного

решателя .

Если нет ошибки , переходим к пункту 6.

Сбрасываем ошибку и восстанавливаем пустые клетки .

Самую левую верхнюю пустую клетку закрашиваем в белый цвет.

T=1.

Пока нет ошибки и есть пустые клетки , вызываем функцию главного

решателя .

Возвращаем код ошибки .

4) Логическая функция.

Идея этой функции заключается в рассмотрении некоторых частных случаев.

Вот примеры , которые описывают эти некоторые часто возникающие случаи :

4 210000000… -> 211112000…

Скрипченков, В . Погореленко, А . Сорокин, В . Андрейчиков, Д . Мухоедов, Н .

Коржов, С. Соколов, Д . Мамонов, Э . Мамедов, Е . Щербаков, В . Гайдай, Д .

Выростков, С. Полянский, С. Пронин, А . Тарасова, А . Бойченко, Л . Тюнина и

др.

Доктор физико-математических наук, профессор Волгоградского

технического университета Геннадий Ильич Брызгалин наградил студентов

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

монографией «Чудесный тайный ключ» (новое прочтение «Слова о полку

Игореве», опирающееся на уникальную закономерность, обнаруженную в

строении поэмы).

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

факультета . Призерам были вручены сувениры . Выступившие на заседании

совета декан , проф. А .И. Шашкин, проф. В .Г. Задорожний, проф. М .А .

Артемов, доц. И.Б . Руссман тепло поздравили победителей и пожелали

успеха олимпиадному движению.

В рамках школы–олимпиады проведен конкурс на лучшую эмблему. Его

победитель – магистр 1 курса Артеменко Людмила награждена денежной

премией из средств ФЦП «Интеграция».

Призы победителям предоставили известные компьютерные фирмы,

руководители которых – выпускники факультета ПММ ВГУ , в прошлом

победители подобных олимпиад и , как правило , отличники учебы :

Даньшин Борис Иванович (компания «Информсвязь-Черноземье»),

Лапыгин Дмитрий Рудольфович (ЗАО «Рет»),

Батуев Игорь Юрьевич (OCS-Юг),

Бойченко Игорь Алексеевич (ЗАО «Релекс» ),

Сисев Андрей Петрович (Издательство «РадиоСофт», Москва),

Пешков Андрей Васильевич (Relax-UZ, США),

Махортов Сергей Дмитриевич (ООО «Эксперт»).

Призы для номинации «Студентки» выделила наш постоянный спонсор в

течение четырех последних лет испанская косметическая фирма Ninelle

(бренд-менеджер по ЧЦР Галина Иванова ).

Информационную поддержку Второй открытой региональной

студенческой школе–олимпиаде оказали средства массовой информации:

Воронежское государственное радио (В.И. Новохатская, автор и ведущая

передачи «Диалоги о главном»), газета «Известия» (А. Сорокин статья «По

(пункт 2).

T=1;

Пока есть пустые клетки и нет ошибки , вызываем функцию главного

решателя (пункт 3).

Записываем полученные данные и освобождаем память.

2). Метод “пересечения”.

Над каждой строкой и каждым столбцом выполняем следующие действия:

Проходим вектор от начала до конца и записываем правые границы каждой

из групп (они будут минимальными).

Проходим вектор от конца к началу и записываем левые границы каждой из

групп (они будут максимальными).

Теперь сопоставляем для каждой группы ее минимальную правую Rmin и

максимальную левую Lmax границы . Если Rmin>=Lmax, то клетки с

номерами i, Lmax<=i<=Rmin закрашиваем в черный цвет.

3). Главный решатель .

Проходим по всем строкам и столбцам и выполняем следующие действия.

Если ряд решен или не изменялся , после того как к ряду применялась

функция перебора, то переходим к следующему ряду и опять делаем

проверку . Если ошибка переходим к пункту 6

Применяем к ряду логическую функцию (пункт 4).

Если ряд решен, то переходим к следующему ряду и к пункту 1.1.

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

а) Количество известных белых блоков.

б) Количество белых клеток в известных белых блоках.

в) Количество белых клеток.

Если количество белых клеток больше допустимого. то это ошибка и

переходим к пункту 5.

президентскому гранту»), газета «Молодой коммунар» (заметка О .

Емельяненко «Талантам надо помогать»), газета «Ф @ культет ПММ» (№ 9, №

10, гл. редактор ст . преп. Каф. ММИО И.Л . Каширина), газета «Учитель»

Воронежского государственного педагогического университета, газета «За

науку» Воронежской государственной технологической академии,

английская версия газеты «Воронежский университет».

Серьезную поддержку в публикации четырех частей учебного издания

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

ООО ПФ «Джуди». Каждая часть издана тиражом 200 экз. Все эти книги

были подарены участникам 2 тура школы – олимпиады. Первые две части

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

части рассматривались задачи предшествовавших олимпиад по информатике

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

федеральных). Некоторые задачи приведены с решениями, в основном

разработанными студентами факультета ПММ ВГУ . Во второй части помимо

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

материалы первого (заочного) тура первой школы – олимпиады 2001 года.

Авторы решений задач, представленных в первой и второй частях Поляков

А ., Мхитарян Л ., Якубенко А ., Вахтин А., Сигаева О ., Польшакова Н .,

Шахова Н ., Ромащенко А ., Гладышев О., Клинских А., Ширяев М .,

Колбешкин Д. В третьей части представлены материалы Второй открытой

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

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

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

Шалиткин А.(номинация «Первокурсники», задача «Множители и

факториалы»), Щербаков Е . (задача «Горизонты для архитектора»),

Скрипченков Д . (задача «Автобусы»), Выростков Д . (задача «Лабиринт»),

Андрейчиков В . (задача «Арифметика») и др. В четвертой части приведена

English version положения о первом туре и вариантов заданий секции

программирования и информационного моделирования. Перевод выполнен

магистрами ПММ первого года обучения Сустретовым Д., Бронякиным Д. и

Хатько В . под руководством доктора филологических наук М .А. Стерниной.

Здесь же помещен список участников второго тура всех номинаций и секций

Второй школы – олимпиады и список победителей секции прикладного

программного обеспечения и список победителей номинации

одной “белой” клеткой.

II. Обозначения и терминология.

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

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

Вектора Vj и Gi будем называть векторами групп или блоков.

Если цвет клетки еще не известен, будем называть ее пустой, а числовое

значение, соответствующее пустой клетке будет 0.

Строки и столбцы будем называть рядами.

Через Т обозначим максимальное число вариантов для функций перебора,

которое может изменяться .

А через MAX_TIMES обозначим тоже , что и через Т, только это число не

может изменяться .

III. Алгоритм .

Сделаем одно замечание по поводу матрицы А . Для упрощения алгоритмов

перебора и логических функций преобразуем матрицу А , окаймив ее белыми

клетками (то есть получим вместо матрицы mxn матрицу (m+2)x(n+2)). Это

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

хотя бы одна белая клетка.

1). Главный блок.

Инициализируем все структуры данных начальными значениями .

Проверяем на ошибки векторы групп Gi и Vi :

а) Группы указанные в векторе должны помещаться в ряде с выполнением

условий, указанных в условии задачи .

б) Сумма длин групп “черных” групп по строкам должна быть равна сумме

длин “черных” групп по столбцам .

Применяем к каждой строке и к каждому столбцу метод “пересечения”

«Первокурсники»

Как и в предыдущей школе олимпиаде 2001 года, к организации и

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

факультета ПММ, как правило , победители прошлых олимпиад :

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

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

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

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

Черноземного представительства корпорации «Парус» );

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

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

четверть финала мирового первенства по программированию, отличник

учебы , стипендиат Центрально – Черноземного представительства

корпорации «Парус» );

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

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

учебы );

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

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

учебы ).

Студенты факультета ПММ ВГУ успешно выступили как на Первой, так

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

результатом 10 баллов из 10 возможных Щербаков Евгений; Мамедов Эмин

и Мамонов Дмитрий, набрав 7 баллов, заняли 2-ое место ; Шалиткин Андрей

вышел на 3-е место с результатом 5 баллов. Первое место среди

первокурсниц заняла Тюнина Людмила . Интересно отметить, что Щербаков

Е., Шалиткин А. И Тюнина Л . были приняты на факультет ПММ ВГУ вне

конкурса как победители олимпиады по информатике среди школьников.

В секции «Прикладное программное обеспечение» лучшими среди

студентов ПММ были студенты 2 курса Павлов Леонид и Коржов Николай,

которые заняли соответственно 2-ое и 3-е место . В этой секции

безусловными лидерами были студенты ВГПУ .

Во второй тур в основной номинации прошли следующие студенты

ПММ:

inc (i, k);

end;

dec(i, k-1);

for i:=i to NumMice do L:=(L + step - 1) mod i + 1;

end

else

L:=NumMice;

write ('Надо начать с мыши под номером ');

writeln ((NumMice + NumWhite - L) mod NumMice + 1,'.');

writeln ('Нажмите esc, чтобы выйти .');

while not (readkey#27) do;

End.

Программа № 10

Японский кроссворд

Автор решения - Ларин Игорь, который учится на 2-ом курсе факультета

ПММ. В связи с большим объемом кода программы приведем только

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

I. Постановка задачи .

Японский кроссворд представляет собой зашифрованную матрицу A (mxn),

поля которой могут принимать значения либо 1 (поле закрашено в черный

цвет), либо 2 (поле закрашено в белый цвет). i-ой строке (i=1,..,m) ставится в

соответствие вектор чисел Gi, а j-ому столбцу ставится в соответствие вектор

чисел Vj. Количество чисел в векторе Gi показывает, сколько непрерывных

групп “черных” клеток находится в i-ой строке , а значение каждого числа -

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

содержит ту же информацию о j-ом столбце , только направление просмотра

становится сверху вниз. Группы “черных” клеток разделены по крайней мере

8 73

1. Андрейчиков В .А .

2. Барабаш В .В .

3. Беленко А .

4. Бойченко А .И.

5. Власов А .В .

6. Выростков Д .В .

7. Гайдай В .А .

8. Громов С.А .

9. Коржов Н .Е .

10. Ларин И.А.

11. Матвеев Н.А.

12. Матюшевский К.Л.

13. Мухоедов Д .С.

14. Погореленко В .А .

15. Полянский В.В.

16. Пронин С.С.

17. Просин С.А.

18. Сидоренко С.В .

19. Скрипченков Д .А .

20. Соколов С.А .

21. Сорокин А.И.

22. Тарасова А .С.

23. Усунов А .В .

24. Филипцов А .М .

25. Новиков А .

26. Ширяев М .М .

27. Клинских А.

28. Митогуз Д.

29. Ситникова Е .

30. Жоров М .

31. Шестопалова Е .

32. Орлова А .

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

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

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

3 место ВГТА

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

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

6 место ВГТУ

7 место ВГПУ

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

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

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

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

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

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

место с результатом 22 балла вышел студент 2 курса ПММ Просин Сергей,

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

(2) оно будет следующим:

W = (L(s, n) + f - 2) mod n +1 (7).

Найдем теперь f, если известно W. Из (7) получим, что W=L(s, n) + f – 2 + ni

+1, где i любое целое число . А значит f = (W + n – L(s, n)) mod n + 1 (8). На

формулах (2), (6), (8) и основана вся программа, а также на том , что

L(s, 1) = 1.

Program KMice;

(* Автор – Ларин Игорь, студент 2 курса факультета ПММ*)

Uses

Crt;

Var

NumMIce, Step, L, i, NumWhite, k: longint;

Begin

ClrScr;

write ('Введите число мышей: ');

read (NumMice);

write ('Введите кол-во слов в считалочке : ');

read (step);

write ('Введите номер белой мыши : ');

read (NumWhite);

if step > 1 then

begin

L:=1; i:=2; k:=1;

while i <= NumMice do

begin

L:=(L + step * k - 1) mod i + 1;

k:=(i - L) div (step - 1) + 1;

призов олимпиады – цифровым фотоаппаратом от ООО «OCS-Юг».

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

студент СТИ МИС и С Малашенко Олег (результат 17 баллов), занявшие 3

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

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

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

(выпускника ПММ) книгу «Ethical Hacking» объемом 720 страниц и

пятикурсник ВГТА , постоянный участник олимпиад по информатике

Затворницкий Александр (результат 12 баллов), получивший наушники от

«OCS-Юг».

По мнению участников 2-

го тура олимпиадные задания были

достаточно сложными: то

лько 42 % смогли набрать более 3 баллов, 12 %

показали нулевой результат и лишь 10 % набрали выше 12 баллов.

Выпускник факультета ПММ, неоднократный победитель подобных

олимпиад , ныне доцент математического факультета и директор ООО

«Эксперт» С .Д . Махортов учредил приз (модем ) лучшему участнику 2-го тура

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

половину турнирной таблицы . Этот приз получил студент 2-го курса матфака

Лагунов Сергей, набравший 5 баллов и занявший 7 место . Студент 2 курса

ФКН Десятов Андрей с результатом 8 баллов и студент 2 курса ПММ

Андрейчиков Василий заняли 5 место . Они награждены «Современным

англо -

русским словарем по вычислительной технике» (600 страниц), который

предоставил зам . директора Издательства «РадиоСофт» А . П . Сисев,

выпускник ПММ.

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

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

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

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

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

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

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

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

В рамках Второй открытой студенческой школы – олимпиады по

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

межвузовская олимпиада по информатике между студентами факультета

Теперь начнем решение основной задачи . Пусть L(s, n) – искомое число .

Выделим несколько свойств этого числа :

1) L(s, 1) = 1,

2) 1 <= L(s, n) <= n.

Допустим нам известно L(s, k - 1). Докажем , что L(s, k) = (L(s, k - 1) + s - 1)

mod k + 1.

Доказательство .

В начале нам даны k чисел и мы, начиная отсчет с единицы , вычеркиваем

число (s – 1) mod k +1. После этого у нас остается k – 1 число и отсчет уже

начинается с числа (s - 1) mod k + 2. Последнее оставшееся число будет L(s, k

- 1)-ым, если считать от (s - 1) mod k + 2, т.е . по формуле (1) это будет ((s - 1)

mod k + 2 + L(s, k - 1) - 2) mod k + 1 = (L(s, k - 1) + s - 1) mod k + 1.

Значит L(s, k) = (L(s, k - 1) + s - 1) mod k + 1, чтд .

Итак, мы вывели рекуррентную формулу

L(s, n) = (L(s, n - 1) + s - 1) mod n + 1 (2)

Основой недостаток этой формулы заключается в том , что мы двигаемся к

цели слишком медленно. Чтобы вычислить L(s, n), нам надо применить

формулу (2) n – 1 раз. Выясним, нельзя ли это сделать это быстрее.

Заметим, что если L(s, n) + s – 1 <= n, то L(s, n + 1) = L(s, n) + s и тогда L(s,

n + 2) = (L(s, n ) + 2s - 1) mod (n + 2) + 1. При этом скорость вычислений

увеличивается .

Допустим, что L(s, n) + (k-1)(s-1) <= n (3), а L(s, n) + k(s-1) >= n (4).

Преобразуем неравенство (3) следующим образом :

L(s, n) + (k - 1)s – 1 <= n + k – 2

L(s, n) + is+ (k - i - 1)s –1 <= n + k – 2

L(s, n) + is –1 <= n + k – 2 – (k – i - 1)s = n + i –1 + k – i –1 – (k – i -1)s =

= n + i – 1 – (k – i -1)(s - 1) <= n + i – 1, если k – i +1 >=0, т.е . i <= k – 1

Итак, из (3) следует, что L(s, n) + is – 1 <= n + i – 1, если i <= k – 1 (5).

Из неравенства (5) при i=1 и формулы (2) следует, что L(s, n + 1) = L(s, n) +

s, откуда L(s, n + 2) = (L(s, n) + 2s - 1) mod (n + 2) + 1. А учитывая (5) при i=2,

из предыдущего равенства получим, что L(s, n + 2) = L(s, n) + 2s, откуда L(s, n

+ 3) = (L(s, n) + 3s - 1) mod (n + 3) + 1. Продолжая так и дальше, получим, что

L(s, n + k - 1) = L(s, n) + (k - 1)s, откуда L(s, n + k) = (L(s, n) + ks - 1) mod (n +

k) + 1. И это равенство уже не упрощается , т.к. действует неравенство (4).

Найдем из (3) и (4) число k:

1) Из (3) получим, что k – 1 <= (n – L(s, n))/(s - 1).

2) Из (4) получим, что k – 1 >= (n – L(s, n))/(s - 1) –1.

Из полученных неравенств следует, что k – 1 = (n – L(s, n)) div (s - 1), откуда

k = (n –L(s, n)) div (s – 1) + 1.

L(s, n + k) = (L(s, n) + ks – 1) mod (n + k) + 1, где max(k) = (n – L(s, n)) div (s -

1) + 1 (6)

Заметим, что скорость вычисления будет тем больше, чем будет меньше s.

Допустим, мы нашли , каким будет по счету последнее оставшееся число ,

если считать от f. Ну а если мы хотим узнать само это число , то по формуле