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

Переселяется A[1,2], A[2,1], A[3,3]

Переселяется A[1,3], A[2,2], A[3,1]

Количество каждого из переселений легко подсчитать:

= min(A[1,2], A[2,1], A[3,3]) = P1

= min(A[1,3], A[2,2], A[3,1]) = P2

В итоге, от A[1,2], A[2,1], A[3,3] отнимается Р1, а от A[1,3], A[2,2], A[3,1] отнимается Р2, а Р1 и Р2 добавляются к минимальному числу переселений. Потом к минимальному числу добавляется (неправильность)/2 и полученный результат выводится в ответ.

Сложность: О(N)

{ NetOI-2005: Tour2 COUNTRY}

Program Country;

const

s:array[1..3]of byte = (1,3,2);

var

g:array[1..50000]of byte;

i,n,m,m1:longint;

w:array[1..3,1..3] of longint;

k:array[1..3]of word;

function min(a,b,c:longint):longint;

begin

if a<b then begin

if a<c then min:=a else

min:=c;

end else

if b<c then min:=b else

min:=c;

end;

begin

k[1]:=0;k[2]:=0;k[3]:=0;

read(n);

for i:=1 to n do begin

read(g[i]);

inc(k[s[g[i]]]);

end;

for i:=1 to k[1] do inc(w[1,g[i]]);

for i:=k[1]+1 to k[1]+k[2] do inc(w[3,g[i]]);

for i:=k[1]+k[2]+1 to n do inc(w[2,g[i]]);

m1:=min(w[1,3],w[2,1],w[3,2]);

m:=m1;

w[1,3]:=w[1,3]-m1;

w[2,1]:=w[2,1]-m1;

w[3,2]:=w[3,2]-m1;

m1:=min(w[1,2],w[2,3],w[3,1]);

m:=m+m1;

w[1,2]:=w[1,2]-m1;

w[2,3]:=w[2,3]-m1;

w[3,1]:=w[3,1]-m1;

m:=m+(w[1,2]+w[1,3]+w[2,1]+w[2,3]+w[3,1]+w[3,2])div 2;

write(m);

end.

Building

Задача. Компания Megasoft хочет построить новый офис. Карта местности представляет собой прямоугольник M*N, разделенный на единичные квадраты. Некоторые квадраты полностью непригодны для застройки. Помогите владельцу компании Гиллу Бейтсу выбрать для офиса участок прямоугольной формы с максимальной площадью. Граница участка всегда проходит по границам квадратов.

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

Пример

Ввод>

5 7 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 0

Вывод> 9

Решение. Сперва строим массивы U[i,j] и D[i,j], где в U[i,j] хранится, на сколько клеток вверх от данной (включая данную) клетки пригодны для строительства, а в D[i,j] хранится то же самое, но вниз. Оба этих массива можно создать за O(MN) (просто проходимся по каждому столбцу сверху (снизу) вниз (вверх)). Отмеченными клетками назовем все непригодные клетки, а также, клетки с координатами вида [0, j] понятно, что любой прямоугольник будет прилегать к одной из отмеченных клеток справа (иначе его можно было бы расширить влево). Теперь делаем так: проходимся по массиву и для каждой встреченной отмеченной клетки делаем такую операцию:

Пусть координаты нашей отмеченной клетки [i, j], а координаты следующей за ней справа отмеченной (или края прямоугольника) [I, j] тогда для t=i..I вычисляем s(t) площадь наибольшего квадрата, прилагающего к клетке [i, j] и доходящего по горизонтали до [t, j] это делается в один проход: пусть u(t) d(t) - это ф-ции, показывающие насколько максимум такой прямоугольник может подниматься вверх и опускаться вниз от j-й строчки тогда s(t)=(t-i+1)(u(t)+d(t)-1), а сами u(t) и v(t) вычисляются из соотношения u(t) = min(U[t, j],u[t-1]) d(t) = min(D[t, j],d[t-1]). Потом берется максимум s(t) по всем t. Итак, видно, что для каждой отмеченной клетки мы можем найти наибольший прямоугольник, прилагающий к ней, пройдясь до следующей отмеченной клетки. В итоге, мы пройдемся по каждой клетке прямоугольника по 1 разу.

Сложность: O(MN)

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

{ NetOI-2005: Tour2: Building }

Program Building;

var

pole: array[1..100,1..100]of byte;

down:array[1..100,1..100]of byte;

i,j,m,n,t:byte;

max,tec:word;

procedure makedown;

var i,j:byte;

begin

for j:=1 to n do begin

down[m,j]:=pole[m,j];

for i:=m-1 downto 1 do

if pole[i,j]=1 then down[i,j]:=down[i+1,j]+1 else

down[i,j]:=0;

end;

end;

function kol(a,b:byte):word;

var

max,tec,vis:word;

i:byte;

begin

max:=0;

vis:=100;

i:=b;

while (i<=n)and(pole[a,i]>0) do begin

if down[a,i]<vis then vis:=down[a,i];

if max<vis*(i-b+1) then max:=vis*(i-b+1);

inc(i);

end;

kol:=max;

end;

begin

read(m,n);

if m<n then begin

for i:=1 to m do

for j:=1 to n do

read(pole[j,i]);

t:=m;

m:=n;

n:=t;

end else

begin

for i:=1 to m do

for j:=1 to n do read(pole[i,j]);

end;

max:=0;

makedown;

for i:=1 to m do

for j:=1 to n do begin

tec:=kol(i,j);

if tec>max then max:=tec;

end;

write(max);

end.

Разбор задач II и III этапов Всеукраинской олимпиады по информатике в АРКрым

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

Исходные данные (файл decode.inp)

Входной текстовый файл decode.inp содержит описание ленты.

Результат (файл decode.out)

Выходной текстовый файл decode.out содержит декодированное сообщение.

ВНИМАНИЕ! Выходной файл должен содержать только те символы, который были закодированы на ленте!

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

Файл decode.inp	Файл decode.out
___________ | o . o| | o . | | ooo . o| | ooo .o o| | oo o. o| | oo . oo| | oo o. oo| | o . | | oo . o | | ooo . o | | oo o.ooo| | ooo .ooo| | oo o.oo | | o . | | oo .oo | | oo o.ooo| | oooo. | | o . | | oo o. o | | ooo .o o| | oo o.o o| | ooo . | | ooo . oo| | o . | | oo o.ooo| | ooo .oo | | oo .o o| | ooo . o | | o . | | ooo .o | | oo o. | | oo .o o| | o . | | oo o.o | | oo . o| | oooo. o | | oooo. o| | o . | | oo .o | | oo o.ooo| | oo .ooo| | o o.oo | | o. o | ___________	A quick brown fox jumps over the lazy dog.

Решение

Каждая строка ленты содержит один байт. Дырка единичный бит, её отсутствие - нулевой. Из восьми битов складывается байт и переводится в символ по кодировке ASCII.

Общая временная сложность алгоритма: O(L)

{ *** Burdakov Danil School#2 Yalta *** }

var

counter:integer;

sent:byte;

mustsend:boolean;

s:string;

function f(index,slagaemoe:integer):integer;

begin

if s[index]='o' then f:=slagaemoe else f:=0;

end;

BEGIN

assign(input,'decode.inp');

assign(output,'decode.out');

reset(input);

rewrite(output);

counter:=0;

mustsend:=false;

repeat

if counter<2 then inc(counter);

readln(s);

if mustsend and not((s='___________') and (sent=10)) then

write(chr(sent));

if s<>'___________' then

begin

mustsend:=true;

sent:=f(2,128)+f(3,64)+f(4,32)+f(5,16)+f(6,8)+f(8,4)+f(9,2)+f(10,1);

end;

until (s='___________') and (counter>1);

close(input);

close(output);

END.

Конфеты

Ограничение времени: 5 секунд

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

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

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

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

Исходные данные (файл sweet.inp)

Входной текстовый файл sweet.inp состоит из двух строк.

Первая строка содержит одно целое число N - длину конфеты в сантиметрах (1 <= N <= 200). Следующая строка - последовательность символов 0 или 1, описывающая дольки конфеты от левого конца к правому концу ('0' - кислая долька, '1' - сладкая).

Результат (файл sweet.out)

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

ВНИМАНИЕ! Число выводить с переводом строки!

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

Файл sweet.inp	Файл sweet.out
15 100110001010001	9
16 0010111101100000	13

Решение

Сначала можно построить матрицу G[0..200,0..200], где G[i,j]=<количеству сладких долек в куске от i-й дольки по j-ю>. Она строится за O(n^2). Используется только верхний треугольник матрицы (где i<j). Потом строим матрицу A[0..200,0..200]. Элемент A[i,j] показывает длину части конфеты, которую удастся продать из куска [I,J] (при условии, что этот кусок уже вырезан из конфеты). Очевидно, что i<j.

A[i,i]=

A[i,j] =

Ответом будет a[1,N].

Общая временная сложность алгоритма: O(N^2)

var

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

oc:array[0..220,0..220] of byte;

konfeta:string;

BEGIN

assign(input,'sweet.inp');

assign(output,'sweet.out');

reset(input);

rewrite(output);

readln(n);

readln(konfeta);

fillchar(oc,sizeof(oc),0);

for i:=0 to n-1 do oc[i+1,i]:=ord(konfeta[i+1])-ord('0');

for k:=2 to n do

for i:=k to n do

oc[i,i-k]:=oc[i,i-1]+oc[i-1,i-k];

for i:=0 to n-1 do oc[i,i+1]:=ord(konfeta[i+1])-ord('0');

for k:=2 to n do

for i:=0 to n-k do

if 2*oc[i+k,i]>k then

oc[i,i+k]:=k

else

begin

max:=0;

if oc[i+k,i]>0 then

for j:=i+1 to i+k-1 do

if max<oc[i,j]+oc[j,i+k] then max:=oc[i,j]+oc[j,i+k];

oc[i,i+k]:=max;

end;

writeln(oc[0,n]);

close(input);

close(output);

END.

Простые множители

Ограничение времени: 1 секунда

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

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

Целое число g > 1 называется простым, если его положительными делителями являются только единица и само это число (в противном случае число называется составным). Например, число 21 - составное, число 23 - простое. Заметьте, что разложение положительного целого числа g на простые множители, то есть

единственно, если f_i > 1 для всех i и f_i < f_j для i < j.

Исходные данные (файл prime.inp)

Входной текстовый файл prime.inp содержит единственное целое число g в диапазоне -2³¹ < g <2³¹, не равное -1, 0 или 1.

Результат (файл prime.out)

Выходной текстовый файл prime.out должен содержать единственную строку, в которой записано входное число и его простые множители. Для входного числа

где каждое f_i является простым числом, большим единицы и f_i < f_j для i < j, строка вывода должна иметь вид

Когда g < 0 и

то строка вывода должна иметь вид

ВНИМАНИЕ! Все числа, знаки умножения и знак равенства разделены ровно одним пробелом!

Строка в выходном файле должна заканчиваться переводом строки!

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

Файл prime.inp	Файл prime.out
-190	-190 = -1 x 2 x 5 x 19
-191	-191 = -1 x 191
-192	-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
196	196 = 2 x 2 x 7 x 7
197	197 = 197
200	200 = 2 x 2 x 2 x 5 x 5
199	199 = 199
198	198 = 2 x 3 x 3 x 11

Решение

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

Общая временная сложность алгоритма: O()

Program prime;

var

a,i,k,b:longint;

m:array[1..40]of longint;

function prost(a:longint):boolean;

var i:longint;

o:boolean;

begin

if a in[2,3]

then prost:=true else

begin

o:=false;

for i:=2 to round(sqrt(a))+1 do if (a mod i=0)and not o then o:=true;

prost:=not o;

end;

end;

procedure deist;

begin

inc(i);

if prost(i)and(a mod i=0) then

begin

inc(k);

m[k]:=i;

a:=a div i;

dec(i);

if prost(a) then begin inc(k); m[k]:=a; a:=1; end;

if a>1 then deist;

end;

end;

begin

assign(input,'prime.inp');reset(input);

assign(output,'prime2.out');rewrite(output);

read(b);

a:=b;

write(a,' = ');

if a<0 then begin a:=-a; write(-1);if not prost(a)or(prost(a)and(b<0))then write(' x ') end;

if prost(a) then writeln(a)

else

begin

i:=1;k:=0;

repeat

deist;

until a=1;

for i:=1 to k-1 do write(m[i],' x ');

writeln(m[k]);

end;

close(input);close(output);

end.

Поезд

Ограничение времени: 1 секунда

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

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

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

Исходные данные (файл train.inp)

Входной текстовый файл train.inp состоит из двух строк. В первой строке содержится единственное целое число L (1 <= L <= 50) - количество вагонов в поезде. Во второй строке содержится ровно L различных целых чисел в диапазоне от 1 до L, то есть некоторая перестановка чисел от 1 до L.

Результат (файл train.out)

Выходной текстовый файл train.out должен содержать единственное число - минимальное количество перестановок соседних вагонов, необходимое для того, чтобы расположить вагоны в возрастающем порядке от 1 до L.

ВНИМАНИЕ! Число выводить с переводом строки!

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

Файл train.inp	Файл train.out
3 1 3 2	1
4 4 3 2 1	6
2 2 1	1
4 4 1 2 3	3

Решение

Здесь можно использовать обычную «пузырьковую» сортировку с подсчётом количества перестановок.

Общая временная сложность алгоритма: O(N^2)

var

i,j,l,s:integer;

a:array[0..60] of integer;

BEGIN

assign(input,'train.inp');

assign(output,'train.out');

reset(input);

rewrite(output);

readln(l);

s:=0;

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

for i:=2 to l do

for j:=1 to i-1 do

if a[j]>a[i] then inc(s);

writeln(s);

close(input);

close(output);

END.

Как заработать

Ограничение времени: 5 секунд

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

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

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

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

Исходные данные (файл Money.inp)

Входной текстовый файл Money.inp содержит три числа N, M, P, разделенные одним пробелом (0 < N, M, P < 10001).

Результат (файл Money.out)

Выходной текстовый файл Money.out должен содержать единственное целое число - прибыль Васи в рублях.

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

Файл Money.inp	Файл Money.out
15 10 2	28
21 4 3	48
7 3 2	10

Пояснения к решению задачи:

Решение возможно двумя способами:

1 - с использованием цикла;

2 - с использованием итоговой формулы:

1 способ:

var s,n,m,p:integer;

den:longint;

begin

assign (input,'money.inp'); reset(input);

read (input,n,m,p);

close (input);

while s<n do

begin

inc(s);

if s mod m<>0 then den:=den+p

end;

assign (output,'money.out'); rewrite (output);

write (output,den);

close (output);

end.

2 способ:

var

f:text;

n,m,p,res:longint;

begin

assign(f,'money.inp');

reset(f);

read(f,n,m,p);

close(f);

res:=(n - n div m)*p;

assign(f,'money.out');

rewrite(f);

writeln(f,res);

close(f);

end.

Как строить башни

Ограничение времени: 5 секунд

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

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

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

Вася решил предложить свой проект башни. Она будет расширяться кверху и иметь бесконечное число этажей и комнат. Устроена она следующим образом - на первом этаже одна комната, затем идет два этажа, на каждом из которых по две комнаты, затем идет три этажа на каждом из который по три комнаты и так далее. Вася предлагает Пете сыграть в следующую игру. По номеру комнаты N (0 < N < 2 000 000 000) определить номер этажа и порядковый номер комнаты на этаже (считая слева).

…………….

19 20 21 22

15 16 17 18

12 13 14

9 10 11

6 7 8

4 5

2 3

1

Исходные данные (файл Tower.inp)

Входной текстовый файл Tower.inp содержит единственное число N - номер комнаты (0 < N < 2 000 000 000).

Результат (файл Tower.out)

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

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

Файл Tower.inp	Файл Tower.out
5	3 2
25	9 3

Пояснения к решению задачи:

Из схемы построения видно, что всего квартир в блоке из i этажей i*i.

Таким образом, в цикле мы определим блок из i этажей в котором находиться искомая квартира (для этого мы в переменной etaj будем хранить номера этажей, а от переменной n(номер искомой квартиры) будем отнимать количество квартир в каждом пройденом блоке-так сказать подниматься выше). Дальше уже не составляет труда определение на каком именно этаже находиться искомая квартира, ну и её положение на этаже (это делается не хитрыми манипуляциями mod и div).

var

f:text;

etaj,i,n,komnata:longint;

flag:boolean;

begin

assign(f,'Tower.inp');

reset(f);

read(f,n);

close(f);

i:=0;

etaj:=0;

flag:=false;

while not flag do

begin

inc(i);

if i*i<n then

begin

etaj:=etaj+i;

n:=n-i*i;

end

else flag:=true;

end;

etaj:=etaj+n div i;

if n mod i = 0 then komnata:=i

else

begin

inc(etaj);

komnata:=n mod i;

end;

assign(f,'Tower.out');

rewrite(f);

writeln(f,etaj,' ',komnata);

close(f);

end.

Как складывать слова

Ограничение времени: 5 секунд

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

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

Сегодня Вася учил английский язык. После этого он вырезал из бумаги L (0 < L < 201) карточек. На каждой карточке он написал одну маленькую букву английского алфавита. Теперь он предлагает Пете сыграть в следующую игру. Он складывает из L карточек некоторое слово. Вася должен сложить следующее в лексикографическом (алфавитном) порядке слово, используя все эти карточки.

Исходные данные (файл Words.inp)

Входной текстовый файл Words.inp содержит единственную строку - слово, сложенное Васей.

Результат (файл Words.out)

Выходной текстовый файл Words.out должен содержать слово, которое должен сложить Петя, или `no word' (без кавычек), если не удается найти такое слово.

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

Файл Words.inp	Файл Words.out
abca	acab
aaa	no word

Пояснения к решению задачи:

Сначала ищем первый справа символ, что больше своего предыдущего (справа) т.е. s[i+1]>=s[i] - если такого символа не найдёться, то значит следующую комбинацию мы уже не построим. Этот символ (s[i]) мы будем менять с символом из последовательности справа(s[i+1]..s[l]), с символом, наименьшим из тех что больше заданного - то есть с первым просматривая справа, что окажеться больше s[i]. А дальше, получившуюся последовательность справа от s[i], нужно отсортировать по возрастанию. А если учесть, что они уже отсортированы по убыванию - то просто сделать реверс .

var s:string;

i,l,j,j1:byte;

f:text;

Procedure Swap(var a,b:char);

var

ch:char;

begin

ch:=a;

a:=b;

b:=ch;

end;

begin

assign(f,'Words.inp');

reset(f);

readln(f,s);

close(f);

l:=length(s);

i:=l-1;

while (i>1) and (s[i]>=s[i+1]) do

dec(i);

assign(f,'Words.out');

rewrite(f);

if i=1 then

writeln(f,'no word')

else

begin

for j:=l downto i+1 do

if s[j]>s[i] then

begin

swap(s[i],s[j]);

break;

end;

j1 := 0;

for j:=i+1 to ((l-i) div 2)+i do

begin

swap(s[j],s[l-j1]);

inc(j1);

end;

writeln(f,s);

end;

close(f);

end.

Корабли пустыни

Ограничение времени: 5 секунд

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

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

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

Номер особенного билета имеет следующий вид. Сначала цифры номера идут в неубывающем порядке, а затем в невозрастающем (длина неубывающей или невозрастающей последовательности может быть равна 0).

У Васи есть интересный вопрос. Сколько существует особенных билетов, номер которых содержит ровно S цифр.

Исходные данные (файл Ships.inp)

Входной текстовый файл Ships.inp содержит единственное число S (1 ? S ? 20) - количество цифр в номере билета. Номер может иметь лидирующие нули.

Результат (файл Ships.out)

Выходной текстовый файл Ships.out должен содержать единственное целое число - количество особенных билетов.

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

Файл Ships.inp	Файл Ships.out
1	10
3	715

Пояснения к решению задачи:

Возможны 2 способа решения:

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

2 - способ - просчитаны все 20 элементов при помощи вспомогательной программы- вручную.

1 способ:

var

f:text;

kol:int64;

s,k:byte;

procedure help(nomer,pred:byte);

var

i:byte;

begin

if nomer>s then

begin

inc(kol);

exit;

end;

if nomer<=k then

for i:=pred to 9 do

help(nomer+1,i)

else

if nomer=k+1 then

begin

if pred>=1 then

for i:=pred-1 downto 0 do

help(nomer+1,i);

end

else

for i:=pred downto 0 do

help(nomer+1,i);

end;

begin

assign(f,'Ships.inp');

reset(f);

read(f,s);

close(f);

kol:=0;

k:=0;

for k:=1 to s do

help(1,0);

assign(f,'Ships.out');

rewrite(f);

writeln(f,kol);

close(f);

end.

2 способ:

var

f:text;

a:array[1..20] of int64;

s:byte;

begin

assign(f,'Ships.inp');

reset(f);

read(f,s);

close(f);

a[1]:=10;

a[2]:=100;

a[3]:=715;

a[4]:=4015;

a[5]:=18832;

a[6]:=76714;

a[7]:=278707;

a[8]:=920491;

a[9]:=2803658;

a[10]:=7963384;

a[11]:=21280337;

a[12]:=53886781;

a[13]:=130069928;

a[14]:=300752764;

a[15]:=668955542;

a[16]:=1436458486;

a[17]:=2987013068;

a[18]:=6031074184;

a[19]:=11851853042;

a[20]:=22714926826;

assign(f,'Ships.out');

rewrite(f);

writeln(f,a[s]);

close(f);

end.

Гирлянда

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

Задание

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

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

Единственная строка входного файла GARLAND.DAT содержит одно целое число N (1?N?10⁹) - номер секунды.

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

Единственная строка выходного файла GARLAND.SOL должна содержать целое число - количество лампочек, которые будут гореть на секунде N.

Пример входных и выходных данных

GARLAND.DAT	GARLAND.SOL
5	2

Программа реализована наTurbo Delphi Explorer { tde }

{"stupid" generator with O(N^2)}

{$APPTYPE CONSOLE}

{$B-,R-,O+}

const

maxn=100001;

var

fi,fo:text;

n,i,j,ans:longint;

page:byte;

a:array[0..1,0..maxn] of boolean;

begin

assign(fi,'garland.dat');

assign(fo,'garland.sol');

reset(fi);

rewrite(fo);

readln(fi,n);

page:=0;

fillchar(a[page],sizeof(a[page]),0);

a[page,1]:=true;

for i:=2 to n do

begin

page:=1-page;

fillchar(a[page],sizeof(a[page]),0);

for j:=1 to n do

a[page,j]:=a[1-page,j-1] xor a[1-page,j+1];

end;

ans:=0;

for i:=1 to n do

inc(ans,byte(a[page,i]));

writeln(fo,ans);

close(fi);

close(fo);

end.

Острова

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

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

Задание

Напишите программу ISLANDS, которая по карте островов находит минимальную стоимость строительства группы мостов, которые соединяют все острова.

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

Первая строка выходного файла ISLANDS.DAT содержит два целых числа N и M (1?N, M?500) - размеры карты островов. Каждая из последующих N строк содержит M символов 0 (вода) либо 1 (суша).

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

Единственная строка выходного файла ISLANDS.SOL должна содержать одно целое число - найденную минимальную стоимость строительства мостов. Если соединить острова мостами невозможно, требуются вывести число -1.

Пример входных и выходных данных

ISLANDS.DAT	ISLANDS.SOL
5 5 01110 00100 10010 00100 10001	8

Задача реализовани на Free Pascal.

{ fp }{$B-,O+,R-,H+}{$M 20000000,0,20000000}

const maxMN = 500;

dr: array[1..4] of longint = (-1,0,0,1);

dc: array[1..4] of longint = (0,-1,1,0);

type TEdge = record v,w,len : longint;

end;

TDSNode = record parent,rank : longint;

end;

var n,m,ans,ucnt : longint;

field : array [1..maxMN] of String;

island : array [1..maxMN,1..maxMN] of longint;

i,j,qb,qe,r,c,d,beg : longint;

ifs,ofs : text;

iCnt,eCnt : longint;

q : array [1..maxMN*maxMN,1..2] of longint;

edges : array [1..maxMN*maxMN] of TEdge;

nds : array [1..maxMN*maxMN] of TDSNode;

function DSRepr(x : longint):longint;

begin

if nds[x].parent=x then DSRepr:=x

else begin

nds[x].parent:=DSRepr(nds[x].parent);

DSRepr:=nds[x].parent;

end;

end; { DSRepr }

function DSUnion(x,y : longint):boolean;

begin

x:=DSRepr(x);

y:=DSRepr(y);

if x=y then DSUnion:=false

else begin

if nds[y].rank>nds[x].rank then begin

x:=x xor y;y:=x xor y;x:=x xor y;

end;

if nds[x].rank=nds[y].rank then inc(nds[x].rank);

nds[y].parent:=x;

DSUnion:=true;

end;

end; { DSUnion }

procedure SortEdges;

procedure Swap(i,j : longint);

var tmp : TEdge;

begin

tmp:=edges[i];

edges[i]:=edges[j];

edges[j]:=tmp;

end; { Swap }

procedure Heapify(i,max : longint);

var j : longint;

begin

while 2*i<=max do begin

j:=2*i;

if (j+1<=max) and (edges[j].len<=edges[j+1].len) then inc(j);

if edges[i].len<edges[j].len then begin

Swap(i,j);

i:=j;

end

else i:=max+1;

end;

end; { Heapify }

var i : longint;

begin

for i:= eCnt div 2 downto 1 do Heapify(i,eCnt);

for i:= eCnt downto 2 do begin

Swap(1,i);

Heapify(1,i-1);

end;

end; { SortEdges }

begin

assign(ifs,'islands.dat'); reset(ifs); assign(ofs,'islands.sol'); rewrite(ofs); readln(ifs,n,m);

for i:=1 to n do readln(ifs,field[i]);

iCnt:=0;

fillchar(island,sizeof(island),0);

{Finding islands}

for i:=1 to n do

for j:=1 to m do

if (field[i][j]='1') and (island[i,j]=0) then begin

inc(iCnt); qb:=1;qe:=1; island[i,j]:=iCnt; q[qe,1]:=i;q[qe,2]:=j;inc(qe);

while qb<>qe do begin

r:=q[qb,1];c:=q[qb,2];inc(qb);

for d:=1 to 4 do

if (r+dr[d]>0)and(r+dr[d]<=n)and(c+dc[d]>0)and(c+dc[d]<=m)and

(field[r+dr[d]][c+dc[d]]='1')and(island[r+dr[d],c+dc[d]]=0) then begin

island[r+dr[d],c+dc[d]]:=iCnt;

q[qe,1]:=r+dr[d];q[qe,2]:=c+dc[d];inc(qe);

end;

end;

end;

{ Finding possible bridges }

eCnt:=0;

for i:=1 to n do begin

beg:=n+5;

for j:=1 to m do

if field[i][j]='1' then begin

if (j-beg>1) and (island[i,j]<>island[i,beg]) then begin

inc(eCnt);

edges[eCnt].v:=island[i,j];edges[eCnt].w:=island[i,beg];edges[eCnt].len:=j-beg-1;

end;

beg:=j;

end;

end;

for j:=1 to m do begin

beg:=m+5;

for i:=1 to n do

if field[i][j]='1' then begin

if (i-beg>1) and (island[i,j]<>island[beg,j]) then begin

inc(eCnt);

edges[eCnt].v:=island[i,j];edges[eCnt].w:=island[beg,j];edges[eCnt].len:=i-beg-1;

end;

beg:=i;

end;

end;

SortEdges;

{ Kruskal's algo }

for i:=1 to iCnt do begin

nds[i].parent:=i;

nds[i].rank:=0;

end;

ans:=0;

ucnt:=0;

for i:=1 to eCnt do begin

if DSUnion(edges[i].v,edges[i].w) then begin

inc(ans,edges[i].len);

inc(ucnt);

end;

end;

if ucnt=iCnt-1 then writeln(ofs,ans)

else writeln(ofs,'-1');

close(ifs);

close(ofs);

end.

Геном Ньютона

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

Разработанное оборудование получает представление генома в виде набора множеств чисел. Каждое множество задается четверкой чисел s, f, a, b. Такому множеству принадлежат a последовательных целых чисел начиная с s, следующие b чисел множеству не принадлежат, следующие a снова принадлежат, и т.д. Все числа множества не превышают f. Например, множество (s=1, f=10, a=2, b=1) содержит числа: 1, 2, 4, 5, 7, 8, 10, а множество (s=5, f=50 a=1, b=19) числа: 5, 25, 45.

Задание

Напишите программу GENOME, которая по представлению генома в виде набора множеств чисел установит, обладает ли его владелец каким-то генетически обусловленным талантом, и определит его номер.

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

Первая строка входного файла GENOME.DAT содержит количество множеств N (1?N?10 000) в наборе. Последующие N строк задают сами множества. Каждое множество задается четверкой чисел - s, f, a, b, (1?s, f, a, b<10⁹; s?f). Гарантируется, что представление генома содержит не больше одного числа, которое встречается нечетное количество раз.

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

Единственная строка выходного файла GENOME.SOL должна содержать целое число, которое встречается нечетное количество раз в представлении генома, либо 0, если такого числа не существует.

Пример входных и выходных данных

GENOME.DAT	GENOME.SOL
4 7 59 1 9 7 82 1 49 17 50 1 29 27 27 1 1	37

Программа реализована наTurbo Delphi Explorer

uses

SysUtils;

var

f:textFile;

n,s,l,a,a1,b,i,temp,res:longint;

begin

assignfile(f,'GENOME.DAT');

reset(f);

readln(f,n);

res:=0;

for i := 1 to n do

begin

read(f,s,l,a,b);

inc(b);

temp:=s;

a1:=1;

while temp<=l do

begin

res:=res xor temp;

if a1=a then

begin

temp:=temp+b;

a1:=1;

end

else

begin

inc(a1);

inc(temp);

end;

end;

end;

closefile(f);

assignfile(f,'GENOME.SOL');

rewrite(f);

writeln(f,res);

closefile(f);

end.

Скидки

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

1. При покупке трех товаров вы платите за них как за два самых дорогих из них.

2. При покупке четырех товаров вы платите за них как за три самых дорогих из них.

Таким образом, определенные товары можно объединить в тройки либо четверки и заплатить за них меньше. Требуется определить наименьшую возможную сумму денег, которая будет потрачена на приобретение всех подарков. Например, если цены пяти выбранных подарков составляют: 50, 80, 50, 100, 20, то можно отдельно купить четыре первых товара, получить за них скидку, и потом купить оставшийся подарок по его номинальной цене. В целом вся покупка будет стоить 250 денежных единиц, вместо 300.

Задание

Напишите программу DISCOUNT, которая по ценам всех подарков, находит минимальную сумму денег, достаточную для их покупки.

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

Первая строка входного файла DISCOUNT.DAT содержит одно целое число N (0?N?10 000). Вторая строка содержит N натуральных чисел - цены подарков. Сумма цен всех подарков меньше чем 10⁹. Объединять можно не только те товары, которые идут подряд во входных данных.

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

Единственная строка выходного файла DISCOUNT.SOL должна содержать одно целое число - найденную минимальную сумму денег, за которую можно купить все подарки.

Пример входных и выходных данных

DISCOUNT.DAT	DISCOUNT.SOL
5 50 80 50 100 20	250

Задача реализовани на Free Pascal.{ fp }

const

MAX_N = 10000;

var

n, i, sum : Longint;

A : array[1..MAX_N] of integer;

procedure swap(var a : integer; var b : integer);

var c : integer;

begin

c:=a;

a:=b;

b:=c;

end;

procedure bubbleSort;

var

i, j : integer;

begin

for i := 1 to n-1 do

for j := 1 to n-1 do

if (a[j] < a[j+1]) then swap(a[j], a[j+1]);

end;

begin

Assign(input, 'discount.dat');

Reset(input);

ReadLn(n);

for i:=1 to n do

Read(A[i]);

Close(input);

bubbleSort;

sum := 0;

for i := 1 to n do

if i mod 3 <> 0 then sum := sum + a[i];

Assign(output, 'discount.sol');

Rewrite(output);

Writeln(sum);

Close(output);

end.

Точки

На плоскости задано N точек. Кроме того, на плоскости заданы две базовые точки.

Задание

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

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

Первая строка входного файла POINTS.DAT содержит одно целое число N (0?N?10 000) - количество точек. Вторая строка содержит координаты двух базовых точек в формате x₁ y₁ x₂ y₂. Каждая из последующих N строк содержит координаты точки плоскости в формате x y. Координаты точек - целые числа, по модулю не превышающие 10 000. Базовые точки отличаются, по крайней мере, одной координатой.

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

Единственная строка выходного файла POINTS.SOL должна содержать целое число - найденное максимальное количество точек, которые попадут в полосу, образованную оптимально проведенными параллельными прямыми через базовые точки.

Пример входных и выходных данных

POINTS.DAT	POINTS.SOL
4 0 0 50 0 0 -50 -1 0 50 0 100 50	3

Задача реализовани на Visual C++

/* vc_cpp */

#include <vector>

#include <algorithm>

#define _USE_MATH_DEFINES

#include <math.h>

#include <assert.h>

using namespace std;

#define EPS 1e-9

FILE * fin = fopen("points.dat", "r");

FILE * fout = fopen("points.sol", "w");

struct point

{int x, y;};

inline double vprod(point A, point B, point C)

{return (A.x - B.x) * (C.y - B.y) - (A.y - B.y) * (C.x - B.x);}

int n;point A, B;vector<point> p;

int calc (point A, point A_, point B, point B_)

{ int ans = 0;

for (int i = 0; i < n; ++i)

{double p1 = vprod(p[i], A, A_);double p2 = vprod(p[i], B, B_);

if (fabs(p1) < EPS || fabs(p2) < EPS) ans ++;

else if (p1 * p2 < 0 && fabs(p1*p2) > EPS)

ans ++;}

return ans;}

int main (){ int i, ans;point A_, B_;ans = 0; fscanf(fin, "%d", &n);

fscanf(fin, "%d%d%d%d", &A.x, &A.y, &B.x, &B.y);

assert(A.x != B.x || A.y != B.y);

p.resize(n); for (i = 0; i < n; ++i)

fscanf(fin, "%d%d", &p[i].x, &p[i].y);

for (i = 0; i < n; ++i){A_.x = p[i].x;A_.y = p[i].y; B_.x = B.x + (A_.x - A.x);

B_.y = B.y + (A_.y - A.y);ans = max(ans, calc(A, A_, B, B_));

B_.x = p[i].x;B_.y = p[i].y;

A_.x = A.x + (B_.x - B.x);

A_.y = A.y + (B_.y - B.y);

ans = max(ans, calc(A, A_, B, B_));}

fprintf(fout, "%d\n", ans);fclose(fin); fclose(fout);

return 0;};

Катакомбы

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

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

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

Задание

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

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

Вам предоставлено 10 входных файлов, которые имеют названия CATACOMB.D01, CATACOMB.D02,…, CATACOMB.D10, в таком формате. Первая строка содержит одно целое число D - глубину катакомб. Вторая строка содержит 2^D разных целых чисел от 1 до 2^D. Каждое i-ое из них идентифицирует номер пещеры, в которую должен попасть сундук, находившийся сначала в пещере i.

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

Создайте 10 файлов CATACOMB.S01,…, CATACOMB.S10. Эти файлы должны содержать ответы для соответствующих входных файлов. Первая строка файла должна содержать единственное целое число - минимальное суммарное расстояние, которое пройдут пираты с сокровищами. Вторая строка: целое число K - соответствующее количество обменов. Каждая последующая из K строк: два числа, которые есть номерами пещер, между которыми производится обмен. Обмены должны быть указаны в том порядке, в котором они должны производиться.

Пример входных и выходных данных

CATACOMB.D00	CATACOMB.S00
2 4 3 1 2	20 3 3 4 1 4 3 2

Например, можно проводить обмены таким образом. Сначала поменять местами сокровища в пещерах 3 и 4. Пройденное расстояние 4 (по 2 для каждого сундука). Потом поменять сокровища в пещерах 4 и 1, и 3-2. Расстояние в обоих случаях - 8. Таким образом - все встанут на свои места, а суммарное расстояние будет 20.

Программа реализована наTurbo Delphi Explorer { Greedy dividing cycles }

{$APPTYPE CONSOLE}

{$B-,R-,O+}

const

maxn=256;

var

fi,fo:text;

n,m,h,i,j,numcol:smallint;

ans:smallint;

a:array[1..maxn] of smallint;

color:array[1..maxn] of smallint;

procedure Search(l,r,h:smallint);

var

mid,i,j,k:smallint;

begin

mid:=(l+r)div 2;

if(r>l)then

begin

Search(l,mid,h-1);

Search(mid+1,r,h-1);

end;

for i:=l to mid do

for j:=mid+1 to r do

if(color[i]=color[j])then

begin

inc(numcol);

k:=a[i];

repeat

color[k]:=numcol;

k:=a[k];

until k=a[j];

inc(ans,h);

k:=a[i];

a[i]:=a[j];

a[j]:=k;

end;

end;

begin

assign(fi,'catacomb.dat');

assign(fo,'catacomb.sol');

reset(fi);

rewrite(fo);

readln(fi,n);

n:=1 shl n;

for i:=1 to n do

read(fi,a[i]);

m:=1;

h:=1;

while(2*m<n) do

begin

m:=2*m;

inc(h);

end;

for i:=n+1 to 2*m do

a[i]:=i;

numcol:=0;

fillchar(color,sizeof(color),0);

for i:=1 to n do

if color[i]=0 then

begin

inc(numcol);

j:=i;

repeat

color[j]:=numcol;

j:=a[j];

until j=i;

end;

ans:=0;

Search(1,2*m,h);

writeln(fo,4*ans);

close(fi);

close(fo);

end.

01110001, вот в чем вопрос

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

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

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

Как известно все числа в компьютере представляются с помощью 0 и 1. Ваша задача перевести число из двоичного представления в десятичное.

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

Входной файл содержит одну непустую строку S. Длина S не превышает 60 символов. S содержит только '0' и '1'.

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

Выведите в отдельную строку выходного файла десятичное представление числа.

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

Файл Quest.inp	Файл Quest.out
101	5
01	1
00110011	51
1111	15

Решение задачи

uses

SysUtils;

var

f:text;

s:string;

l,i:byte;

mnoj,res:int64;

begin

assign(f,'Quest.inp');

reset(f);

readln(f,s);

close(f);

L:=length(s);

mnoj:=1;

res:=0;

for i:=l downto 1 do

begin

res:=strtoint(s[i])*mnoj+res;

mnoj:=mnoj*2;

end;

assign(f,'Quest.out');

rewrite(f);

writeln(f,res);

close(f);

end.

Спасите Валли

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

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

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

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

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

Первая строка входного файла содержит 4 числа, H (1 <= H <= 20), W (1 <= W <= 20), X (1 <= X <= H), Y(1 <= Y <= W). Левый верхний угол имеет координаты (1,1) правый нижний (H,W). Следующие H строк содержат по W символов описания каньона. Символ '#' обозначает скалу, символ '*' грунт. Робот может перемещаться только по грунту. Следующая строка содержит непустую строку T, путь робота. T содержит только следующие символы: 'U' обозначает движение вверх, 'D' вниз, 'R' вправо, 'L' влево. Размер T не превышает 200 символов. Во время выброса гамма-лучей память робота тоже могла быть повреждена, как следствие некоторые команды могли поменять свое истинное значение, поэтому следует игнорировать все попытки выхода за пределы каньона или заезда на скалу. Все тесты корректны, начальное положение робота всегда на грунте.

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

Выведите в отдельную строку выходного файла текущие координаты робота в формате "X Y" (два целых числа, разделенных пробелом). Смотрите примеры для разъяснения.

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

Файл Vally.inp	Файл Vally.out
3 3 1 1 *## **# ### URD	2 1
1 3 1 3 *#* LRLRUDUDR	1 3
5 5 1 1 ***** ####* ***** *#### ***** RRRRDDLLLLDDRRRR	5 5
2 5 1 4 ###*# #**** UUDDRRLLLLLLL	2 2

Первый пример:

3 3 1 1

.##

..#

###

URD

Робот начинает своё движение из левой верхней клетки, первую команду 'U' он пропускает, т.к не может выходить за пределы каньона, вторую команду 'R' он тоже пропускает, т.к натыкается на скалу. Только 3 команду 'D' можно выполнить. Робот перемещается на клетку вниз в позицию (2,1).

Второй пример:

1 3 1 3

.#.

LRLRUDUDR

Робот находится в самой правой клетке. Ни одну из команд нельзя выполнить.

Решение

{$APPTYPE CONSOLE}

uses

SysUtils;

var

f:text;

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

s:string;

l,i,j,h,w,x,y,tempx,tempy:byte;

ch:char;

begin

fillchar(a,sizeof(a),0);

assign(f,'Vally.inp');

reset(f);

readln(f,h,w,x,y);

for i:=1 to h do

begin

for j:=1 to w do

begin

read(f,ch);

if ch='*' then a[i,j]:=true;

end;

readln(f);

end;

readln(f,s);

close(f);

l:=length(s);

tempx:=x;

tempy:=y;

for i:=1 to l do

begin

...