Задача 1. “Условная оптимизация”. Заданы два массива положительных чисел А и В. Требуется выбрать числа i1, i2, ... ik, чтобы сумма A[i1] + A[i2] + ... + A[ik] < M, a сумма B[i1] + B[i2] + ... + B[ik] = max была максимальной. Определите величину max.
Технические требования: имя входного файла 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]. Таких сумм всего 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 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;
Полностью программу решения этой задачи (архив с программой и входным файлом) смотрите в <Приложении 1>.
Задача 2. “Шифровка”. Заполнить квадратную область заданным текстом по спирали, начиная от центра влево и далее против часовой стрелки.
Технические требования: имя входного файла 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:
Решение. Одна из проблем, которую приходится решать в этой программе, заключается в том, что длина текста до 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); 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;
Полностью программу решения этой задачи (архив с программой и входным файлом) можно посмотреть в <Приложении 2>.
Задача 3. “Количество поворотов”. Маршрут движения автомобиля задан в виде координат вершин ломанной. Необходимо определить количество левых и правых поворотов. Автомобиль начинает движение из первой вершины ломанной.
Технические требования: имя входного файла input3.txt, имя выходного файла output.txt
Формат входных данных: Первая строка входного файла состоит из одного числа, количества звеньев ломанной; в последующих строках – пары натуральных чисел, координаты вершин ломанной.
Формат выходных данных: Выходной файл output.txt содержит два числа: количество левых и правых поворотов.
Пример файлов входных и выходных файлов: Input3.txt: 4; 1 1; 2 2; 3 2; 3 3; 2 3. Output.txt: 2 1.
Решение. Зная координаты вершин ломанной, мы получаем последовательность векторов в плоскости ХОY. Требуется написать алгоритм, который, получив первый и второй векторы, определял, в какую сторону совершён поворот. Найдём векторное произведение этих векторов. Векторное произведение – это вектор, параллельный оси аппликат, а по его направлению можно судить о повороте: если поворот от первого вектора ко второму осуществляется против часовой стрелки, то z-координата векторного произведения положительна; если поворот от первого вектора ко второму осуществляется по часовой стрелки, то z-координата векторного произведения отрицательна. z-координата векторного произведения равна определителю, составленному из координат первого и второго вектора. Для хранения вершин ломанной создадим следующие типы.
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;
Теперь осуществляем подсчёт левых и правых поворотов. Если соседние векторы сонаправлены или противоположно направлены, то их векторное произведение равно нулю, и количество поворотов не изменяется. (В следующем ниже коде b – массив элементов типа TPoint, координаты векторов).
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); end;
Полностью программу решения этой задачи (архив с программой и входным файлом) можно посмотреть в <Приложении 3>.
Задача 4. “Виза”. Жители одного государства очень любят различные математические головоломки. Даже тот, кто желает получить въездную визу, должен решить задачу: отыскать ключевое слово. Условие задачи таково. На листке написано несколько длинных чисел. Если сложить все цифры в каждом числе, получатся новые числа. Далее следует сложить все цифры в каждом из вновь полученных чисел. Процесс следует продолжить до тех пор, пока в результате не останутся числа, меньше 10. После этого всё просто: числа от 0 до 9 – это номера букв в алфавите (в этом государстве алфавит состоит всего из 10 букв). Замена чисел буквами и даёт ключевое слово. Напишите программу, которая будет отыскивать ключевое слово.
Технические требования: имя входного файла input4.txt, имя выходного файла output.txt
Формат входных данных: Первая строка
– алфавит государства: 10 букв, расположенных по
возрастанию порядковых номеров без пробелов.
Вторая строка количество чисел (n< = 255).
Следующие n строк – исходные числа, по одному на
строке, в каждом не более 255 цифр.
Формат выходных данных: Ключевое слово
Пример файлов входных и выходных файлов: Input4.txt: AGEIKLMORT; 4; 8267; 19929; 54262; 0000000000000. Output.txt: LIGA.
Решение. Очевидно, что при многократном сложении цифр ноль может получиться только если все цифры числа – нули. В [1] доказано, что окончательная сумма цифр натурального числа равна остатку от деления этого числа на основание системы счисления, то есть на 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;
Полностью программу решения этой задачи (архив с программой и входным файлом) можно посмотреть в <Приложении 4>.
Задача 5. “Противометеоритная
защита”. Для защиты космической станции от
метеоритного дождя сделана специальная
установка. Все метеориты засекаются радаром,
после чего мощный лазер просто испаряет их.
Внешнее сечение станции представляет собой
квадрат. Лазерная установка находится в глубине
станции на расстоянии Н от внешнего её сечения в
центре сечения станции. Мощности лазера хватает
на испарение метеоритов на дальности не более D.
Метеориты летят перпендикулярно сечению
станции. Дальности стрельбы достаточно для того,
чтобы сбивать метеориты до того, как они долетят
до плоскости внешнего сечения станции. Более
того, установка в порядке благотворительности
сбивает даже те метеориты, которые не попадают в
станцию. Требуется определить, сколько
метеоритов из тех, что видно на радаре, будет
сбито.
Входной файл input.txt: Первая строка содержит Н (1.00<
= H< = 100.00). Следующие 4 строки содержат пары
вещественных чисел – координаты вершин
космической станции. На следующей строке
находится D (Н<D<1000.00). После этого строка,
содержащая k (1< = k< = 100) – количество
метеоритов. Следующие k строк содержат пары
вещественных чисел – координаты метеоритов в
плоскости сечения станции. Все координаты по
модулю не превосходят 1000.
Пример входного файла: 10.00; 1.00 0.00; 0.00 1.00; -1.00 0.00; 0.00 -1.00; 50.00; 5; 0.00 0.00; 1.00 1.00; 2.00 2.00; 3.00 3.00; 4.00 4.00.
Пример выходного файла: output.txt: 3_
Решение. Сначала найдём координаты пушки – точки Р(px,py,pz). Систему координат расположим так, чтобы ось OZ была направлена через пушку навстречу метеоритам, квадрат располагался в плоскости XOY, а начало координат – в плоскости квадрата. Посмотрим на рисунок 1. Ясно, что лазер в состоянии испарить метеорит, если он попадёт в сферу радиуса d с центром в пушке P, а также если этот метеорит будет засечён радаром, то есть, если он попадёт в бесконечную пирамиду (см. рис. 1). Поэтому найдём координаты точки Q на сфере, куда попадёт метеорит. При этом возможна ситуация, когда метеорит вообще пройдёт мимо сферы, то есть заведомо вне пределов досягаемости пушки.
Пусть координаты данного метеорита (x,y). Координату z точки Q на сфере находим так:
z: = pz + sqrt(d*d – (x – px)*(x – px) – (y – py) * (y – py));
Находим координаты вектора PQ.
p: = x – px; q: = y – py; r: = z – pz;
Получаем уравнение прямой PQ (точка с координатами (xx,yy) – точка на прямой PQ):
(xx – px)/p = (yy – py)/q = (0 – pz)/r.
Отсюда находим координаты пересечения прямой PQ и плоскости станции. Так мы узнаем, попадает ли метеорит одновременно и в сферу, и в бесконечную пирамиду.
xx: = px – p*pz/r; yy: = py – q*pz/r;
Итак, точка R(xx,yy) в плоскости квадрата найдена. Осталось определить, попала ли точка R в квадрат. Посмотрите на рисунок 2.
Очевидно, что точка R попадает в квадрат (а может и в его границу), если и только если сумма площадей четырёх треугольников S1 + S2 + S3 + S4 равна площади квадрата. Для этого нам потребуется функция, которая по трём вершинам треугольника будет находить его площадь. Это удобно осуществить по формуле Герона.
function striangle(aax,aay,bbx,bby,ccx,ccy:real):real;
var a,b,c,p:real;
begin
c: = sqrt(sqr(aax – bbx) + sqr(aay – bby)); b: = sqrt(sqr(aax – ccx) + sqr(aay – ccy));
a: = sqrt(sqr(ccx – bbx) + sqr(ccy – bby)); p: = (a + b + c)/2; striangle: = sqrt(p*(p – a)*(p-b)*(p – c));
end;
Функция, определяющая, можно ли сбить данный метеорит:
function ff(x,y:real):boolean; {Функция проверяет, попадает ли метеорит в зону действия радара и находится в пределах досягаемости лазера}
var ss,sss,xx,yy,px,py,pz,z,p,q,r,s1,s2,s3,s4,qq:real;
begin {Координаты лазерной пушки:} px: = (ax + bx + cx + dx)/4; py: = (ay + by + cy + dy)/4; pz: = – h;
{Отыскиваем координату z так, чтобы точка с координатами (x,y,z) была на сфере радиуса d с центром лазерной пушке}
qq: = d*d – (x – px)*(x – px) – (y – py)*(y – py);
if qq<0 then ff: = false {Метеорит не пересекает сферу и проходит слишком далеко}
else begin z: = pz + sqrt(qq); p: = x – px; q: = y – py; r: = z – pz;
{(p,q,r) – координаты вектора с началом в пушке и концом в точке (x,y,z) на сфере. Находим координаты пересечения прямой (пушка-точка на сфере) с плоскостью z = 0, с плоскостью станции:}
xx: = px-p*pz/r; yy: = py – q*pz/r; {проверяем, попала ли точка (xx,yy) внутрь квадрата, иными словами, достигает ли пушка мееторита}
s1: = striangle(ax,ay,bx,by,xx,yy); s2: = striangle(bx,by,cx,cy,xx,yy);
s3: = striangle(cx,cy,dx,dy,xx,yy); s4: = striangle(dx,dy,ax,ay,xx,yy);
ss: = s1 + s2 + s3 + s4; sss: = sqr(ax-ay) + sqr(bx-by); ff: = (abs(ss-sss)<1e-7);
end
end;
Полностью программу решения этой задачи (архив с программой и входным файлом) можно посмотреть в <Приложении 5>.
Задача 6. “Геном марсианина”. Сотрудники лаборатории внеземных цивилизаций обнаружили в пробах марсианского грунта фрагменты органических молекул, которые могли бы переносить генную информацию. Зашифрованные фрагменты молекул образуют отдельные слова. Известно, что фрагменты молекул могут соединяться, если на конце предыдущей и в начале последующей молекулы стоят одинаковые символы. Переворачивать фрагменты не надо. Каждый фрагмент в виде целого слова используется только один раз.
Входной файл input.txt. Первая строка
содержит N – количество фрагментов, не более 100.
Последующие N строк – зашифрованные в виде
отдельных слов фрагменты молекул (не более чем по
100 символов).
Выходной файл output.txt – максимальная длина полной молекулы.
Пример входного файла: 4; 12345; 543; 54321; 12. Выходной файл output: 13.
Решение. Для решения задачи нам потребуются некоторые типы:
type string100 = string[100]; sto = 1..100;
Основная ошибка, которую учащиеся могут
допускать при решении этой задачи – это пытаться
сразу склеивать первые подходящие строки, пусть
даже они самые длинные. Но ясно, что при такой
склейке мы можем просмотреть много коротких
склеек, которые в сумме дадут большую общую
длину, и тогда программа будет работать лишь для
некоторых частных случаев. Причём могут
склеиваться самые разные строки в самом
непредсказуемом порядке, и очень может быть, что
будут склеиваться не только какие-то две строки,
но гораздо больше. По существу, нужно провести
аккуратный перебор всех случаев.
Идея решения этой задачи следующая. Создадим
вспомогательную прямоугольную таблицу Х целых
чисел. Будем туда записывать номера строк,
которые можно склеить. Например, пусть мы
получили во входном файле следующие строки:
12345
543
54321
12
1-ю строку можно склеить со второй. Записываем в
1-ю строку таблицы Х номера слов по порядку,
которые можно склеить: 1, 2.
1-ю строку можно склеить с третьей. Записываем в
следующую строку таблицы Х номера слов по
порядку, которые можно склеить: 1, 3.
Больше первая строка ни с какой не склеивается.
Вторая строка тоже ни с какой не склеивается.
3-ю строку можно склеить с первой. Записываем в
следующую строку таблицы Х номера слов по
порядку, которые можно склеить: 3, 1.
3-ю строку можно склеить с четвёртой. Записываем в
следующую строку таблицы Х номера слов по
порядку, которые можно склеить: 3, 4.
Получили таблицу Х:
| 1 | 2 | 0 | 0 | 0 ... |
| 1 | 3 | 0 | 0 | 0 ... |
| 3 | 1 | 0 | 0 | 0 ... |
| 3 | 4 | 0 | 0 | 0 ... |
Снова просмотрим таблицу Х. Первая строка
оканчивается на 2, и больше с двойки ничто не
начинается, значит, нет ни одной молекулы,
начинающейся со слова 2, и эта молекула длиннее
сделана быть не может.
Вторая строка оканчивается на 3, а третья строка с
тройки начинается. Но склеены они быть не могут,
поскольку в 3-й строке используется тот же номер,
что и во второй, а по условию задачи нельзя
использовать одну молекулу несколько раз.
Но 2-я и 4-я строки прекрасно склеиваются. Получаем
цепочку 1 3 4, значит, можно по порядку
склеить 1-ю, 3-ю и 4-ю молекулы.
3-я строка склеивается с 1-й, получаем цепочку 3
1 2. Значит, можно по порядку склеить 3-ю, 1-ю и
2-ю молекулы. Такая склейка, кстати, и даёт самую
длинную молекулу.
Получили таблицу Х:
| 1 | 2 | 0 | 0 | 0 ... |
| 1 | 3 | 4 | 0 | 0 ... |
| 3 | 1 | 2 | 0 | 0 ... |
| 3 | 4 | 0 | 0 | 0 ... |
Будем просматривать так таблицу в цикле Х до
тех пор, пока не будет сделано ни одного нового
изменения в этой таблице. Ясно, что процесс рано
или поздно закончится.
После этого останется только просмотреть
таблицу Х, каждую строку, для каждой строки
определить длину соответствующей склеенной в
этом порядке молекулы (это сумма длин строк с
данными номерами в этой строке таблицы Х), и среди
всех этих длин найти максимальную.
Полностью программу решения этой задачи (архив с
программой и входным файлом) можно посмотреть в <Приложении 6>.
Задача 7. “Шифр Цезаря”. Известно, что символы в электронных документах кодируются разными числами при помощи кодировочных таблиц. Это позволяет кодировать сообщение, делая сдвиг по кодировочной таблице для каждого символа всего текста. Написать программу, реализующую сдвиг (ключ задаётся) только для больших латинских букв.
Входной файл input.txt. В первой строке размещается зашифрованный текст, во второй – ключ.
Выходной файл output.txt содержит расшифрованный текст.
Пример входного файла: ABZ; 2.
Выходной файл output: CDB.
Решение. Это самая простая задача из предложенных на олимпиаде. Приведённый ниже код осуществляет требуемый сдвиг. Программа понимает и отрицательные сдвиги.
for i: = i to n do
begin
c: = h[i]; k: = ord(c); inc(k,dd);{Осуществляем сдвиг}
if k>ord('Z') then dec(k,26); if k<ord('A') then inc(k,26); {если вышли за алфавит}
c: = char(k); {Изменённый символ} hh[i]: = c
end;
writeln(hh); {Готовая строка}
Полностью программу решения этой задачи (архив с программой и входным файлом) можно посмотреть в <Приложении 7>.
Задача 8. “Парижский клуб”. Дан список, в каждой строке которого указано, какая страна какой стране сколько миллиардов должна. Оптимизировать список долгов, используя взаиморасчеты.
Анализ и решение этой задачи можно посмотреть в <Приложении 8>.
Задача 9. “Археологическая находка”. Дана прямоугольная таблица из нулей и единиц – просканированный рисунок отпечатка древнего листа на угле. Найти количество сторон многоугольника. Анализ и решение этой задачи можно посмотреть в <Приложении 9>.
Задача 10. “Баскетбольная команда”. Дан список претендентов в баскетбольную команду с указанием имени, фамилии, роста и возраста. Вывести список претендентов старше 13 лет в порядке возрастания возраста. Если возраст совпадает, то выводить спортсменов в порядке убывания роста. Анализ и решение этой задачи можно посмотреть в <Приложении 10>.
Список литературы.
- Морозов В.В. Опыты детского творчества. [Текст] / В.В.Морозов. // Математика в школе. – 2000. – № 8.