Интернет-олимпиада уч. года, 1-й этап, информатика

Интернет-олимпиада уч. года

1-й этап

Информатика

Задача A. Кузнечик

(Время - 1 сек., память - 16 Мб, баллы - 100)

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

Входные данные

Входной файл input. txt содержит в первой строке одно число n (1 ≤ n ≤ 100000) – количество ящиков, во второй строке содержатся n чисел – количество монет в каждом ящике (от 1 до 10).

Выходные данные

В единственную строку выходного файла output. txt нужно вывести одно число – собранное кузнечиком максимальное количество монет.

Пример

№	input. txt	output. txt
1	10 10 7	35

Разбор

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

Программа на Паскале

var

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

i, n : longint;

Begin

assign(input,'input. txt'); reset(input);

assign(output,'output. txt'); rewrite(output);

readln(n);

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

if n=1 then write(a[1]) else begin

if n>2 then a[3]:=a[1]+a[3];

for i:=4 to n do

if a[i-2]>a[i-3] then a[i]:=a[i-2]+a[i]

else a[i]:=a[i-3]+a[i];

if a[n-1]>a[n] then write(a[n-1])

else write(a[n])

end;

close(output)

End.

Задача B. Максимальная сумма

(Время - 1 сек., память - 16 Мб, баллы - 100)

Отрезок последовательности целых чисел образуют числа, идущие в ней подряд.

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

Входные данные

В единственной строке входного файла input. txt записана последовательность чисел, не равных нулю. Признак окончания – 0, не входящий в последовательность. Гарантировано, что последовательность не пуста и что сумму и количество чисел любого отрезка можно представить в типе longint.

Выходные данные

В единственную строку выходного файла output. txt нужно вывести номера первого и последнего числа и сумму чисел отрезка.

Примеры

№	input. txt	output. txt
1	-2 -1 0	2 2 -1
2		1 2 3

Разбор

Задача из замечательной книги и «Алгоритмы и программы. Решение олимпиадных задач». Подробный разбор этой задачи вы найдёте на страницах 49-50. Настоятельно рекомендуем скачать книгу и внимательно её хотя бы прочитать, а ещё лучше самостоятельно прорешать рассмотренные в ней задачи.

Программа на Паскале

var

a, t, MaxS, begMaxS, finMaxS, TempS, begTempS, finTempS : longint;

begin

assign(input,'input. txt'); reset(input);

assign(output,'output. txt'); rewrite(output);

read(a); t:=1;

MaxS:=a; begMaxS:=t; finMaxS:=t;

while a<0 do

begin

if a>MaxS then begin MaxS:=a; begMaxS:=t; finMaxS:=t end;

read(a);

if a=0 then begin write(begMaxS,' ',finMaxS,' ',MaxS); exit end;

t:=t+1

end;

TempS:=a; begTempS:=t; finTempS:=t;

MaxS:=a; begMaxS:=t; finMaxS:=t;

while true do

begin

read(a);

if a=0 then

begin write(begMaxS,' ',finMaxS,' ',MaxS); exit end

else t:=t+1;

if TempS>=0 then

begin

TempS:=TempS+a;

if a>0 then

begin

finTempS:=t;

if TempS>MaxS then

begin

MaxS:=TempS; begMaxS:=begTempS; finMaxS:=finTempS

end

end

end

else

if a>0 then

begin

TempS:=a; begTempS:=t; finTemps:=t;

if TempS>MaxS then

begin

MaxS:=TempS; begMaxS:=begTempS; finMaxS:=finTempS

end

end

end

end.

Задача C. Максимальное входящее число

(Время - 1 сек., память - 16 Мб, баллы - 100)

Для натуральных чисел X и Y будем говорить, что X входит в Y, ес­ли дво­ичную запись числа X можно получить из двоичной записи Y вычерки­ванием нуле­вого, единичного или большего количества цифр. Например, X=10=10102 входит в Y=76=.

Требуется написать программу, которая для двух данных натуральных чисел A и B найдет максимальное число C, входящее как в A, так и в B.

Входные данные

В единственной строке входного файла input. txt записаны числа A и B (1 £ A, B £ ). Числа записаны в десятичной системе счисления.

Выходные данные

В единственную строку выходного файла output. txt нужно вывести найденное число C. Число записать в десятичной системе счисления.

Пример

№	input. txt	output. txt
1	3 6	3

Разбор

Достаточно стандартное применение метода динамического программирования.

Программа на Паскале

var

a, b : string;

c : array [1..30, 1..30] of longint;

n, m, d : longint;

i, j : integer;

begin

assign(input,'input. txt'); reset(input);

assign(output,'output. txt'); rewrite(output);

read(n, m);

a:='';

while n>0 do begin a:=chr(n mod 2 +48)+a; n:=n div 2 end;

n:=length(a);

b:='';

while m>0 do begin b:=chr(m mod 2 +48)+b; m:=m div 2 end;

m:=length(b);

for j:=1 to m do c[1,j]:=1;

for i:=1 to n do c[i,1]:=1;

for i:=2 to n do

for j:=2 to m do

begin

d:=c[i-1,j];

if c[i, j-1]>d then d:=c[i, j-1];

if (a[i]=b[j]) and (2*c[i-1,j-1]+ord(a[i])-48>d) then

d:=2*c[i-1,j-1]+ord(a[i])-48;

c[i, j]:=d

end;

write(c[n, m])

end.

Задача D. Матрица

(Время - 1 сек., память - 16 Мб, баллы - 100)

Задана прямоугольная таблица A размером N (количество строк) на M (количество столбцов), элементами которой являются натуральные числа, меньшие 30000. Строки и столбцы нумеруются с единицы, начиная с левого верхнего угла.

Требуется написать программу, которая находит таблицу B такого же размера, элемент bi,j которой равен максимальному из элементов части таблицы A, ограниченной снизу проходящими через i, j диагоналями.

Например, для i=3, j=2 часть таблицы, в которой ищется максимальный элемент, показана на рисунке

x	x	x	x
x	x	x
	x

Входные данные

Входной файл input. txt содержит в первой строке числа N и M, записанные через пробел (1 £ N*M £ 30000). В следующих N строках записано через пробел по M чисел.

Выходные данные

В выходной текстовый файл output. txt записывается по строкам найденная матрица, в строках числа разделяются пробелами.

Пример

№	input. txt	output. txt
1	2 2 1 3 4 2	1 3 4 3

Разбор

Достаточно стандартное применение метода динамического программирования.

Программа на Паскале

var

n, m, i, j, x, y, z, b : integer;

a : array[1..30001] of integer;

function max4(a, b,c, d:integer):integer;

var m:integer;

begin

m:=a;

if b>m then m:=b;

if c>m then m:=c;

if d>m then m:=d;

max4:=m

end;

begin

assign(input,'input. txt'); reset(input);

assign(output,'output. txt'); rewrite(output);

readln(n, m);

for j:=1 to m do begin

read(a[j]);

write(a[j]); if j<m then write(' ') else writeln

end;

a[m+1]:=0;

for i:=2 to n do begin

x:=0; y:=a[1];

for j:=1 to m do begin

z:=a[j+1]; read(b);

a[j]:=max4(b, x,y, z);

write(a[j]);

if j<m then write(' ') else if i<n then writeln;

x:=y; y:=z

end

end

end.