Методы решения олимпиадных задач по программированию

Program generator_combination; {Генератор всех сочетаний}

uses WinCrt; {для произвольного массива}

const

n1 = 100;

type

t = array[1..n1] of integer;

var

a, x, min, max : t;

i, n, r : integer;

{----------------------------------------------------------------------------------------}

Procedure gen_comb(a, x, min, max : t; n, k : integer;

var r : integer);

var

i, j : integer;

begin

for j := 1 to k do

begin

max[j] := n - j + 1; min[j] := k - j + 1; x[j] := min[j]

end;

i := 0;

while i <= k do

begin

for j := k downto 1 do write(a[x[j]]:4); writeln;

r := r + 1; i := 1;

while (i <= k) and (x[i] = max[i]) do i := i + 1;

if i <= k then x[i] := x[i] + 1;

for j := i - 1 downto 1 do

begin

min[j] := x[j + 1] + 1; x[j] := min[j]

end

end

end;

{----------------------------------------------------------------------------------------}

begin

write('Введите число элементов массива n = '); readln(n);

writeln('Вводите элементы массива');

for i := 1 to n do

begin

write('Введите ', i, '-й элемент '); readln(a[i])

end;

writeln('Всевозможные сочетания из ', n, ' элементов');

for i := 1 to n do gen_comb(a, x, min, max, n, i, r);

writeln('Число всех сочетаний равно r = ', r)

end.

Изменения в процедуре только два: увеличивается число входных параметров - вводится заданный массив чисел a: t; при выводе элементов на экран, массив x[j] - это номера элементов, поэтому для вывода сочетаний цикл станет таким:

for j := k downto 1 do write(a[x[j]]:4); writeln;

В основной программе элементы a[i] вводятся с клавиатуры (они описаны как целые числа, но это сделано лишь из соображений "лености" работы с вещественными числами, впрочем, если возникнет необходимость их использования, то достаточно изменить описание массива a в разделе описаний основной программы).

Домашнее задание: Из данного массива целых чисел нужно выбрать всевозможные подмассивы элементов, чтобы их сумма была равна заданному целому числу z, т. е.

Урок № 13-15. Размещения с повторениями

Во многих задачах полного перебора у нас будет возникать необходимость выводить не только размещения элементов, но и размещения с повторениями. Что это такое и чем они отличаются от обычных размещений элементов?

Математику этого вопроса рассмотрим на примере тех же размещений из 5 элементов по 3. В предыдущем примере мы показывали часть размещения из 5 элементов по 3 и они были такими:

Переставляем элементы в первом сочетании, получаем:

1 3 5, 1 5 3, 5 1 3, 5 3 2, 2 3 5, 2 5 3,

переставляем элементы во втором сочетании, получаем:

1 4 5, 1 5 4, 5 1 4, 5 4 1, 4 1 5, 4 5 1

и так далее. Если теперь пойти дальше и допустить возможность повторения элементов в каждом из этих размещений, тогда можем получить такие размещения с повторениями. Для элементов 1 3 5 можно получить такие размещения с повторениями:

1 1 1, 3 3 3, 5 5 5, 1 1 3, 1 3 1, 3 1 1,

1 1 5, 1 5 1, 5 1 1, 3 3 5, 3 5 3, 5 3 3.

3 3 1, 3 1 3, 1 3 3, 5 5 1, 5 1 5, 1 5 5,

5 5 3, 5 3 5, 3 5 5, 1 3 5, 1 5 3, 5 1 3.

Как видите, таких размещений будет очень много. Ведь еще не выведены размещения из элементов: 5 3 2, 1 3 2 и другие!

Несмотря на всю громоздкость таких размещений программа будет несложной. [6]

Пример 7. Составить программу вывода на экран всех размещений с повторениями из n элементов заданного массива.

Размещения с повторениями, которые будут выдаваться этой программой несколько отличаются от теоретически изложенного только порядком расположения. Так для размещений с повторениями из 5 элементов по 3 будут выданы следующие элементы:

1 1 1, 1 1 2, 1 1 3, 1 1 4, 1 1 5,

1 2 1, 1 2 2, 1 2 3, 1 2 4, 1 2 5,

1 3 1, 1 3 2, 1 3 3, 1 3 4, 1 3 5 и т.д.

Идея составления программы, да и сама программа мало отличается от генератора сочетаний из n элементов по k.

В начале программы устанавливаются значения наибольшего и наименьшего элементов из числа заданных, а поскольку элементы - натуральные числа от 1 до n, то наименьшим является 1, а наибольшим n (в программе: max := n; min := 1;).

Первоначальное значение элементов устанавливается равным наименьшему элементу массива, в данном случае 1. Это может быть сделано с помощью следующего цикла с параметром:

for j := 1 to k do x[j] := min;

Значения этих элементов выводятся на экран и получается первое из размещений: 1 1 1.

Дальнейший процесс очевиден. Надо увеличивать последний из элементов первоначального размещения на 1 до тех пор, пока их число будет меньше заданного числа размещений k (i <= k, i <= 3) и последний элемент не станет равным наибольшему (x[i] = max), т.е. 5 и тогда получатся следующие размещения:

1 1 1, 1 1 2, 1 1 3, 1 1 4, 1 1 5,

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

while (i <= k) and (x[i] = max) do i := i + 1;

if i <= k then x[i] := x[i] + 1;

Дальнейший процесс будет заключатся в том, чтобы предпоследний элемент размещений увеличить на единицу, а последнему снова присвоить наименьшее значение, получится такое размещение: 1 2 1.

Эта замена выполняется с помощью цикла:

for j := 1 to i - 1 do x[j] := min

После чего процесс увеличения последнего элемента на 1 надо повторить и получатся такие размещения:

1 2 1, 1 2 2, 1 2 3, 1 2 4, 1 2 5,

Теперь вам стала понятна "механика" получения размещений с повторениями, но, конечно, все эти операторы надо заключить в основной цикл, начало которого такое:

while i <= k do

begin

for j := k downto 1 do write(x[j]:4); writeln;

r := r + 1; i := 1;

Полностью программа приведена ниже. Продумайте все шаги ее выполнения и составьте "протокол" ее работы для размещений с повторениями для двух элементов из 5.

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

Program generator_distribution_repeat; { генератор размещений }

uses WinCrt; { с повторениями }

const

p = 100;

type

t = array[1..p] of integer;

var

x : t;

max, min, n, k, i, j : integer;

r : longint;

begin

write('Введите общее число элементов n = '); readln(n);

write('Введите число элементов, по сколько выбираем k = ');

readln(k); writeln;

max := n; min := 1; {границы x[j]}

for j := 1 to k do x[j] := min;

while i<=k do

begin

for j := k downto 1 do write(x[j]:4); writeln;

r := r + 1; i := 1;

while (i <= k) and (x[i] = max) do i := i + 1;

if i <= k then x[i] := x[i] + 1;

for j := 1 to i - 1 do x[j] := min

end;

writeln;

writeln('Число размещений с повторениями равно r = ', r)

end.

Домашнее задание

1. Представьте число 100 в виде суммы нескольких натуральных чисел так, чтобы их произведение было наибольшим.

2. Найти две группы из 10 натуральных чисел, сумма которых равна их произведению.

Урок №16. Олимпиадные задачи. Уровень 1. Задача 1

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

На этом уровне могут встретиться всевозможные задачи. Некоторые задачи составлены так, что их может решить любой ученик. Другие, наоборот, требуют знания специальных методов. Например, таких, как динамическое программирование, или перебор с возвратом.

Начинать надо с самого простого. Самая простая задача на мой взгляд- это:

Задача 1

Условие:

Пусть заданы координаты: x1, y1; x2, y2; x3, y3 вершин треугольника и координаты x,y любой точки на плоскости.

Определить: лежит ли точка с заданными координатами x, y внутри треугольника?

Решение:

Самое простое, что можно сделать, - это нарисовать треугольник на экране, закрасить его, а потом проверить цвет точки.

Но про координаты ничего не сказано - положительные они или нет. Так что потребуется другое решение. Оно должно быть основано на аналитическом методе. Подумав еще немного, можно придумать способ, основанный на свойстве любой внутренней точки. Ведь нам надо проверить, находится ли данная точка во множестве внутренних точек треугольника, говоря научным языком.

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

А для вывода формул, необходимых для проверки, можно взять ручку и лист бумаги. Поразвивайте свои навыки выводить формулы, талант "подгонять" различные формулы, и все получиться.

Конечно, есть очень простой способ.

Рассмотрим треугольники, такие что одной из вершин является данная точка, а другими - вершины данного треугольника. Их будет три. И если площадь любого из них отлична от нуля и сумма площадей треугольников будет равна площади данного треугольника, то точка лежит в треугольнике, иначе - нет.

Осталось написать формулу площади треугольника. Конечно, вы можете и сами вывести формулу по координатам, но я хочу предложить один из ее видов:

s=abs(x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3)/2. (abs - модуль числа).

Вроде все основные возможные решения описаны. Теперь у вас появилось представление о задачах этого уровня и примерных решениях.

Эта же задача является примером для рассмотрения целого пласта информационной науки - вычислительной геометрии. Именно с помощью этого раздела сейчас в мире люди способны создавать модели всех земных процессов. Например, выход рек из берегов, оползни и другие геодезические процессы. Задача на дом.

Найдите центр и радиус окружности, описанной вокруг треугольника, координаты которого известны.[6]

Урок №17. Олимпиадные звдачи. Уровень 1. Задача 2

Теперь разберем другую олимпиадную задачу.

Задача 2. По известной легенде шах должен был дать зерна изобретателю шахмат по принципу геометрической прогрессии. На 1 клетку положить одно зерно, на 2 клетку 2 зерна, на 3-ю 4 зерна, на 4 - 8 и т.д. На каждую следующую клетку в 2 раза больше зерен пшеницы, чем на предыдущую.

Составить программу, которая определит, сколько положить шах зерен пшеницы на 32-ю клетку шахматной доски.

Многим наверняка известно такое понятие, как длинная арифметика. О ней написано много различных книг.

Суть ее заключается в том, что число заносится в массив. Например, если число состоит из 100 знаков, то на Pascal массив опишется как:

var s:array[1..100] of byte;

На C/C++ этот же массив будет иметь вид: int s[100];

И, как во всех языках, идет обращение к любой цифре числа. Но имея числа, нам надо производить над нам какие-то операции. Поэтому для работы с огромными числами приходится писать процедуры и функции.

И лучше всего сразу запомнить некоторые стандартные процедуры над массивами. Для начала надо написать процедуру сложения и умножения с обыкновенными числами.

procedure sum(d:integer);

var i:integer;

begin

i:=1;

repeat

s[i]:=s[i]+ d mod 10;

d:=int(d/10);

inc(i);

until (d>0);

end;

Процедуру умножения реализовать чуть сложнее. Все по одной причине, надо чтобы тип цифры был не byte, а на 4 бита больше, чем тип числа на которое умножают.

Так же полезно будет написать процедуры сложения двух больших чисел и, если захотите, умножение их (если вы это захотите, можно создать целую библиотеку и обязательно при умножении используйте динамические массивы).

Глубоко эту тему я подниму позже на примерах задач. Пока же только ознакомительно я рассмотрела длинную арифметику и вычислительную геометрию.

Для самостоятельного решения могу предложить следующее:

Задание на дом

Напишите процедуры умножения и сложения больших чисел с обыкновенными.

Урок №18. Олимпиадные задачи. Уровень 1. Рекурсия

Рекурсией называется вызов функции или процедуры внутри этой функции или процедуры. И только это место называется рекурсией. То есть внутри себя функция вызывает сама себя.

В основном, в процедуре происходят следующее: один из параметров (переменная или что-то другое), его назовем управляющим, меняется по какому-то алгоритму или закону, а другой параметр (управляемый)- также изменяется по какому-то закону или алгоритму. Вызов функции как самой себя внутри себя происходит до тех пор, пока первый параметр не достигнет какого-то предела или значения.

Фактически в этом и заключается рекурсия.

Но какова цель рекурсия?! И чего этим добиваются?!

В основном, многие задачи требуют, чтобы действие совершалось столько раз, сколько требует та или иная переменная. И для этого используется алгоритм рекурсии. Рекурсия поддерживает во многих языках программирования. Рекурсия встречается во многих задачах, поставленных перед программистом.

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

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

Далее выяснить, какой параметр должен быть управляющим и какой управляемым. Вслед за этим выяснить, по каким законам или алгоритмам должны изменяться параметры. Затем Вы пишите процедуру, состоящую из алгоритмов изменения параметров, проверки на выполнения рекурсии. Вызов рекурсии в случаи положительного результата проверки и конца процедуры.

В Pascal - е рекурсия поддерживается только процедурами. А на Pascal - е в основном пишут все олимпиадные задачи.

Наиболее известным примером рекурсии является вычисление факториала числа:

var factor:longint;

procedure fact(f:integer);

begin

if f>1 then begin

factor:=f*factor;

fact(f-1);

end;

end;

begin

...

factor:=1;

fact(num);

...

end.

Итак, в этой процедуре:

Ш f - управляющий параметр, т.к. на него делается проверка;

Ш factor - управляемый параметр, т.к. над ним происходят определенные действие, и нам необходимо конечное значение этого параметра;

Ш f>1 - проверка;

Ш factor:=f*factor - алгоритм изменения управляемого параметра;

Ш f-1 - алгоритм изменения управляющего параметра;

Ш num - первоначальное значение управляющего параметра;

Ш factor:=1 - первоначальное значение управляемого параметра;

Ш fact() - процедура рекурсии.

Урок №19-21. Длинная арифметика. Продолжение

Для начала сложение чисел.

const maxlen=100;

type

longnum=array[1..maxlen]of byte;

procedure sum(var s:longnum;d:integer); {прибавление к длинному числу обыкновенного.}

var i,j:integer;

begin

i:=0;

repeat

inc(i);

s[i]:=s[i]+ d mod 10; {складываем по разрядам.}

j:=i;

while int(s[j]/10)>0 begin {проверка лимита цифры и перенос на следующую цифру излишков.}

s[j+1]:=s[j+1]+int(s[j]/10);

s[j]:=s[j] mod 10;

inc(j);

if (j>=maxlen)and(s[maxlen]<0)then write('Error sum');

end;

d:=int(d/10);

until(d>0);

end;

function max(a,b:integer):integer;

begin max=int((abs(a-b)+a+b)/2); { метод определения максимального числа .}

end;

function len(a:longnum):integer; {находит длину числа(т.е. количество занятых разрядов).}

var c:integer;

begin

c:=maxlen;

while ((a[c]=0)and(c>=0)) dec(c);

len:=c;

end;

procedure sum2d(var s:longnum;a,b:longnum);

var i,j:integer;

begin

i:=0;

repeat

inc(i);

s[i]:=s[i]+a[i]+b[i];

j:=i;

while int(s[j]/10)>0 begin {проверка лимита цифры и перенос на следующую цифру излишков.}

s[j+1]:=s[j+1]+int(s[j]/10);

s[j]:=s[j] mod 10;

inc(j);

if (j>=maxlen)and(s[maxlen]<0)then write('Error sum2d');

end;

until (i<=max(len(a),len(b)));

end;

Урок №22-24. Рекурсия. Окончание

В этом уроке подведём итоги по теме рекурсия и рассмотрим окончательный пример завершающий эту тему.

После изучения остальных методов - более сложных - я поняла, что рекурсия это фундамент, который можно использовать как вводный курс в решение олимпиадных задач.

И следующую тему, которую я хотела бы разобрать, - это динамическое программирование.

Теперь рассмотрим пример.

Пускай нам необходимо вычислить минимальный номер члена прогрессии a(i): a(i+1)=3*a(i)+4, - который больше чем X, причем первый член равен A.

uses crt,dos;

var a:real;

x:comp;

procedure next(i:integer;b:comp);

var d:comp;

begin

d:=3*b+4;

if(d<=x)then next(i+1,d) else writeln(i);

end;

begin

clrscr;

write("Input x,a:");

readln(x,a);

next(1,a);

end.

Вот и вся программа. Плюс её над такой же программой, но реализованной с помощью циклов, заключает в ее компактности и скорости выполнения, и все потому что мы исключаем счетчик цикла, оператор перехода на определенную строку, а реализуем это все через ближний вызов функции. [12]

Урок №25. Задачи (часть 1)

Прочитав теорию, вы вполне можете приступать к решению задач, ведь порой этого достаточно. Но все же для полного понимания требуется разбор задач данного уровня. Во втором занятии я предложила решить задачу с описанной окружностью. Вот её условие:

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

Эта задача имеет не очень сложное решение. Итак, для начала найдем радиус окружности. Хотела бы напомнить из курса школьной математики:

S=(a*b*c)/(4*R),

где:

S - площадь треугольника;

a,b,c - стороны треугольника;

R - радиус описанной окружности.

Такими обозначениями мы будем пользоваться всегда. Выразив из этой формулы радиус и зная площадь треугольника из формулы, которую я давала в занятии 2 (s=abs(x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3)/2. (abs - модуль числа)), можно спокойно найти радиус.

Теперь надо найти центр. Как это возможно сделать? Сейчас введем немного теории.

Итак, введем понятие прямой. Точнее будем рассматривать свойства и особенности прямой в координатной плоскости. Для начала введем уравнение прямой на координатной плоскости: a*x+b*y+c=0.

Именно такое уравнение имеет прямая. А привычный многим вид y=k*x+b применим лишь в алгебре, но никак не в аналитической геометрии.

Допустим нам известны две точки прямой - (x1,y1),(x2,y2).

Тогда:

a*x1+b*y1+c=0

a*x2+b*y2+c=0

a(x1-x2)+b(y1-y2)=0

Т.к. a или b могут быть нулем, если x1-x2 не равно 0, то b=1 a=(y1-y2)/(x1-x2), иначе a=1 b=0. "c" вычисляется из 1 формулы.

Теперь введем структуру, описывающую прямую:

line=record

a,b,c:real;

end;

typedef struct{

float a,b,c;

}line;

Надо разобрать пересечение 2 прямых. Вот элемент программы:

l1,l2:line;

x,y:real;

...

if (l2.b*l1.a-l1.b*l2.a)<>0 then begin

x:=(l1.b*l2.c-l2.b*l1.c)/(l2.b*l1.a-l1.b*l2.a);

y:=(l1.a*l2.c-l2.a*l1.c)/(l2.b*l1.a-l1.b*l2.a);

end;

line l1,l2;

float x,y;

if ((l2.b*l1.a-l1.b*l2.a)!=0){

x=(l1.b*l2.c-l2.b*l1.c)/(l2.b*l1.a-l1.b*l2.a);

y=(l1.a*l2.c-l2.a*l1.c)/(l2.b*l1.a-l1.b*l2.a); };

Условие перпендикулярности прямых:

l1,l2:line;

if ((l2.b*l1.a+l1.b*l2.a)=0)) then ... end;

line l1,l2;

if ((l2.b*l1.a+l1.b*l2.a)==0)){ ...

Решение данной задачи с поиском центра можно получить с помощью данных методов. Помните, как в школе вы получали центр описанной окружности с помощью циркуля и линейки.

Урок № 26-32. Начальные сведения о работе с файлами. Файловый тип

Под файлом понимается либо именованная область внешней памяти ПК (жесткого диска, гибкой дискеты, электронного "виртуального" диска), либо логическое устройство - потенциальный источник или приемник информации.

По содержанию, под файлом понимают любой набор элементов одного и того же типа. Число элементов, называемое длиной файла, не фиксировано. В этом основное отличие файла от массива. Файл, не содержащий ни одного элемента, называется пустым: его длина равна нулю.

На этом примере рассмотрим, как происходит работа с файлом на диске.

Пример 1. Поставим задачей, записать в один файл произвольный массив чисел, затем прочесть их из файла, отсортировать по не убыванию методом пузырьковой сортировки и записать отсортированный массив в новый файл.

1. Запись информации в файл

1. Нам уже известно, что файл - это именованная область на диске для записи информации. Значит, этой области надо дать имя, иначе говоря "открыть файл" на диске, Для этого надо указать: имя диска, имя каталога и подкаталога, в который записывается файл и, наконец, имя самого файла. (Сразу надо заметить, что не всегда обязательно нужно указывать путь к файлу, т. е. диск, каталог, подкаталог. Другие случаи разберем позже).

Итак, указываем путь к файлу и его имя. Сразу возникает вопрос, в каком разделе программы это можно сделать?

Один из способов - записать в разделе констант, т. е. некоторой константе определить имя физического файла, а затем работать уже с этой константой, что может упростить запись, особенно в тех случаях, когда путь к файлу "долгий" - состоит из нескольких подкаталогов.

Это можно сделать так:

const

name = 'd:\Bp\prakt\p23\array1.dat';

name - константа, в которой записывается путь к файлу и его имя. Далее, в апострофах, как символьная переменная, записывается:

'd:\Bp\Prakt\p23\array1.dat'

d - имя диска, Bp - имя каталога, Prakt - имя подкаталога, P23 - еще один подкаталог, array1.dat - имя файла и его расширение, которое должно удовлетворять известным требованиям (имя - не должно превышать 8 символов, расширение - трех символов).

В файл array1.dat будут записываться элементы массива до сортировки.

Теперь надо, таким же образом, указать второй файл, в который будут записываться отсортированные элементы массива, назовем его array1.int и запишем в другую константу name1.

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

const

name = 'd:\Bp\prakt\p23\array1.dat';

name1 = 'd:\Bp\Prakt\p23\array1.int';

n = 100;

Здесь еще добавилось n - возможное число элементов массива.

2. Понятно, что константой, определяющей имя файла еще нельзя пользоваться в программе. Константа - это постоянная, не подверженная изменениям в программе, а ведь нам надо записывать информацию в файл, считывать ее, да и размер файла не всегда может быть заведомо установлен.

Значит, необходимо завести переменные для файлов. Обозначим эти переменные f и f1. Но поскольку это переменные, необходимо указать их тип.

Для переменных файлового типа указывается тип: file - что и означает файловый тип, а затем указывается тип данных, которые будут записаны в этот файл. В данном случае - это целые числа, значит, запись будет такой: file of integer.

Нам уже известно, как можно описать переменные. Вот эти два способа:

type var

v = file of integer; f, f1 : file of integer;

var

f, f1 : v;

В нашем примере будет использован первый способ. Кроме того, опишем массив чисел и другие переменные. И тогда полностью раздел описаний станет таким:

const

name = 'd:\Bp\prakt\p23\array1.dat';

name1 = 'd:\Bp\Prakt\p23\array1.int';

n = 100;

type

v = file of integer;

t = array[1..n] of integer;

var

f, f1 : v;

a : t;

i : integer;

3. Для создания массива чисел мы, как и раньше, воспользуемся процедурой, но в из нее нам надо получить файл с записью целых чисел массива, значит в качестве выходного параметра добавляется и файловая переменная f.

Начало процедуры станет:

Procedure create(n : integer; var a : t; var f : v);

Но чтобы работать в программе или процедуре с файловой переменной, надо связать логическое имя файла f с физическим, которое записано в константе name, т. е. сделать доступной переменную f, как сам файл.

Для этого используется стандартная (встроенная) процедура assign (назначит).

Она запишется так: assign(f, name); { доступ к файлу f }

В переводе на простой язык, это значит, что файлу name назначается в программе имя f и в дальнейшем к переменной f можно обращаться как самому файлу, т. е. посредством f осуществляется доступ к файлу.

Процедура уже напишется дальше:

Procedure create(n : integer; var a : t; var f : v);

var

i : integer;

begin

assign(f, name); { доступ к файлу f }

4. Теперь наступило время приступить к работе с файлом f. Но, прежде, надо установить, что делать в файле: записывать в него информацию, читать или что-то другое. Нам следует записать в него информацию. Для этого его надо открыть для записи.

Открывается файл для записи стандартной процедурой rewrite(f) (переписать). При этом уничтожается вся информация, которая была в файле f и запись новой информации начнется с начала файла.

Procedure create(n : integer; var a : t; var f : v);

var

i : integer;

begin

assign(f, name); { доступ к файлу f }

{$i-}

rewrite(f); { открытие его для записи }

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

В процедуре записаны два новых для вас знака {$i-} и {$i+}. Что они означают?

С помощью указания (директиве) компилятору {$i-} отключается автоматический контроль ошибок ввода-вывода. Если этого не сделать, то отсутствие файла приведет к аварийному завершению программы.

{$i-} { Отключить контроль ошибок ввода-вывода }

С помощью директивы {$i+}, напротив, включается контроль за ошибками ввода и вывода.

{$i+} { Включить контроль ошибок ввода-вывода }

Вначале, до открытия файла для записи, контроль за ошибками был отключен, после включения контроля за ошибками ввода и вывода, можно установить условный оператор, который бы, в случае ошибки, выдавал соответствующую информацию.

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

if IORESULT <> 0 then ..... { Файл не существует }

else .... { Файл существует }

Встроенная функция IORESULT типа WORD в случае ошибки получает ненулевое значение, в частности, если файл, к которому обращаются, вообще не существует.

5. Препятствий для записи элементов массива в файл f нет. Сделаем это с помощью известной встроенной процедуры write(f, a[i]).

Procedure create(n : integer; var a : t; var f : v);

var

i : integer;

begin

assign(f, name); { доступ к файлу f }

{$i-}

rewrite(f); { открытие его для записи }

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

randomize;

for i := 1 to n do

begin

a[i] := random(201) - 100;

write(f, a[i]) {запись элементов массива в файл f}

end;

6. После записи информации в файл, его надо закрыть. Это делается с помощью встроенной, стандартной процедуры close(f).

Полностью процедура создания массива чисел и его записи в файл со строгим контролем за ошибками ввода-вывода получится такой:

Procedure create(n : integer; var a : t; var f : v);

var

i : integer;

begin

assign(f, name); { Доступ к файлу f }

{$i-} { Отключить контроль ошибок ввода-вывода }

rewrite(f); { Открытие его для записи }

{$i+} { Включить контроль ошибок ввода-вывода }

if ioresult <> 0 then writeln('Такой файл не существует');

randomize;

for i := 1 to n do

begin

a[i] := random(201) - 100;

write(f, a[i]) { Запись элементов массива в файл f }

end;

close(f); {Закрытие файла f}

end;

2. Чтение информации из файла

Порядок чтения информации из файла подобен порядку записи.

1. Открыть файл для чтения стандартной процедурой reset(f) (вновь установить), В результате специальная переменная-указатель, связанная с этим файлом, будет указывать на начало файла, т.е. на компонент с порядковым номером 0.

2. Выполнить считывание информации из файла с помощью стандартной процедуры read(f, a) - информация считывается в переменную a. В нашей процедуре, в качестве переменных, в которые будет считываться информация, являются элементы массива: for i := 1 to n do read(f, a[i]); { Чтение из файла f }

3. Закрыть файл после чтения из него информации процедурой close(f).

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

const

name1 = 'd:\Bp\Prakt\p23\array1.int';

и далее

type

v = file of integer;

var

f1 : v;

Теперь, в процедуре сортировки

Procedure bubble(n : integer; var f1 : v);

Следует установить доступ к файлу

assign(f1, name1); {доступ к файлу f1}

Открыть его для записи

rewrite(f1); {открытие файла f1 для записи}

Отсортировать массив

for i := 2 to n do

for j := n downto i do

if a[j] < a[j - 1] then

begin

p := a[j];

a[j] := a[j - 1];

a[j - 1] := p

end;

Записать в файл отсортированный массив

for i := 1 to n do write(f1, a[i]); {запись отсортированного

массива в файл f1 },

Закрыть файл

close(f1)

В основной программе:

1. Снова установить доступ к файлу f1

assign(f1, name1); { доступ к файлу f1 }

2. Вызвать процедуру сортировки

bubble(n, f1); { вызов процедуры сортировки }

3. Открыть файл для чтения (попутно перестраховаться от ошибок)

{$i-}

reset(f1); { Открытие файла f1 для чтения }

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

4. Прочитать информацию из файла и вывести ее на экран

writeln('Отсортированный по не убыванию массив');

for i := 1 to n do

begin

read(f1, a[i]); { Чтение элементов массива из файла f1 }

write(a[i], ' ') { Вывод их на экран }

end;

writeln;

5. Закрыть файл

close(f1) {Закрытие файла f1}

Полностью программа

Program Problem1; { Обработка массивов с помощью файлов }

uses WinCrt; { пузырьковая сортировка }

const

name = 'd:\Bp\prakt\p23\array1.dat';

name1 = 'd:\Bp\Prakt\p23\array1.int';

n = 100;

type

v = file of integer;

t = array[1..n] of integer;

var

f, f1 : v;

a : t;

i : integer;

{----------------------------------------------------------------------------------------}

{ Открытие файла f, соответствующего на диске файлу arra1.dat

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

Procedure create(n : integer; var a : t; var f : v);

var

i : integer;

begin

assign(f, name); { доступ к файлу f }

{$i-}

rewrite(f); { открытие его для записи }

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

randomize;

for i := 1 to n do

begin

a[i] := random(201) - 100;

write(f, a[i]) {запись элементов массива в файл f}

end;

close(f); {закрытие файла f}

end;

{---------------------------------------------------------------------------------------}

{Процедура, читающая элементы из файла f, сортирующая

элементы методом "пузыря" и записывающая отсортированный

массив в новый файл array1.int}

Procedure bubble(n : integer; var f1 : v);

var

i, j, p : integer;

begin

assign(f, name); {доступ к файлу f}

assign(f1, name1); {доступ к файлу f1}

create(n, a, f);

{$i-}

reset(f); {открытие файла f для чтения}

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

rewrite(f1); {открытие файла f1 для записи}

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

for i := 1 to n do read(f, a[i]); {чтение из файла f}

for i := 2 to n do

for j := n downto i do

if a[j] < a[j - 1] then

begin

p := a[j];

a[j] := a[j - 1];

a[j - 1] := p

end;

for i := 1 to n do write(f1, a[i]); {запись отсортированного

массива в файл f1 }

close(f); close(f1) {з закрытие файла f, закрытие файла f1 }

end;

{----------------------------------------------------------------------------------------}

{Основная программа, вызывающая отсортированные элементы

из файла f1 и выводящая их на экран}

begin

assign(f1, name1); { доступ к файлу f1 }

bubble(n, f1); { вызов процедуры сортировки }

{$i-}

reset(f1); { Открытие файла f1 для чтения }

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

writeln('Отсортированный по не убыванию массив');

for i := 1 to n do

begin

read(f1, a[i]); { Чтение элементов массива из файла f1 }

write(a[i], ' ') { Вывод их на экран }

end;

writeln;

close(f1) {Закрытие файла f1}

end.

Program Problem1a; { Обработка массивов с помощью файлов }

uses WinCrt; { пузырьковая сортировка }

const

name = 'd:\Bp\prakt\p23\array1.dat';

name1 = 'd:\Bp\Prakt\p23\array1.int';

n = 100;

type

v = file of integer;

t = array[1..n] of integer;

var

f, f1 : v;

a : t;

i : integer;

{---------------------------------------------------------------------------------------}

{Процедура, читающая элементы из файла f, сортирующая

элементы методом "пузыря" и записывающая отсортированный

массив в новый файл array1.int}

Procedure bubble(n : integer; var f1 : v);

var

i, j, p : integer;

begin

assign(f, name); {доступ к файлу f}

assign(f1, name1); {доступ к файлу f1}

create(n, a, f);

{$i-}

reset(f); {открытие файла f для чтения}

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

rewrite(f1); {открытие файла f1 для записи}

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

for i := 1 to n do read(f, a[i]); {чтение из файла f}

for i := 2 to n do

for j := n downto i do

if a[j] < a[j - 1] then

begin

p := a[j];

a[j] := a[j - 1];

a[j - 1] := p

end;

for i := 1 to n do write(f1, a[i]); {запись отсортированного

массива в файл f1 }

close(f); close(f1) {з закрытие файла f, закрытие файла f1 }

end;

{Основная программа, вызывающая отсортированные элементы

begin

assign(f1, name1); { доступ к файлу f1 }

bubble(n, f1); { вызов процедуры сортировки }

{$i-}

reset(f1); { Открытие файла f1 для чтения }

{$i+}

if ioresult <> 0 then writeln('Такой файл не существует');

writeln('Отсортированный по не убыванию массив');

for i := 1 to n do

begin

read(f1, a[i]); { Чтение элементов массива из файла f1 }

write(a[i], ' ') { Вывод их на экран }

end;

writeln;

close(f1) {Закрытие файла f1}

end.

Часть II. Разбор задач Всеукраинских Интернет олимпиад NetOI

BISHOP

Задача. На шахматной доске размерами М*N клеток стоит слон (фигура, которая ходит по диагонали). Выяснить, может ли слон дойти до поля (x,y). Если может, то за какое наименьшее количество ходов; если количество ходов больше 1, то указать, через какие промежуточные клетки должен пройти слон (если таких маршрутов несколько, указать любой из них). Поля шахматной доски кодируются парой натуральных чисел 1..М,1..N, где первое число - номер горизонтали, а второе - номер вертикали (1?М,N?1000).

Технические условия. Вы вводите с клавиатуры через пробел числа М, N, а далее координаты начального и конечного полей желаемого маршрута слона. Вы выводите на экран число К (минимальное количество ходов), а далее в К-1 строках по 2 числа через пробел - координаты посещенных полей. Если решений нет, вывести 0.

Пример:

Ввод

10 10 1 1 1 7

Вывод

2

4 4

Описание алгоритма. Задача довольно тривиальна: если конечная и начальная клетки имеют разный цвет, или поле имеет единичную длину/ширину - ответ 0. В противном случае ответом будет более короткий маршрут из двух, имеющих вид зигзагов максимального размаха, касающихся краев доски.

Код программы на языке Паскаль:

{ NetOI-2003: Tour1: BISHOP}

program bishop;

var

M, N, x1, y1, x2, y2: integer;

x, y, dy, dx: integer;

K: array [1..2] of integer;

flip: array [1..2,1..1000,1..2] of integer;

swapper: array [1..2] of integer;

procedure proceed( i: integer);

begin

x := x1; y := y1;

while (abs(x2-x)<>abs(y2-y)) do

if (((dy=1) and (y<N)) or ((dy=-1) and (y>1))) then

begin

x := x + dx;

y := y + dy;

end

else

begin

K[i] := K[i] + 1;

flip[i,K[i],1] := x;

flip[i,K[i],2] := y;

dy := -dy;

end;

K[i] := K[i] + 1;

flip[i,K[i],1] := x;

flip[i,K[i],2] := y;

end;

procedure out( i: integer);

var j: integer;

begin

writeln(K[i]+1);

for j:=1 to K[i] do

writeln(flip[i,j,swapper[1]],' ',flip[i,j,swapper[2]]);

end;

procedure swp2int( var a, b: integer);

var

t: integer;

begin

t := a; a := b; b := t;

end;

begin

read(M,N,x1,y1,x2,y2);

if ((M=1) or (N=1) or ((x1+y1) and 1<>(x2+y2) and 1)) then

writeln(0)

else

if (abs(x2-x1)=abs(y2-y1)) then

writeln(1)

else

begin

if (abs(x2-x1)<abs(y2-y1)) then

begin

swp2int(x1,y1); swp2int(x2,y2); swp2int(M,N);

swapper[1] := 2; swapper[2] := 1;

end

else

begin

swapper[1] := 1; swapper[2] := 2;

end;

if (x2>x1) then dx := 1 else dx := -1;

K[1] := 0;

if (y1<N) then

begin

dy := 1;

proceed(1);

end;

K[2] := 0;

if (y1>1) then

begin

dy := -1;

proceed(2);

end;

if (K[1]=0) then

out(2)

else

if (K[2]=0) then

out(1)

else

if (K[1]<K[2]) then

out(1)

else

out(2);

end;

end.

ROBOTS

Задача. Колония роботов живет по таким законам:

1. За один год M роботов собирают А новых роботов, а N роботов собирают B новых роботов.

2. Роботы всегда пытаются собрать как можно больше новых роботов.

На момент основания колонии было К роботов. Сколько будет роботов через Т лет? (Все входные величины не превосходят 100, результат не превышает 2000000000).

Технические условия. Вы вводите с клавиатуры числа М, А, N, B, K, T через пробел. Вы выводите на экран единственное искомое число.

Пример:

Ввод

3 5 5 9 15 1

Вывод

42

Комментарий. В условии не указано, могут ли входные величины быть равными нулю. Результат обсуждений в форуме: "ни одно из чисел N M не может принимать значение 0". Отсюда вывод: A,B>0. Однако, на всякий случай, в программу была встроена соответствующая проверка.

Математичекая формулировка. Очевидно, решение задачи для T лет можно получить последовательным решением T задач для одного года с изменяющимся (неубывающим) K. Поэтому сформулируем задачу для T=1. Пусть x - количество групп по N роботов, а y - групп по M роботов. Необходимо найти максимум функции F(x,y)=Bx+Ay при ограничении Nx+Ay?K.

Описание алгоритма. Так как x,y>=0, B,A>0, то при каждом конкретном x необходимо выбирать наибольшее допустимое y. Как следует из ограничения, такое значение есть: y=[(K-Nx)/M]. Тогда задача принимает вид: максимизировать функцию F(x)=Bx+A[(K-Nx)/M] при условии 0?x?[K/N].

Пусть r=[x/M], p=(x mod M) ? x=Mr+p. Тогда

F(x)=F(Mr+p)=B(Mr+p)+A[(K-N(Mr+p))/M]=Bx+A[(K-Nq)/M-Nr]=B(Mr+p)+[(K-Nq)/M]-ANr=(BM-AN)r+Bq+[(K-Nq)/M]=(BM-AN)r+F(p).

Последнее выражение есть сумма двух функций от разных аргументов, которые не связаны между собой. Т.к. ищется максимум, то

BM-AN>0 ? r_opt=[x_max/M]=[[K/N]/M]

и

BM-AN?0 ? r_opt=[x_min/M]=[0/M]=0.

p принимает значения 0..M-1 при [K/N]?M-1 и 0..[K/N] при [K/N]<M-1. Для перебора всех возможных значений p в худшем случае потребуется O(M) операций. Для решения же задачи с количеством лет T потребуется в худшем случае O(T*M) операций. Т.к. по условию M,T?100, то такое количество операций является допустимым и решение задачи находим перебором значений p.

Комментарий. Т.к. скорость работы программы явно зависит от M, и результат не меняется при замене M ? N, A ? B, то в качестве M нужно выбирать меньшее из M, N.

Комментарий. Если Ваша программа основана на анализе производительностей групп роботов, предлагаю прогнать ее на таком примере: 4 5 10 11 11 1 (правильный ответ 22).

Код программы на языке Паскаль:

{ NetOI-2003: Tour1: ROBOTS}

program robots;

var

M, A, N, B, K, T: longint;

p, max, tmp, ml, i, bd, KdivN: longint;

procedure readncorr;

begin

read(M,A,N,B,K,T);

if (M>N) then

begin

tmp := M; M := N; N := tmp;

tmp := A; A := B; B := tmp;

end;

end;

function F( x: longint): longint;

begin

F := B*x + A*((K-N*x) div M);

end;

procedure proceed;

begin

if ((N>0) and (A+B>0)) then

begin

if (M=0) {=> & A=0} then

begin

for i:=1 to T do

K := K + B*(K div N);

end

else

begin

ml := B*M-A*N;

for i:=1 to T do

begin

KdivN := K div N;

max := F(0); if (ml>0) then max := max + ml*(KdivN div M);

if (KdivN<M-1) then bd := KdivN else bd := M-1;

for p:=1 to bd do

begin

tmp := F(p); if (ml>0) then tmp := tmp + ml*((KdivN-p) div M);

if (tmp>max) then

max := tmp;

end;

K := K + max;

end;

end;

end;

writeln(K);

end;

begin

readncorr;

proceed;

end.

CARS

Задача. Две прямые дороги пересекаются. Каждая из дорог является координатной осью с началом координат в точке их пересечения. Два авто двигаются по дорогам со скоростями V1 и V2 (м/с). Угол между направлениями движения А градусов. Если скорость положительна, то ее направление совпадает с направлением соответствующей оси, если отрицательна, то авто едет в противоположном направлении. В начальный момент времени авто имели координаты S1 и S2 (м). На каком минимальном расстоянии один от другого могут оказаться авто во время своего движения? Все величины не выходят за пределы типа real языка Pascal.

Технические условия. Вы вводите с клавиатуры числа A, V1, V2, S1, S2 через пробел. Вы выводите на экран единственное искомое число.

Пример:

Ввод

90.0 -1.0 -2.0 3.0 4.0

Вывод

8.9442719100Е-01

Комментарий. В условии не указано, могут ли скорости V1, V2 равняться нулю, и как понимать условие задачи в таком случае. Результат обсуждений в форуме: "если какая-либо скорость равна нулю, направление движения считать произвольным". Под словом "произвольным" жюри имело в виду произвольное направление вдоль соответствующей прямой.

Описание алгоритма. Пусть ни одна скорость не равна нулю. Определим косинус cosA угла между прямыми (напоминаю, что A - угол между направлениями движения). Если знак скоростей V1, V2 совпадает, значит cosA = cos(A). В противном случае cosA = cos(p - A) = -cos(A). Как обычно, символом t будем обозначать время. По теореме косинусов квадрат расстояния между авто:

S(t) = (S1+t*V1)² + (S2+t*V2)² - 2cosA*(S1+tV1)(S2+tV2)

Функция S(t) - квадратичная по t с положительным коэффициентом при квадрате, поэтому единственный экстремум - минимум. Найдем нули производной:

S'(t) = 2(S1+t*V1)*V1+2(S2+t*V2)*V2-2cosA*(V1*S2+S1*V2+2(V1+V2)) = 0 ?

? t_opt = (cosA(V1*S2+S1*V2)-(S1*V1+S2*V2))/(V1²+V2²-2cosA*V1*V2)

Знаменатель дроби может обратиться в ноль при cosA = 0, V1 = ±V2. Рассмотрим случай V1 = V2:

t_opt = (cosA*V1(S1+S2)-V1*(S1+S2))/(2V1²*(1-cosA)) = -(S1+S2)/(2*V1)

Аналогично при V1 = -V2

t_opt = (cosA*V1(S2-S1)-V1*(S1-S2))/(2V1²*(1+cosA)) = (S2-S1)/(2*V1)

Итак, будем считать, что t_opt уже вычислено. Тогда, если t_opt < 0, машины для минимального сближения должны двигаться в обратном направлении. Это означает, что они находятся на минимальном возможном расстоянии друг от друга в момент t = 0. Т.о. t_opt < 0 ? t_opt = 0. Далее требуемое расстояние находим как sqrt(S(t_opt)).

Пусть теперь одна из скоростей равна нулю. Не умаляя общности будет считать, что V2 = 0. Тогда cosA = ±cos(A) и пользуясь предыдущими формулами, находим:

t_opt = (±cos(A)*S2-S1)/V1 ? t_opt1 = (cos(A)*S2-S1)/V1, t_opt2 = -(cos(A)*S2+S1)/V1

Как и ранее, t_opti < 0 ? t_opti = 0 и требуемое расстояние находим как sqrt(min(S(t(_opti))), i=1,2).

Если же V1 = V2 = 0, тогда ответ очевиден:

sqrt(S1*S1 + S2*S2 - 2*|cos(A)*S1*S2|)

Код программы на языке Паскаль:

{ NetOI-2003: Tour1: CARS}

program cars;

var

A, cosA, V1, V2, S1, S2, t, x, y: real;

L, L1, L2, t1, t2: real;

procedure readncorr;

begin

read(A,V1,V2,S1,S2);

while (A>360) do A := A - 360;

if (A>180) then A := A - 180;

if (V1=0) then

begin

V1 := V2; V2 := 0;

t := S1; S1 := S2; S2 := t;

end;

end;

procedure proceed;

begin

cosA := cos(A*Pi/180);

if (V1=0) {=> & V2=0} then

begin

L := S1*S1 + S2*S2;

if (A<>90) then

L := L - 2*abs(cosA*S1*S2);

end

else

if (V2=0) then

begin

t1 := (cosA*S2 - S1)/V1; if (t1<0) then t1 := 0;

t2 := -(cosA*S2 + S1)/V1; if (t2<0) then t2 := 0;

y := S2;

x := S1+t1*V1; L1 := x*x+y*y-2*cosA*x*y;

x := S1+t2*V1; L2 := x*x+y*y+2*cosA*x*y;

if (L1<L2) then

L := L1

else

L := L2;

end

else

begin

if (V1*V2<0) then cosA := -cosA;

if (V1=V2) then

t := -(S1+S2)/(2*V1)

else

if (V1=-V2) then

t := (S2-S1)/(2*V1)

else

t := (cosA*(V1*S2+V2*S1)-(S1*V1+S2*V2))/(V1*V1+V2*V2-2*cosA*V1*V2);

if (t<0) then t := 0;

x := S1+t*V1; y := S2+t*V2;

L := x*x+y*y-2*x*y*cosA;

end;

writeln(sqrt(L));

end;

begin

readncorr;

proceed;

end.

LINE

Задача. Дано прямоугольную декартову систему координат. N прямоугольников размещены так, что одна из их сторон лежит на оси x. Каждый прямоугольник задан координатами начала и конца стороны, лежащей на оси х и высотой у (у>0). Найти длину линии, очерчивающей площадь, занятую прямоугольниками. Часть линии, совпадающую з осью х, не учитывать.

Технические условия. Вы вводите с клавиатуры количество прямоугольников N (от 1 до 10000), а затем N раз по три целых числа через пробел - координаты основания и высоту прямоугольника (все числа неотрицательны и не превосходят 10000). Вы выводите на экран единственное искомое число.

Пример:

Ввод

3

1 2 3

5 9 4

6 8 7

Вывод

25

Описание алгоритма. Эта задача - самая простая. Представим себе, что прямоугольники формируют рельеф местности вдось оси x. Рельеф можно представить в виде массива достаточной длины (10000 хватит), если его элементы задают высоту рельефа на соответствующих промежутках длины 1. Тогда (сначала обнулив массив) после ввода параметров очередного прямоугольника нужно "поднимать" более низкие участки "рельефа" до уровня высоты прямоугольника. После окончания ввода остается подсчитать длину линии рельефа и вывести ее.

Код программы на языке Паскаль:

{ NetOI-2003: Tour1: LINE}

program line;

var

N, i, j, a, b, am, bm, h: integer;

L: longint;

rct: array [0..10002] of integer;

begin

fillchar(rct,sizeof(word)*10003,0);

read(N); bm := 0; am := 10000;

for i:=1 to N do

begin

read(a,b,h);

if (b<a) then

begin

j := b; b := a; a := j;

end;

if (b>bm) then bm := b;

if (a<am) then am := a;

for j:=a+1 to b do

if (rct[j]<h) then

rct[j] := h;

end;

L := 0;

for i:=am to bm+1 do

begin

if (rct[i]>0) then

L := L + 1;

if (rct[i]<>rct[i+1]) then

L := L + abs(rct[i+1]-rct[i]);

end;

writeln(L);

end.

SWEETS

Задача. Маленький мальчик попал в сказочную страну и увидел там дорогу, вдоль которой разложены мешки с конфетами. На каждом мешке написано количество конфет. Мальчик может взять в каждую руку два мешка, лежащие рядом. Какое наибольшее количество конфет он может взять?

Технические условия. Вы вводите с клавиатуры количество мешков N (4?N?10000), а затем N чисел через пробел - количество конфет в каждом мешке (все числа неотрицательны и не превосходят 1000000). Вы выводите на экран единственное искомое число.

Пример:

Ввод

8 3 8 5 2 1 7 8 5

Вывод

28

Математичекая формулировка. В массиве A[1]..A[N] неотрицательных целых чисел (не превышающих 1000000) найти такие два элемента A[j1], A[j2] (j1+1<j2), что сумма A[j1]+A[j1+1]+A[j2]+A[j2+1] принимает наибольшее возможное значение.

Описание алгоритма. Пусть для массива A[1]..A[i] (i<N) задача решена: известны удовлетворяющие условию оптимальности индексы j1, j2 и, следовательно, S_i = A[j1]+A[j1+1]+A[j2]+A[j2+1] - решение задачи при N=i. Кроме того, пусть для массива A[1]..A[i-1] известен индекс jmax такой, что A[jmax]+A[jmax+1] - маскимальная сумма соседних элементов. При добавлении к массиву A[1]..A[i] элемента A[i+1] возможны две и только две ситуации:

1. A[jmax]+A[jmax+1]+A[i]+A[i+1]>S_i ? S_i+1=A[jmax]+A[jmax+1]+A[i]+A[i+1] (j1'=jmax, j2'=i)

2. A[jmax]+A[jmax+1]+A[i]+A[i+1]?S_i ? S_i+1 = S_i (j1'=j1, j2'=j2)

Если i+1<N, тогда для последующих расчетов нужно вычислить новое значение jmax':

A[i-1]+A[i]>A[jmax]+A[jmax+1] ? jmax'=i-1

A[i-1]+A[i]?A[jmax]+A[jmax+1] ? jmax'=jmax

Если же i+1=N, расчеты прекращаются.

Начальные условия:

j1=1, j2=3, jmax=((A[1]+A[2]?A[2]+A[3])?1:2).

Комментарий. Решить задачу можно многими способами. Предложенный отличается от прочих в следующем: решение находится в один проход по массиву, последовательный характер вычислений позволяет совместить ввод исходных данных с вычислениями (в приведенной ниже программе это не сделано).

Код программы на языке Паскаль:

{ NetOI-2003: Tour1: SWEETS}

program sweets;

var

N, i, jmax, j1, j2: word;

a: array [1..10000] of longint;

max, s, sum2, sum2max: longint;

procedure inp;

begin

read(N);

for i:=1 to N do read(a[i]);

end;

procedure proceed;

begin

...