- •Оценка эффективности алгоритмов
- •Целочисленная арифметика
- •Дано натуральное число. Выяснить является ли оно палиндромом, то есть читается справа налево и слева направо одинаково
- •Дано натуральное число. Выяснить соотношение между количествами двоек и пятерок в этом числе
- •Найти самую большую и самую маленькую цифры данного натурального числа
- •Выяснить образуют ли цифры натурального числа возрастающую последовательность
- •Формат выходного файла
- •Формат входного файла
- •Формат выходного файла
- •Формат входного файла
- •Формат входного файла
- •Формат выходного файла
- •Длинная арифметика
- •Выходные данные
- •Задачи Задача 52 Иностранные земли
- •Входные данные.
- •Выходные данные.
- •Формат входного файла
- •Формат выходного файла
- •Задачи Задача 56 Уравнение
- •Решение
- •Одномерные массивы
- •Базовые задачи на массивы
- •Задача 15 Сокращение одночленов
- •Входные данные:
- •Задача 16 Школьный субботник
- •Входные данные:
- •Входные данные:
- •Выходные данные:
- •Примеры
- •Задача 27 Решение систем линейных уравнений на Pascal
- •Двумерные массивы
- •Описание массива
- •Способы создания массива
- •Задачи:
- •Задача 5 Малыш играет в "Морской бой 2" Малыш играет в "Морской бой". Поле для игры представляет собой квадрат
- •Входные данные
- •Выходные данные
- •Задача 26 Шарик в лабиринте
- •Примечание
- •Задача 27 Блохи
- •В первой строке входного файла Input.Txt находится 5 чисел, разделенных пробелом: n, m, s, t, q.
- •Входные данные
- •Выходные данные
- •Примеры
- •Задача 34 Магический квадрат
- •Формат входного файла
- •Формат выходного файла
- •Входные данные
- •Выходные данные
- •Входные данные
- •Выходные данные
- •Рекурсия
- •Комбинаторика
- •2.5. Генерация комбинаторных объектов
- •Множество всех подмножеств
- •Перестановки
- •Размещения
- •Перестановки с повторениями
- •Сочетания с повторениями
- •Перебор
- •Символ o()
- •Отсечение по времени
- •Рассмотрим несколько олимпиадных задач.
- •Шарик в лабиринте
- •Задача 1. Шарик в лабиринте
- •Задача 3 Цепочка слов
- •Входные данные
- •Выходные данные
- •Примеры
- •Формат входного файла
- •Формат выходного файла
- •Примеры
- •Динамическое программирование
- •Задача 8 Гвоздики
- •Задача 13 Лесенки
- •Задача 18 Свинья-копилка
- •Входные данные
- •Выходные данные
- •Задача 13 Лесенки Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий.
- •Задача 18 Свинья-копилка
- •Формат входного файла:
- •Формат выходного файла:
- •Примеры
- •Решение
- •Входные данные:
- •Выходные данные:
- •Формат входа
- •Формат выхода
- •Задача 39 Лесенка-2
- •Входные данные
- •Выходные данные
- •Примеры
- •Системы счисления
- •Задача 11 Троичная сбалансированная система счисления
- •Алгоритм перевода
- •Процедуры и функции для работы с символами и строками
- •Определить количество слов в строке
- •Получите строковой массив из всех слов данной строки
- •Получите строковой массив из всех слов данной строки и
- •Получите строковой массив из всех слов данной строки и
- •Составьте программу, определяющую, является ли введенное слово изображением числа
- •Введите 2 целых числа. Преобразуйте числа в две строки, объедините их в одну строку и выведите результат на экран.
- •Вычислите длину самого короткого и самого длинного слов в строке
- •Подсчитайте количество букв в каждом слове данной строки
- •Дана строка. Определить количество слов этой строки, в которых есть ровно две буквы «е»
- •Составьте программу, удаляющую все лишние пробелы из введенной строки
- •Напишите программу, сортирующую символы введенной с клавиатуры строки в порядке возрастания их номеров в ascii-таблице. Например, если введено: 'cba', в результате надо получить ‘abc’.
- •В тексте, состоящем из маленьких латинских букв , подсчитайте количество гласных букв
- •Заданы фамилия, имя и отчество учащегося, разделенные пробелом. Напечатайте его фамилию и инициалы.
- •Сложное слово состоит из двух частей одинаковой длины и соединительной гласной. Найдите обе части этого слова.
- •Вычеркните из слова х те буквы, которые встречаются в слове z
- •Подсчитайте число различных букв в слове
- •Даны два слова. Составьте программу, определяющую можно или нет из букв слова а составить слово в.
- •Даны два слова. Являются ли они анаграммами
- •Является ли данная строка палиндромом?
- •Задача 4. Сокращение одночленов
- •Входные и выходные данные
- •Это чисто техническая задача на аккуратное программирование.
- •Задача 6 Текст
- •Входной файл Input.Txt в первой строке входного файла находится 5 чисел,разделенных пробелом: n, m, s, t, q.
- •Бинарные деревья. Алгоритм HeapSort
- •Поиск в глубину в графе
- •Алгоритм Флойда поиска кратчайших расстояний и кратчайших путей
- •Бинарные деревья. Алгоритм HeapSort
- •Графызадачи Двоичная куча
- •Примеры задач, которые решаются с помощью двоичной кучи
- •Поиск максимального потока методом Форда-Фалкерсона на Pascal
- •Графызадачи Поиск сильно связанных компонент на Pascal
- •Поиск точек раздела, мостов и двусвязных компонент
- •Идеи алгоритмов
- •Точки раздела
- •Двусвязные компоненты
- •Задача 21 Моя Столица
- •Вычислительная геометрия
- •3. Уравнение прямой 2
- •4. Уравнение прямой проходящей через точку м(х0у0)
- •Формат входного файла
Входные данные
Во входном файле Input.txt записаны сначала два числа — начальные координаты расположения путешественника, затем еще два числа — координаты точки, куда ему надо попасть. Затем записано число N — количество гипер-каналов на планете (0N500). Затем идет N описаний гипер-каналов. Каждый гипер-канал описывается четверкой чисел. Первые два задают координаты одной из соединяемых гипер-каналом точек, последние два — координаты другой. Все координаты — целые числа, не превышающие по модулю 1000000.
Выходные данные
В выходной файл Output.txt запишите одно число — минимальную сумму, которой должен располагать путешественник для достижения цели. Если, не рискуя здоровьем, он не сможет добраться до конечной точки, запишите в выходной файл число 171717 (столько стоит лечение лучевой болезни на этой планете).
Примеры
-
Input.txt
Output.txt
10 10
–10 –10
1
2 2 3 3
171717
10 10
-10 –10
2
-10 –10 1 1
10 10 1 1
20
10 10
10 10
4
1 1 2 2
10 10 20 20
2 2 1 1
10 10 20 20
0
Решение методом обхода в ширину. Структура данных одна очередь, реализованная одномерным массивом. В отличие от аналогичных задач, в решении этой задачи мы использовали одну очередь. Отличие в том, что при использовании двух очередей мы меняем очереди , а при использовании одной очереди происходит движение очереди по массиву слева направо и в начале массива остаются уже использованные элементы. Понятно, что можно написать решение с использованием двух очередей. Это можно сделать самостоятельно.
Program giperkanalj;
const maxn=500;
var
xn,yn,xk,yk:array[1..maxn*2] of longint; массив точек – концов каналов
used:array[1..maxn*2] of boolean; отмечаем пройденные точки
og:array[1..maxn*2] of integer; очередь
yk1,yk2,n:integer;
ax,bx,ay,by,res:longint;
procedure init;
var i:integer;
begin
res:=0; результат
yk1:=0;yk2:=0; указатели конца и начала очереди
for i:=1 to maxn*2 do used[i]:=true; отмечаем пройденную точку
fillchar(og,sizeof(og),0); fillchar(xn,sizeof(xn),0);
fillchar(yn,sizeof(yn),0); fillchar(xk,sizeof(xk),0);
fillchar(yk,sizeof(yk),0);
assign(input,'h.in'); reset(input);
read(ax,ay,bx,by,n);
for i:=1 to n do read(xn[i],yn[i],xk[i],yk[i]);
close(input);
end;
procedure out;
begin
assign(output,'h.out'); rewrite(output);
if (ax=bx)and(ay=by) then write('0') else если начало и конец пути совпадают
if yk2>=yk1 then write('171717') если очередь пуста и мы не дошли
else write((res+1)*10); иначе ,если дошли
close(output);
end;
procedure solve;
var i,j:integer;
vx,vy:longint; текущая вершина
yk1old:integer;
begin
for i:=1 to n do
begin
xn[n+i]:=xk[i]; так как канал проходим с двух сторон, то
xk[n+i]:=xn[i]; добавляем в массив каналов перевернутые каналы
yn[n+i]:=yk[i]; и каналов становится максимум 1000 штук
yk[n+i]:=yn[i];
end;
n:=n*2; удваиваем количество каналов
for i:=1 to n do заполняем очередь номерами концов
каналов,
if(xn[i]=ax)and(yn[i]=ay) соединенных с начальной точкой
then
begin
inc(yk1); указатель конца очереди увеличиваем на 1
og[yk1]:=i; помещаем в очередь точку
used[i]:=false; отмечаем ее как использованную
end;
yk1old:=yk1; запоминаем указатель конца старой очереди, чтобы потом
сделать его началом новой очереди
while yk2<yk1 do а очередь не пустая делаем
begin
inc(yk2);
vx:=xk[og[yk2]];vy:=yk[og[yk2]]; берем первый элемент из очереди
if (vx=bx)and(vy=by) then если он совпадает с конечной точкой
begin
out; halt(0); выводим ответ и заканчиваем
end;
for i:=1 to n do иначе бежим по массиву точек и
заполняем новую очередь
if (xn[i]=vx)and(yn[i]=vy)and(used[i]) номерами точек связанных с текущей
then
begin
inc(yk1);og[yk1]:=i;used[i]:=false;
end;
if (yk1old=yk2) then если всю старую очередь просмотрели
begin inc(res);yk1old:=yk1;end; считаем волну и запоминаем указатель
end; конца новой очереди
end;
begin init; solve; out;end.
задачина2массивы
Задача 29 Поиск выхода из лабиринта (Обход в глубину)
Дан лабиринт прямоугольной формы в виде матрицы, состоящей из нулей и единичек. Известно местонахождение путника и выхода из лабиринта. Найти кратчайший путь выхода из лабиринта, его длину и количество путей.
Входной файл Input.txt содержит:
В первой строке два натуральных числа n и m (2<=n,m<=100) –размеры лабиринта. В последующих n строках по m нулей и единиц, разделенных пробелами – карту лабиринта. В третьей строке два числа номер строки и столбца, на пересечении которых находится путник. В четвертой строке два числа номер строки и столбца, на пересечении которых находится выход.
Выходной файл Output.txt содержит:
В первых n строках карту лабиринта с путем к выходу, отмеченный последовательными натуральными числами.
В следующей строке одно число – длина кратчайшего пути.
В следующей строке одно число- количество возможных путей.
И далее сам путь, записанный парами чисел – координатами клеток, входящих в путь.Каждая пара на новой строке.
Input.txt |
Output.txt |
3 3 0 0 0 0 1 0 0 0 0 1 1 3 3
|
1 2 3 0 1 4 0 0 5 4 2 1 1 1 2 1 3 2 3 3 3 |
Решение с использование обхода в глубину. Обход соседних клеток будем производить по часовой стрелке, начиная с верхней, которую обозначим 1. Остальные клетки будут иметь номера 2,3,4.. Если можно идти в соседнюю клетку, то идем и снова пытаемся сначала пойти в верхнюю клетку. Если пойти некуда, то возвращаемся на шаг назад и пытаемся сменить направление. Для хранения пути используем два двумерных массива. Первый puti хранит текущий путь, второй minputi хранит минимальный по длине путь.
program labirint;
const
nmax=50;mmax=50; максимальные размеры лабиринта
di:array[1..4] of integer=(-1,0,1,0); приращения индексов элементов
dj:array[1..4] of integer=(0,1,0,-1); массива задающего лабиринт
var a,c:array[0..nmax+1,0..mmax+1] of integer;
puti,minputi:array[1..2,1..nmax*mmax] of integer;
min,s,si,sj,vi,vj,i,j,n,m,kol:integer;
a – карта лабиринта
c – карта лабиринта с путем
puti – массив с найденным путем
minputi –массив с минимальным путем
min- длина минимального пути
s - номер шага
si,sj,vi,vj- индексы начальной и конечной клеток
kol - количество путей
procedure init;
begin
assign(input,'input.txt');reset(input);
read(n,m);
fillchar(a,sizeof(a),1); окаймляем лабиринт числом 257
for i:=1 to n do считываем лабиринт
for j:=1 to m do
read(a[i,j]);
read(si,sj,vi,vj);
kol:=0;min:=maxint;
fillchar(puti,sizeof(puti),0);
end;
procedure out;
begin
assign(output,'output.txt'); rewrite(output);
minputi[1,1]:=si; minputi[2,1]:=sj; вносим в путь начальную клетку
if c[vi,vj]=0 если в конечную клетку не дошли
then write(-1) значит пути нет
else
for i:=1 to n do выводим лабиринт с путем
begin
for j:=1 to m do
write(c[i,j]:3);
writeln;
end;
writeln(min-1); выводим длину пути
writeln(kol); и количество путей
for i:=1 to min do
writeln(minputi[1,i],' ',minputi[2,i]); выводим сам путь
end;
procedure step(i,j,s:integer); i,j - клетка,из которой делается шаг
s – номер следующей клетки в пути
var k:integer;
begin
if (i=vi)and(j=vj) если пришли в конечную точку
then
begin
inc(kol); считаем найденный путь
if min>a[vi,vj] сравниваем найденную длину
then пути с прежде найденной
begin
min:=a[vi,vj]; запоминаем новую длину пути
c:=a; запоминаем матрицу с путем
minputi:=puti; запоминаем минимальный путь
end;
end
else
for k:=1 to 4 do просматриваем 4 соседние клетки
begin
i1:= i+di[k];j1:= j+dj[k]; координаты соседней клетки
if a[i1,j1]=0 если шаг сделать можно
then
begin
puti[1,s]:=i1 ; puti[2,s]:=j1; заносим клетку в путь
a[i1,j1]:=s; записываем в клетку номер шага
step(i1,j1,s+1); рекурсивно вызываем процедуру step
a[i1,j1]:=0; возврат на один ход назад
puti[1,s]:=0 ; puti[2,s]:=0; удаляем клетку из пути
end;
end;
end;
begin
init;
a[si,sj]:=1; ставим 1 в начальную клетку
step(si,sj,2); вызываем процедуру step
out;
end.
задачина2массивы
Задача 30 Лабиринт (использование двух очередей)
Дан лабиринт прямоугольной формы в виде матрицы, состоящей из нулей и единичек. Известно местонахождение путника и выхода из лабиринта. Найти длину кратчайшего пути до выхода из лабиринта и изобразить сам путь в матрице последовательными натуральными числами.
Входной файл Input.txt содержит:
В первой строке два натуральных числа n и m (2<=n,m<=100) –размеры лабиринта. В последующих n строках по m нулей и единиц, разделенных пробелами – карту лабиринта. В третьей строке два числа номер строки и столбца, на пересечении которых находится путник. В четвертой строке два числа номер строки и столбца, на пересечении которых находится выход.
Выходной файл Output.txt содержит:
В первой строке одно число – длина кратчайшего пути.
В следующих n строках карту лабиринта с путем к выходу, отмеченный последовательными натуральными числами.
Input.txt |
Output.txt |
3 3 0 0 0 0 1 0 0 0 0 1 1 3 3 |
4 1 2 3 2 1 4 3 4 5
|
Этот способ решения не дает возможности посчитать количество кратчайших путей. Если в условии задачи требуется вывести путь перечисляя координаты пройденных точек, то потребуется завести еще один двумерный массив такого же размера как и данный. И в каждом элементе этого массива, соответствующего клетке, хранить два числа, координаты клетки из которой мы пришли.
Тогда путь можно вывести рекурсивно.
program labirint;
Const
nmax=100; mmax=100;
di:array[1..4]of integer =(-1,0,1,0); приращения по строкам
dj:array[1..4]of integer =(0,1,0,-1); приращения по столбцам
var n,m,i,j,t,res,kolold,kolnew,si,sj,vi,vj,i0,j0:integer;
a:array[1..nmax,1..mmax]of integer;
old,new:array[1..2,1..nmax]of integer; старая и новая очереди
begin
assign(input,'input.txt'); reset(input);
assign(output,'Output.txt'); rewrite(output);
Read(n,m);
Fillchar(a,sizeof(a),1); окаймляем лабиринт 1
for i:=1 to n do считываем лабиринт
for j:=1 to m do
read(a[i,j]);
read(si,sj,vi,vj); считываем координаты начальной
close(input); и конечной клеток
res:=0;
a[si,sj]:=1; отмечаем начальную точку
old[1,1]:=si; заносим ее в старую очередь
old[2,1]:=sj;
kolold:=1; количество элементов в старой
очереди
Repeat повторяем до тех пор пока новая
очередь не пуста
fillchar(new,sizeof(new),0); очищаем новую очередь
kolnew:=0; количество элементов в ней 0
inc(res); результат увеличиваем на 1
for i:=1 to kolold do бежим по старой очереди
begin
for t:=1 to 4 do
begin
i0:= old[1,i]+di[t];
j0:= old[2,i]+dj[t]; просматриваем 4 соседние клетки
if a[i0,j0]=0 если клетка проходима
then
begin
a[i0,j0]:=res; записываем в нее номер шага
inc(kolnew); увеличиваем кол-во элементов
new[1,kolnew]:=i0; заносим клетку в новую очередь
new[2,kolnew]:=j0;
if (i0=vi)and(j0=vj) если дошли до конечной клетки
then
begin
writeln(res); выводим результат
for i:=1 to n do
begin
for j:=1 to m do
write(a[i,j):4;
writeln;
end;
close(output);
halt(0); прерываем работу программы
end;
end;
end;
end;
kolold:=kolnew; новую очередь делаем старой и все
повторяем
old:=new;
until kolnew=0;
writeln('NO'); выводим NO, если выхода нет
close(output);
end;
end.
задачина2массивы
Задача 31 Потоп
Дана карта местности размером M на N клеток (M-строк, N-столбцов, 1<=M<=100, 1<=N<=100,). Для каждой клетки на карте указана ее высота Hij (1<=Hij<=100) над начальным уровнем воды. В клетке с координатами(1,1) на земле лежит ковчег.
С каждым часом уровень воды поднимается на одну единицу. Ковчег может в течении каждого часа либо оставаться на той клетке, где он находится, либо переплыть на одну из четырех соседних клеток, если уровень воды в обеих клетках в начале данного часа был как минимум на единицу выше уровня земли. Через сколько часов ковчег сможет достичь клетки с координатами(M,N) при самом оптимальном маршруте?
Входные данные:
В первой строке файла Input.txt содержатся два натуральных числа M и N.
Далее следуют M строк, каждая из которых содержит по N чисел, разделенных пробелами, которые задают карту местности.
Входные данные:
Файл Output.txt содержит единственное целое число –необходимое количество часов.
Пример
Input.txt |
Output.txt |
3 3 2 1 1 6 4 7 1 1 5 |
8 |
Решение с использованием одной очереди.
В этой задаче нельзя использовать две очереди, так как ковчег в процессе движения клонируется и некоторые клоны могут стоять на месте, ожидая, когда вода поднимется на нужную высоту и они смогут плыть дальше. Очередь будет одна, и в нее будем добавлять координаты новых клонов. Процесс закончится, когда один из клонов доплывет до нужной клетки.
Так как вода поднимается, то высота гор уменьшается
program potop;
Const
nmax=100;
mmax=100;
di:array[1..4]of integer =(-1,0,1,0); приращения по строкам
dj:array[1..4]of integer =(0,1,0,-1); приращения по столбцам
var si,sj,n,m,i,j,t,tek,kol,vi,vj,i0,j0,yn:integer;
a:array[0..nmax+1,0..mmax+1]of integer;
b:array[1..nmax,1..mmax]of integer;
ioch,joch:array[1..nmax]of integer; очередь для координат клеток
Procedure init;
begin
assign(input,'input.txt');
reset(input);
assign(output,'Output.txt');
rewrite(output);
Read(n,m);
for i:=0 to n+1 do окружаем карту высокими горами
for j:= 0 to m+1 do
a[i,j]:=20000;
si:=1;sj:=1; отмечаем расположение ковчега
vi:=n;vj:=m; координаты конечной точки
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
close(input);
end;
Procedure out;
begin
write(b[n,m]); вывод результата
close(output);
end;
Procedure Solve;
begin
tek:=a[1,1];
for i:=1 to n do
for j:=1 to m do
begin
b[i,j]:=maxint;
a[i,j]:=a[i,j]-tek-1; уменьшаем высоты клеток на высоту,
end; на которой находится ковчег
inc(tek); увеличиваем время на 1 час
b[1,1]:=tek;
ioch[1]:=si;
joch[1]:=sj;
kol:=1;
a[si,sj]:=20000; отмечаем клетку в которой были
while b[n,m]=maxint do пока не приплыли в конечный пункт
begin
inc(tek); увеличиваем время на 1 час
for i:=1 to kol do
begin
for t:=1 to 4 do просматриваем 4 соседние клетки
if a[ioch[i]+di[t],joch [i]+dj[t]]<0 если в клетку плыть можно
then
begin
i0:=ioch[i]+di[t];
j0:=joch[i]+dj[t];
if a[i0,j0]<>20000 и ковчег там еще не был
then
begin
a[i0,j0]:=20000; отмечаем клетку как пройденную
b[i0,j0]:=tek; заносим в матрицу b текущее время
inc(kol); считаем переход
ioch[kol]:=i0; запоминаем координаты клетки
joch[kol]:=j0;
end;
end;
end;
for i:=1 to n do поднимаем уровень воды на 1
for j:=1 to m do
dec(a[i,j]);
end;
end;
begin Init; Solve; Out; end.
задачина2массивы
Задача 32 Прыжки по матрице
Квадратная матрица размера N*N (1<=N<=29,N- нечетное) заполнена неотрицательными целыми числами из диапазона 0..40.Выяснить из каких клеток матрицы можно попасть в центральную клетку, если передвижения по матрице происходят по следующему правилу: если в клетке, например, число 5, то из этой клетки можно переместиться на 5 клеток или влево или вправо или вверх или вниз, оставаясь в пределах матрицы
Входные данные:
В первой строке файла Input.txt содержится натуральное число N – размер матрицы.
Далее следуют N строк, каждая из которых содержит по N чисел, разделенных пробелами, которые задают карту матрицу.
Входные данные:
Файл Output.txt содержит координаты клеток из которых можно попасть в центр, выведенных в столбец.
Пример
Input.txt |
Output.txt |
3 1 2 3 6 3 1 7 1 3 |
1 1 1 2 2 3 3 2 |
program putjvcentr;
Const nmax=100;
Var n,i,j,ik,jk,t,kolold,kolnew:integer;
a,b:array[1..nmax,1..nmax]of integer;
old,new:array[1..2,1..4*nmax]of integer;
log:boolean;
procedure Init;
begin
assign(Input,'Input.txt'); reset(Input);
assign(Output,'Output.txt'); Rewrite(Output);
Read(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
close(Input);
end;
Procedure Solve;
Var s:integer;
begin
ik:=(n div 2)+1; координаты центра в матрице
jk:=(n div 2)+1;
for i:=1 to n do пробегаем по всем клеткам матрицы и от
каждой
for j:=1 to n do запускаем волну, используя две очереди old
и new
begin
s:=1;
fillchar(b,sizeof(b),0);
b[i,j]:=1; в начальную ячейку заносим 1
old[1,1]:=i; заносим начальную ячейку в очередь old
old[2,1]:=j;
kolold:=1;
log:=false;
Repeat повторяем до тех пор пока новая
очередь не станет пустой
if log then break; если лошли до центра, то
переходим к следующей клетке
fillchar(new,sizeof(new),0); очищаем новую очередь
kolnew:=0;
t:=1;
while t<=kolold do бежим по старой очереди
begin
inc(s);
{right} if (old[2,t]+a[old[1,t],old[2,t]]<=n)and пытаемся прыгнуть вправо
(b[old[1,t],old[2,t]+a[old[1,t],old[2,t]]]=0)
then
begin
if (old[1,t]=ik)and(jk=old[2,t]+a[old[1,t],old[2,t]]) если дошли до центра
then
begin
writeln(i,' ',j);inc(t);log:=true;break выводим координаты
клетки и прерываем цикл
end;
if (a[old[1,t],old[2,t]+a[old[1,t],old[2,t]]]<>0) если из клетки можно прыгнуть
then
begin
inc(kolnew); прыгаем и добавляем
клетку в новую очередь
b[old[1,t],old[2,t]+a[old[1,t],old[2,t]]]:=s;
new[1,kolnew]:=old[1,t];
new[2,kolnew]:=old[2,t]+a[old[1,t],old[2,t]];
end;
end;
{down} if (old[1,t]+a[old[1,t],old[2,t]]<=n)and вниз
(b[old[1,t]+a[old[1,t],old[2,t]],old[2,t]]=0)
then
begin
if (old[1,t]+a[old[1,t],old[2,t]]=ik)and(old[2,t]=jk)
then
begin writeln(i,' ',j);inc(t);log:=true;break
end;
if (a[old[1,t]+a[old[1,t],old[2,t]],old[2,t]]<>0)
then
begin
inc(kolnew);
b[old[1,t]+a[old[1,t],old[2,t]],old[2,t]]:=s;
new[1,kolnew]:=old[1,t]+a[old[1,t],old[2,t]];
new[2,kolnew]:=old[2,t];
end;
end;
{left} if (old[2,t]-a[old[1,t],old[2,t]]>=1) and влево
(b[old[1,t],old[2,t]-a[old[1,t],old[2,t]]]=0)
then
begin
if (old[1,t]=ik)and(jk=old[2,t]-a[old[1,t],old[2,t]])
then
begin
writeln(i,' ',j);inc(t);log:=true;break
end;
if (a[old[1,t],old[2,t]-a[old[1,t],old[2,t]]]<>0)
then
begin
inc(kolnew);
b[old[1,t],old[2,t]-a[old[1,t],old[2,t]]]:=s;
new[1,kolnew]:=old[1,t];
new[2,kolnew]:=old[2,t]-a[old[1,t],old[2,t]];
end;
end;
{up} if (old[1,t]-a[old[1,t],old[2,t]]>=1)and вверх
(b[old[1,t]-a[old[1,t],old[2,t]],old[2,t]]=0)
then
begin
if (old[1,t]-a[old[1,t],old[2,t]]=ik)and(old[2,t]=jk)
then
begin
writeln(i,' ',j); inc(t);log:=true;break
end;
if (a[old[1,t]-a[old[1,t],old[2,t]],old[2,t]]<>0)
then
begin
inc(kolnew);
b[old[1,t]-a[old[1,t],old[2,t]],old[2,t]]:=s;
new[1,kolnew]:=old[1,t]-a[old[1,t],old[2,t]];
new[2,kolnew]:=old[2,t];
end;
end;
inc(t);
end;
kolold:=kolnew; делаем новую очередь старой
old:=new;
Until kolnew=0;
end;
end;
begin init; solve; end.
задачина2массивы
Задача 33 Черные и белые клетки
Возьмем квадратное окно размером N*N клеток и наложим на доску, так чтобы вершины квадратного окна совпали с узлами шахматной доски и стороны окна были параллельны сторонам квадратиков доски. Внутри этого окна будет находиться определенное количество черных клеток. Будем сдвигать окно вправо на 1 клетку. Количество черных квадратиков внутри окна будет меняться. Определить количество черных квадратиков, которое будет находиться внутри окна после T сдвигов.
Формат входного файла
Первая строка входного файла Input.txt содержит натуральные числа N – размеры окна (2≤N≤100) и K-количество черных клеток, находящихся внутри окна (0≤K<2000). В последующих K строках по 2 натуральных числа разделенных одним пробелом -номера строки и столбца, в которых находится черная клетка. Отсчет идет от левого верхнего угла. В последней строке одно натуральное число T –количество сдвигов (1≤T≤100).
Формат выходного файла
В выходном файле Output.txt одно натуральное число- количество черных клеток, находящихся внутри окна, после T сдвигов. .
Примеры
Input.txt |
Output.txt |
2 1 1 2 4 |
1
|
Первое решение это просто моделирование процесса движения окна. Второе решение чисто математическое. Надо выяснить закономерность и найти период появления черных клеток .
Первое решение:
Program ketki;
const nmax=110;
di:array [1..2] of shortint=(2,-1); приращение индексов координат клеток
dj:array [1..2] of shortint=(1,2);
var
a:array[-1..nmax+2,-1..nmax+2] of byte;
x,y:array[1..nmax*45] of byte;
res,t,r,koln,kols,i,j,n,k:longint;
procedure init;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
res:=0;
fillchar(a,sizeof(a),0);
read(n,k);
for i:=1 to k do
begin
read(x[i],y[i]);
a[x[i],y[i]]:=1;
end;
read(T); считываем время
if (n=2)and(k=0) частный случай размеры окна 2*2 и черных
клеток нет
then
begin
if T mod 5=0 then тогда, если время кратно 5
begin
write('0');halt(0) выводим 0
end
else
begin
write('1');halt иначе выводим 1
end;
end;
for i:=1 to n do перебираем клетки последних двух
столбцов окна
for j:=n-2 to n do
if a[i,j]=1 если клетка черная
then
begin
for r :=1 to 2 do пытаемся из нее пойти
if a[i+di[r],j+dj[r]]=0 если пойти можно
then a[i+di[r],j+dj[r]]:=1; ходим
end;
res:=k;
end;
procedure sdvig; сдвигает окно на клетку вправо
begin
kols:=0;
for i:=1 to n do считаем черные клетки в первом столбце
if a[i,1]=1 then inc(kols);
for j:=1 to n+1 do это сам сдвиг
for i:=-1 to n+2 do
a[i,j]:=a[i,j+1];
for i:=-1 to n+2 do a[i,n+2]:=0; очищаем столбец
for i:=1 to n do получаем черные клетки в последних двух
столбцах
for r :=1 to 2 do
if a[i,n]=1 then a[i+di[r],n+dj[r]]:=1;
koln:=0;
for i:=1 to n do считаем количество новых черных клеток
if a[i,n]=1 then inc(koln);
res:=res+koln-kols; пересчитываем результат
for i:=-1 to 0 do
for j:=-1 to n+2 do a[i,j]:=0; очищаем две полоски клеток над окном
for i:=n+1 to n+2 do очищаем две полоски клеток под окном
for j:=-1 to n+2 do a[i,j ]:=0;
end;
procedure out;
begin
write(res);
close(output);
end;
procedure solve;
var v:longint;
begin
for v:=1 to T do sdvig; T раз сдигаем окно
end;
begin init; solve; out;end.
задачина2массивы
