Рассмотрим несколько олимпиадных задач.

1. Шарик в лабиринте

2. Бюрократы

3. Цепочка слов

4. Полоска домино

5. Гангстеры

6. Ковролин для минотавра

7. Значение выражения

8. Последовательность

9. Абракадабра

10. Конструктор

11. Арифметическая прогрессия

12. Вычеркивание чисел

13. Замечательные числа

14. Симметричные последовательности

Задача 1. Шарик в лабиринте

Юный программист Петя все свободное от написания программ и приема пищи время посвящает известной карманной игре «Шарик в лабиринте», суть которой заключается в том, чтобы провести шарик по пластмассовому лабиринту. Для этого лабиринт можно наклонять, отчего шарик начинает катиться по проходу с ускорением g = 9,811 м/с². Шарик катится строго по прямой параллельно сторонам лабиринта. На поворотах шарик мгновенно и полностью останавливается.

Лабиринт имеет размер N  N см и высоту 1 см и состоит из клеток — кубиков 1  1  1 см. Каждый такой кубик является либо проходом, либо стенкой. Ровно один из кубиков помечен как выход из лабиринта.

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

Примечание

Путь, пройденный равноускоренно движущимся из состояния покоя телом за время t, равен g*t²/2.

Формат входного файла

В первой строке входного файла задано число N (1 ≤ N ≤ 10). В следующих N строках задано описание лабиринта.

Каждая строка описания состоит из N цифр от 0 до 2, разделённых пробелами. Здесь 0 соответствует пустой клетке, 1 — стенке, 2 — выходу. При этом цифра 2 встречается во всем описании ровно один раз, а первая цифра первой строки не равна 1.

Формат выходного файла

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

Пример

Input.txt	Output.txt
3 0 1 1 1 0 1 2 0 0	-1
4 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 2	0.156

Задача решается методом перебора с возвратом.

const dx:array[1..4] of shortint=(-1,1,0,0);

dy:array[1..4] of shortint=(0,0,-1,1);

g=981.1;

type cor=record

i,j,z:byte;

end;

var

a:array[1..10,1..10] of shortint; карта лабиринта

exitx,exity:integer; текущие координаты x и y

res,t:real;

n:integer;

procedure init;

var i,j:integer;

begin

assign(input,'input.txt');

reset(input);

read(n);

for i:=1 to n do

for j:=1 to n do

read(a[i,j]);

close(input);

end;

function can(i,j:integer):boolean; проверяет можно ли двигаться вперед

begin

can:=(i>0)and(j>0)and(i<=n)and(j<=n)and(a[i,j]<>1);

end;

procedure rec(i0,j0:byte;nap:byte;d:byte); рекурсивная процедура обхода

var i:byte; лабиринта

begin

if t>res then exit; если текущее время хуже, то возвращаемся

if (i0=exitx)and(j0=exity) если дошли до выхода

then

begin

if t<res then begin res:=t;exit;end; и время лучше, то запоминаем его и

выходим

end

else

begin

for i:=1 to 4 do проверяем по очереди соседние клетки

if can(i0+dx[i],j0+dy[i]) then если в соседнюю клетку можно пойти

begin

a[i0+dx[i],j0+dy[i]]:=1; отмечаем клетку как пройденную

if nap=i then если направление то же самое

begin

t:=t-sqrt(d*2/g)+sqrt((d+1)*2/g); то увеличиваем время и длину пути на 1

rec(i0+dx[i],j0+dy[i],i,d+1); и продолжаем движение из этой точки

по прямой

t:=t+sqrt(d*2/g)-sqrt((d+1)*2/g); иначе возвращаемся назад и

уменьшаем время

end else

begin

t:=t+sqrt(2/g); если поворачиваем

rec(i0+dx[i],j0+dy[i],i,1); начинаем ускоряться заново

t:=t-sqrt(2/g); если попали в тупик, возвращаемся на

шаг назад

end;

a[i0+dx[i],j0+dy[i]]:=0; отмечаем клетку как непройденную

end;

end;

end;

procedure solve;

var i,j:integer;

begin

res:=maxlongint; берем за результат большое число

for i:=1 to n do находим координаты выхода

for j:=1 to n do

if a[i,j]=2 then

begin

exitx:=i;exity:=j;

end;

t:=0;

a[1,1]:=1;

rec(1,1,5,0); запускаем рекурсивную процедуру

поиска самого короткого по времени

пути

end;

procedure out;

var i:integer;

begin

assign(output,'output.txt');

rewrite(output);

if res=maxlongint then write('-1') если пути нет, то выводим -1

else rite(Res:0:3); иначе результат

close(output);

end;

begin init; solve; out; end.

переборзадачи

Задача 2 Бюрократы нет решения

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

procedure справка от (i)

begin

Если ему ничего не надо то выход;

для всех, которые ему нужны(j)

begin

Справка от (j);

Занести(j) в маршрут;

Удалить(j) из списка требований всех бюрократов;

end;

end;

переборзадачи