Решение областной олимпиады школьников
по информатике, 2004 г., Кемеровская область
Морозов В. В., учитель математики и информатики МОУ "Школа № 17" г. Полысаево Кемеровской области.
Задача 1. «Условная оптимизация». (35 баллов)
Заданы два массива положительных чисел А и В. Требуется выбрать числа i1, i2, ... ik, чтобы сумма A[i1]+A[i2]+...+A[ik]<M, a сумма B[i1]+B[i2]+...+B[ik]=max была максимальной. Определите величину max.
Или: Из данных n предметов выбрать такие, чтобы их суммарный вес был менее М, а объём наибольший. Определить суммарный объём выбранных предметов.
Технические требования: имя входного файла input1.txt,
имя выходного файла output.txt
Формат входных данных:
Входной файл input1.txt состоит из следующих строк
В первой строке содержится 2 числа:
n (2<=n<=100) - размерность массивов и число М
В двух последующих строках располагаются элементы массивов А и В.
Формат выходных данных:
Выходной файл output.txt должен содержать одно число max.
Пример файлов входных и выходных файлов:
input1.txt:
5 26
30 10 10 10 5
30 10 20 10 5
Output.txt:
35.
Решение. Самая распространённая ошибка при решении этой задачи (по крайней в нашем городе (Полысаево, Кемеровской обл.)) заключалась в суммировании первых нескольких элементов массивов, например, a[1]+a[2]+...+a[k], и именно для такого рода сумм их программа находила максимальную сумму массива B. Таких сумм всего n.
На самом деле, в программе нужно перебрать всевозможные подмножества массивов, и среди них искать оптимальный набор индексов. Известно, что всего таких подмножеств 2n, что значительно больше n.
Перебирать всевозможные подмножества лучше всего с помощью двоичного представления чисел. Перебираем все числа от 0 до 2n, каждое число преобразуем в двоичное представление, и в данное множество индексов возьмём те индексы, в позиции которых записана 1 в двоичном представлении данного числа.
Например, число 17 соответствует строке '10001', будем рассматривать сумму a[1]+a[5], проверять, выполняется ли условие a[1]+a[5]<M, и если выполняется, то запомним сумму b[1]+b[5], и среди этих сумм будем запоминать максимальное.
Но можно экономнее расходовать машинное время, не тратя его на преобразование числа из десятичной в двоичную систему счисления. А именно. Например, пусть n=10. Начнём со строки С0000000000Т, которая соответствует пустому множеству. Напишем процедуру, которая выполняет двоичное сложение текущей двоичной строки с единицей. А именно: Если эта процедура получает на вход строку, скажем, '1111011011', то процедура будет просматривать эту строку слева, отыскивая первый ноль: '1111011011' и пропуская все единицы, затем процедура заменит найденный ноль единицей, а все предыдущие единицы на нули, получим: '0000111011', а следовательно получили новое множество индексов. Будем осуществлять такой перебор до тех пор, пока не получим строку из единиц. Таким образом, мы переберём все 2n подмножеств множества индексов.
Поскольку эта процедура - ключевая идея этой программы, да и любой программы, где требуется перебор всевозможных подмножеств, приведём эту процедуру здесь полностью.
...
type
...
String100=string[100];
...
procedure inc2(var h:string100); {Двоичное прибавление единицы}
var k,p:integer;
begin
if h[1]='0'
then h[1]:='1'
else
begin
{The most interesting}
k:=2;
while (h[k]='1')and(k<=nn) do inc(k);
if k<=nn
then
begin
h[k]:='1';
for p:=1 to k-1 do
h[p]:='0'
end
end
end;
Полностью программу решения этой задачи (архив с программой и входным файлом) можно скачать здесь (1K).
Задача 2. «Шифровка». (25 баллов)
Заполнить квадратную область заданным текстом по спирали, начиная от центра влево и Далее против часовой стрелки.
Технические требования: имя входного файла input2.txt,
имя выходного файла output.txt
Формат входных данных:
Входной файл input2.txt содержит текст до 1000 символов. Это шифр ключа от секретного замка
Формат выходных данных:
Выходной файл output.txt должен содержать текст расположенный по спирали, начиная от центра.
Пример файлов входных и выходных файлов:
Input2.txt:
Every hunter wishes to know where the bird is sitting! As for me I prefer to find the crocodile!
Output.txt:
! e l i d o
e m r o f s c
I e h t e r e A o
h s i w h r
p b e y r e r w ! c
r i s E v e g
e r h u n t w n e
f d t o k n o i h
e i s s i t t t
r t o f i n d
Решение. Одна из проблем, которую приходится решать в этой программе, заключается в том, что длина текста до 1000 символов. Поэтому читать файл нужно не в строку, в которой может быть не более 255 символов, а в массив символов.
Другая проблема, которая появляется при чтении текста: возможно, что человек, заполняющий текст входного файла, после текста непроизвольно стукнет по клавише Enter. К сожалению, код клавиши Enter читается в очередной элемент массива символов. При выводе этих символов на экран или в файл происходит переход на новую строку, поэтому возникают неприятности при выводе результата. Чтобы защититься от этой неприятности, при чтении текста приходится защититься от чтения нежелательных символов Enter, то есть от символов с кодом #13.
...
i:=1;
l:=true;
while (not(eof(f)))and(l) do
begin
read(f,h[i]);
l:=(h[i]<>#13); {l:boolean}
if not(l)
then
begin
h[i]:=' ';
i:=i-1
end;
inc(i)
end;
lengthh:=i-1; {Длина прочитанного текста}
...
Заполнение квадратной таблицы по спирали - известная классическая задача, её решение даже публиковалось в какой-то книжке об олимпиадах по программированию. Мы будем заполнять квадратную таблицу с правого верхнего угла, по часовой стрелке текстом, записанным в обратном порядке. Правда, при этом придётся дополнить массив строк пробелами так, чтобы длина текста стала полным квадратом.
...
i:=lengthh;
k:=trunc(sqrt(i))+1;
nn:=k*k;
for i:=lengthh+1 to nn do
h[i]:=' ';
hh:=h;
{Пишем текст в обратном порядке}
for i:=1 to nn do
hh[i]:=h[nn-i+1];
...
Теперь заполняем квадратную таблицу по спирали:
...
for m:=1 to k-1 do {Цикл по количеству витков}
begin
for i1:=m to k-m+1 do {Верхняя горизонталь}
begin
x[m,i1]:=hh[i];
inc(i)
end;
for i2:=m+1 to k-m+1 do {Правая вертикаль}
begin
x[i2,k-m+1]:=hh[i];
inc(i)
end;
for i3:=k-m downto m do {Нижняя горизонталь}
begin
x[k-m+1,i3]:=hh[i];
inc(i)
end;
for i4:=k-m downto m+1 do {Левая вертикаль}
begin
x[i4,m]:=hh[i];
inc(i)
end;
end;
...
Полностью программу решения этой задачи (архив с программой и входным файлом) можно скачать здесь (1K).
Задача 3. «Количество поворотов». (25 баллов)
Маршрут движения автомобиля задан в виде координат вершин ломанной. Необходимо определить количество левых и правых поворотов. Автомобиль начинает движение из первой вершины ломанной.
Технические требования: имя входного файла input3.txt,
имя выходного файла output.txt
Формат входных данных:
Первая строка входного файла состоит из одного числа, количества звеньев ломанной; в последующих строках - пары натуральных чисел, координаты вершин ломанной.
Формат выходных данных:
Выходной файл output.txt содержит два числа: количество левых и правых поворотов.
Пример файлов входных и выходных файлов:
Input3.txt:
4
1 1
2 2
3 2
3 3
2 3
Output.txt:
2 1
Решение. Зная координаты вершин ломанной, мы получаем последовательность векторов. Требуется получить алгоритм, который получив первый и второй векторы, определял, в какую сторону совершён поворот. Найдём векторное произведение этих векторов. Очевидно, что векторное произведение - вектор, параллельный оси аппликат, а по его направлению можно судить о повороте: если поворот от первого вектора ко второму осуществляется против часовой стрелки, то z-координата векторного произведения положительна; если поворот от первого вектора ко второму осуществляется по часовой стрелки, то z-координата векторного произведения отрицательна.
z-координата векторного произведения равна определителю 2х2, составленный из координат первого и второго вектора.
Для хранения вершин ломанной создадим следующие типы.
type Tpoint=record
x,y:real
end;
TBr=array[1..n] of TPoint;
TVector=array[1..n] of real;
Функция для вычисления векторного произведения:
function VectProd(a,b:TPoint):real;
var s:real;
begin
s:=a.x*b.y-a.y*b.x;
if abs(s)<1e-5
then VectProd:=0
else VectProd:=s
end;
Теперь осуществляем подсчёт левых и правых поворотов.
lt:=0; rt:=0;
for i:=1 to nn-1 do
begin
c[i]:=VectProd(b[i],b[i+1]);
if c[i]>0
then inc(lt);
if c[i]<0
then inc(rt);
Полностью программу решения этой задачи (архив с программой и входным файлом) можно скачать здесь (1K).
Задача 4. «Виза». (25 баллов)
Жители одного государства очень любят различные математические головоломки. Даже тот, кто желает получить въездную визу, должен решить задачу: отыскать ключевое слово. Условие задачи таково. На листке написано несколько длинных чисел. Если сложить все цифры в каждом числе, получатся новые числа. Далее следует сложить все цифры в каждом из вновь полученных чисел. Процесс следует продолжить до тех пор, пока в результате не останутся числа, меньше 10. После этого всё просто: числа от 0 до 9 - это номера букв в алфавите (в этом государстве алфавит состоит всего из 10 букв). Замена чисел буквами и даёт ключевое слово. Напишите программу, которая будет отыскивать ключевое слово.
Технические требования: имя входного файла input4.txt,
имя выходного файла output.txt
Формат входных данных:
Первая строка - алфавит государства: 10 букв, расположенных по возрастанию порядковых номеров без пробелов.
Вторая строка количество чисел (n<=255).
Следующие n строк - собственно исходные числа, по одному на строке, в каждом не более 255 цифр.
Формат выходных данных:
Ключевое слово
Пример файлов входных и выходных файлов:
Input4.txt:
AGEIKLMORT
4
8267
19929
54262
0000000000000
Output.txt:
LIGA
Решение. Очевидно, что при многократном сложении цифр ноль может получиться только если все цифры числа - нули. В журнале Математика в школе, № 8, 2000 доказано [Морозов В.В.], что окончательная сумма цифр натурального числа равна остатку от деления этого числа на основание системы счисления, то есть на 9; если остаток от деления на 9 равен 0, то окончательная сумма цифр натурального числа равна 9. Программист может использовать этот факт для вычисления окончательной суммы. Функция ff на вход получает строку из цифр, а на выходе стрку-окончательную сумму цифр.
function ff(hhh:string):string; {Вычисление окончательной суммы цифр}
var i,s,code:integer;
hh:string;
v:longint;
begin
val(hhh,v,code);
if v=0
then s:=0
else
begin
s:=v mod 9;
if s=0 then s:=9
end;
str(s,hh);
ff:=hh[1]
end;
Далее всё просто.
Полностью программу решения этой задачи (архив с программой и входным файлом) можно скачать здесь (1K).
Вопросы и замечания можно отправить автору статьи Морозову В. В.