Ускова О.Ф., Горбенко О.Д. Олимпиадные задачи по программированию. Лучшие решения. Часть 3
Подождите немного. Документ загружается.
21
ЧУЛЮКОВ Владимир Алексеевич, доцент кафедры
информатики Воронежского госпедуниверситета
КОЛЫХАЛИН Виктор Михайлович, ООО «БУРУТ»
АРХИПОВ Виктор Петрович, зав. кафедрой математики
Старооскольского филиала МИСИС
Предполагаемые спонсоры второй открытой
региональной студенческой школы -олимпиады по
программированию и компьютерному моделированию
Администрация Воронежской области
ЗАО "РЕТ", г.Воронеж
Косметическая фирма NINELLE, Испания
ЗАО "РЕЛЭКС", г.Воронеж
Фонд С .Г.Крейна
Филиал Гута - банка в г.Ст.Оскол Белгородской
области
Российская Ассоциация "Женщины в науке и
образовании"
Российская Ассоциация "Женщины -математики "
Региональный центр фирмы «Мирра-Люкс»
ЗАО "Кедр+" , г.Воронеж.
ООО ПФ "Джуди"
ООО «БУРУТ»
ООО «Эксперт»
Фирма «Информбухгалтерия-Воронеж»
Фирма «Компьютерные технологии»
Компания «Информсвязь- Черноземье»
Издательское предприятие РадиоСофт
22
Приглашаем к сотрудничеству любые предприятия любых
форм собственности. Реклама о Вашем предприятии будет
размещена на страницах олимпиадного сайта
www.t0140.fromru.com , а также на страницах печати
Информационная поддержка открытой
региональной студенческой школы -олимпиады по
программированию и компьютерному моделированию
Воронежское государственное радио
Газета "Молодой коммунар"
Газета "Воронежский университет"
Газета "Компьютерное чтиво"
Газета «Факультет ПММ»
Газета белгородских студентов «СтуДень»
ООО ПФ «Джуди»
Приглашаем к сотрудничеству периодические издания.
ПОЛОЖЕНИЕ О ПЕРВОМ ТУРЕ
Дата проведения первого тура объявляется в Интернете и в
СМИ. Его предусмотрено провести в телекоммуникационном
режиме. Если вуз не подключен к Интернету , то получить
задания можно одним из способов:
1. Лично явиться в Оргкомитет школы - олимпиады
(Университетская пл., 1, комн.8)
2. Обратиться в ближайший Интернет-салон (например, на
главные почтовые отделения)
3. Прислать заявку на выдачу задания по электронной почте по
адресу t0140@fromru.com.
23
Филиалы университета (Лиски , Верхний Мамон , Старый
Оскол) получат задания через представителей университета на
местах, в своих учебных отделах.
На первом туре будут предложены 2 задачи : первая - общая,
вторая - учитывающая специальность участников олимпиады. К
рассмотрению принимаются работы , в которых решена хотя бы
одна задача.
Оргкомитет предупреждает, что совпадающие друг с другом с
точностью до лексемы программы рассматриваться не будут.
Решения должны быть высланы по электронной почте по
адресу T0140@fromru.com , либо представлены лично в
Оргкомитет школы - олимпиады (Университетская пл., 1, комн.8.
В самом начале программы в качестве вводного комментария
необходимо указать следующие сведения:
- фамилию, имя, отчество автора (полностью );
- представляемый вуз;
- адрес вуза;
- факультет;
- специальность (специализацию);
- форма обучения (вечерняя, заочная);
- фамилию, имя, отчество и ученое звание декана факультета ;
- фамилию, имя, отчество и ученое звание преподавателя ,
которого автор считает своим тренером (если такой есть);
- домашний адрес автора программы;
- e-mail, URL, ICQ.
Оргкомитет будет рассматривать работы только студентов
вузов.
В первом туре устанавлены следующие номинации для
участников:
24
- студенты 1 курса (независимо от специальности );
- студенты , для которых информатика является профилирующей
дисциплиной (специальности - прикладная математика,
математика, механика, физика, компьютерные науки , САПР,
информатика, вычислительные системы, системное
программирование, экономика, экономическая кибернетика,
информационные системы, информационная безопасность);
- студенты , для которых информатика является
общеобразовательной дисциплиной;
- студенты гуманитарных специальностей;
- студенты , специализирующиеся в области медицины ,
искусства, культуры , спорта .
По желанию студенты 1 курса могут перейти в номинацию,
отвечающую их специальности .
ЗАДАЧИ ПРЕДШЕСТВУЮЩИХ ОЛИМПИАД
(С КОММЕНТАРИЯМИ И РЕШЕНИЯМИ)
Задачи 1 – 4 представлены студенткой физико-
математического факультета ВГПУ Слюсаревой Еленой
Васильевной. Реализация задач осуществлялась под
руководством доцента кафедры информатики Воронежского
госпедуниверситета Л . С . Миловской
Задача 1. "Треугольник ".
Постановка задачи. На рисунке изображен треугольник из
чисел. Напишите программу, которая вычисляет наибольшую
сумму чисел, расположенных на пути , начинающемся в верхней
точке треугольника и заканчивающемся на основании
треугольника.
25
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
- Каждый шаг на пути может осуществляться вниз по
диагонали влево или вниз по диагонали вправо.
- Число строк в треугольнике >1 и <=100.
- Треугольник составлен из целых чисел от 0 до 99.
Формат входных данных: первым числом во входном файле с
именем input.txt является количество строк в треугольнике.
Формат выходных данных: в выходной файл с именем output.txt
записывается только наибольшая сумма в виде целого числа .
Пример
входные данные выходные данные
5 30
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
РЕШЕНИЕ
Это типичная задача на метод динамического
программирования. Пусть А[i,j] означает j-ое число в i-ой
строке треугольника, а S[i,j]- наибольшую сумму чисел на пути
от вершины треугольника до этого числа . Очевидны
соотношения:
S[1,1] = A[1,1]
S[i,j] = max(S[i-1, j], S[i-1,j-1]) + A[i,j] (1<=j<=I<=N, i>1)
26
Здесь мы полагаем , что числа S[i,0] и S[i,i+1] равными 0. Ответ
на задачу можно узнать, вычислив max S[N,j]
program triangle;
var A,S:array[1..100,1..100] of integer;
N,MaxS:integer;
procedure ReadData;
var i,j: integer;
begin
assign(input,'input.txt');
reset(input);
read(N);
for i:=1 to N do
for j:=1 to i do
read(A[i,j]);
close(input);
end;
function Max(a,b:integer):integer;
begin
if a>=b then Max:=a else Max:=b;
end;
procedure Solve;
var i,j:integer;
begin
S[1,1]:=A[1,1];
for i:=2 to n do begin
S[i,1]:=s[i-1,1]+A[i,1];
for j:=2 to i-1 do begin
27
S[i,j]:=Max(S[i-1,j-1], S[i-1,j])+A[i,j];
end;
S[i,i]:=S[i-1,i-1]+A[i,i];
end;
MaxS:=-1;
for j:=1 to N do
if S[N,j]>MaxS then MaxS:=S[N,j];
end;
procedure Print;
begin
assign(output,'output.txt');
rewrite(output);
write(MaxS);
close(output);
end;
begin
ReadData;
Solve;
Print;
end.
Задача 2. "Бусы ".
Постановка задачи. Имеются бусы , состоящие из N (N<=100)
бусинок, некоторые из которых красного или голубого цвета , а
остальные – белые. На рисунке 1, 2 приведены два примера бус
для N=29 (цифрами отмечены позиции первой и второй
бусинок).
28
1 2 1 2
о х х о х о о х
о x x х
о о x o
o o @ о
х о @ @
х х o o
х х х x
х х o х
о о x o
х о o о
х о o о
о о о x
о х о о х @
Рис. 1 Рис. 2
о- красная бусинка
х – голубая бусинка
@ - белая бусинка
Конфигурация бус задается последовательностью цветов
бусинок (“b” – голубая, “r” – красная, “w”- белая), начиная с
бусинки номер 1. например бусы на рисунке 1 задаются
последовательностью : brbrrrbbbrrrrrbrrbbrbbbbrrrrb.
Порвем бусы и затем начнем снимать бусинки одного
цвета с первого конца , пока не встретиться бусинка другого
цвета . То же самое проделаем со вторым концом (бусинки ,
снятые с разных концов, могут быть разного цвета ). Требуется
определить точку такого разрыва данных бус, при котором
суммарное количество бусинок, собранных с обоих концов,
максимально. Например, для бус на рисунке 1 точка разрыва
может находиться между 24 и 25 бусинками или между 9 и 10
29
бусинками; при этом суммарное количество бусинок в обоих
случаях равняется 8.
При снятии бусинок с каждого из концов белая бусинка
рассматривается как бусинка голубого или красного цвета по
ситуации, т.е . может сниматься как с голубыми, так и с
красными.
Напишите программу, которая:
1. Вводит данные из входного файла с именем bys.dat,
каждая строка которого содержит конфигурацию бус,
заданную в виде последовательности цветов и записывает
входные данные в выходной файл с именем bys.sol
2. Для каждой конфигурации бус определяет М –
максимальное число собранных бусинок и положение
одной из оптимальных точек разрыва.
3. Выводит в качестве результата в выходной файл bys.dat
число М и точку разрыва.
Пример
входные данные выходные данные
bbwbrrrwbrbrrrrrb 10 between 16 and 17
РЕШЕНИЕ
Идея решения достаточно проста . Необходимо
проверить все возможные точки разрыва и для каждой точки
разрыва определить число снимаемых бусинок. В символьном
массиве A: array [1..3*N] of char будем хранить утроенную
конфигурацию бус. Это поможет избежать трудностей при
переходе через точку «склейки» бус, т.е . от бусинки N к бусинке
1 и наоборот. Так , например, бусам , изображенным на рисунке
3, будет соответствовать символьный массив А, приведенный на
рисунке 4.
30
1
10 2
х о
@ х
х @
о @
o
Рис 3
brbwwrrbwbbrbwwrrbwbbrbwwrrbwb
Рассмотрим точку разрыва, расположенную между
бусинками с номера k и k+1 (1<=k<=N) или между бусинками N
и 1 (k=N), и положим i=k+N. Возьмем i-ый элемент массива А и
будем двигаться от него влево, «снимая» бусинки , до тех пор,
пока это возможно. Затем , аналогичным образом , будем
двигаться от элемента (i+1) вправо. Сложив число бусинок,
«снятых» при движении влево, и число бусинок, «снятых» при
движении вправо, мы получим общее число снимаемых бусинок
для данной точки разрыва.
Рассмотрим, однако, следующий вырожденный случай
бус: когда в них совсем нет либо красных, либо голубых
бусинок. В этом случае с бус можно снять все бусинки и
необходимо предупредить какой-либо «барьер» для нашего
продвижения. Этим «барьером», например, может служить
проверка того , что номер анализируемого элемента массива А
принадлежит диапазону [i-N+1..i+N-1], так как выход из этого
диапазона как раз и означает «вырожденность» бус.
1 2
101 2 1012
A: array [1..3*N] of char
i-N, при mov=-1 i
i+N, при mov=+1
Рис 4