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

Решение

{$APPTYPE CONSOLE}

uses

SysUtils;

Function Min(a,b,c:word):word;

var

temp:word;

begin

if a<b then temp:=a

else temp:=b;

if temp<c then min:=temp

else min:=c;

end;

var

f:text;

n,m,i,j:byte;

a:array[0..21,0..21] of word;

res:word;

begin

assign(f,'Path.inp');

reset(f);

readln(f,n,m);

for i:=1 to n do

for j:=1 to m do

read(f,a[i,j]);

close(f);

for i:=1 to n do

begin

a[i,0]:=65535;

a[i,m+1]:=65535;

end;

for j:=0 to m+1 do

a[0,j]:=0;

for i:=1 to n do

for j:=1 to m do

a[i,j]:=min(a[i-1,j-1],a[i-1,j],a[i-1,j+1])+a[i,j];

res:=65535;

for j:=1 to m do

if a[n,j]<res then res:=a[n,j];

assign(f,'Path.out');

rewrite(f);

writeln(f,res);

close(f);

end.

Билеты

Ограничение по времени: 1 сек.

Входной файл: Ticket.inp

Выходной файл: Ticket.out

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

Известно, что на продажу i-му человеку из очереди 1-го билета кассир тратит Ai секунд, а на продажу 2-х билетов - Bi секунд.

Билеты на группу всегда покупает 1й человек. Никто также не покупает лишних билетов.

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

Входные данные для программы (текстовый файл Ticket.inp)

Первая строка входного файла содержит N (N <= 1000) - число покупателей, затем идут N строк, содержащие 2 числа Ai и Bi (1 <= Ai, Bi <= 20 ) - время в минутах.

Результат работы программы (текстовый файл Ticket.out)

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

Примеры входных данных и результатов

Подсказка:

В первом случае минимальное время в минутах, за которое может быть обслужен 1-й болельщик, составляет 1 минуту.

2 болельщика - 2 минуты.

3 болельщика тоже 2 минуты.

4 болельщика - 7 минут.

И все 5 болельщиков - 4 минуты :).

Решение

{$APPTYPE CONSOLE}

uses

SysUtils;

Function Min(a,b:word):word;

begin

if a<b then min:=a

else min:=b;

end;

var

f:text;

i,n:word;

a,b:array[1..1000] of byte;

mas:array[0..1000] of word;

begin

assign(f,'Ticket.inp');

reset(f);

readln(f,n);

for i:=1 to n do

read(f,a[i],b[i]);

close(f);

mas[0]:=0;

mas[1]:=a[1];

for i:=2 to n do

mas[i]:=min(mas[i-1]+a[i],mas[i-2]+b[i-1]);

assign(f,'Ticket.out');

rewrite(f);

writeln(f,mas[n]);

close(f);

end.

Список рекомендованной литературы

1. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы.: Пер. с англ.: Уч. пос. Ї М.: Издательский дом “Вильямс”, 2000. Ї 384 с., ил.

2. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. Харьков: Фолио; Ростов н/Д: Феникс, 1997. Ї 368 с.

3. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. Ї М.: Мир, 1989. Ї 360 с., ил.

4. Караванова Т.П. Інформатика: методи побудови алгоритмів та їх аналіз: необчислювальні алгоритми: .: Навч. посіб. для 9-10 кл. із поглибл. вивч. інф-ки - К.: Генеза. - 2006.- 216 с

5. Караванова Т.П. Інформатика: основи алгоритмізації та програмування: 777 задач з рекомендаціями та прикладами: Навч. посіб. для 8-9 кл. із поглибл. вивч. інф-ки - К.: Генеза. - 2006.- 286 с.

6. Керман, Митчел, К. Программирование и отладка в Delphi. Учебный курс. Пер. с англ.. Ї М.: Издательский дом “Вильямс”, 2002, 672 с.: ил. - Парал. тит.англ.

7. Кнут Д. Искусство программирования. Ї М.: Вильямс, 2000

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001. Ї 960 с., 263 ил.

9. Культин Н.Б., Основы программирования в Delphi 2006 Microsoft .NET Framework-CПб. БХВ-Петербург, 2006 - 487с.:ил.

10. Лавренов С.М. Excel: Сборник примеров и задач. - М.: Финансы и статистика, 2001. - 336 с. : ил. - (Диалог с компьютером)

11. Липский В. Комбинаторика для программистов: Пер. с польск. Ї М.: Мир, 1988. Ї 213 с., ил.

12. Шупруга В.В., Delphi 2006 на примерах CПб. БХВ-Петербург, 2006 - 528с.:ил.

Размещено на Allbest.ru