- •Тема: Перебор вариантов. Задача 1. Замечательные числа
- •Задача 2. Острова
- •Задача 3 Клавиатура
- •Задача 4 . Вырубка деревьев
- •Краткие методические рекомендации по решению задачи
- •Оценка решения
- •Формат входных данных
- •Формат выходных данных
- •Золото племени абба
- •Работа с большими числами
- •Сортировка и поиск
- •2. Домашнее задание.
- •Метод перебора вариантов, отсечения перебора
- •Сумма двух чисел
- •Элементы вычислительной геометрии
- •4. Две окружности
- •Эффективные структуры данных
- •5. Поиск прямоугольников (Время: 0,5 сек. Память: 16 Мб Сложность: 34%)
- •Тема 1: «Работа с длинными числами»
- •Тема 2: Алгоритмы поиска и сортировки
- •Тема 3: Аналитическая геометрия
- •Тема 4: Перебор вариантов
- •Тема 5: Строки. Элементы лексического и синтаксического разобра
- •Задача 3. "Функция"
- •Ограничения
- •Площади покрытия антенны
- •Площадь покрытия решение
- •Элементы лексического и синтаксического разбора Шифровка
- •Шифровка Решение
- •Сортировка и поиск Независимые судьи
- •Независимые судьи Решение
- •Сувениры
- •Сувениры Решение
- •Треугольник Условие задачи
- •Треугольник Решение
- •Олимпиадные задачи по информатике
- •Задача 1. «Код да Винчи»
- •Задача 3 «Буквы»
- •Задача 4 «Соревнования»
- •Задача «Красивая последовательность»
- •Тема: Задача на динамическое программирование
- •Динамическое программирование Задача: Черепашка
- •Решение
- •Тема: Работа с большими числами
- •Тема: Сортировка и выбор
- •Задача. Подземная дорога (поиск в ширину)
- •Формат входных данных
- •Задача rebus
- •Задача “Эчпочмаки”
- •Задача “Ниточка”
- •Задача “Обезьяны”
- •Задача Интересное число
Эффективные структуры данных
5. Поиск прямоугольников (Время: 0,5 сек. Память: 16 Мб Сложность: 34%)
На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.
Получившуюся ситуацию записали в таблицу чисел (каждой клетке поля соответствует клетка таблицы). Если клетка поля не закрыта прямоугольником, то в соответствующую клетку таблицы записали число 0. Если же клетка закрыта одним или несколькими прямоугольниками, то в соответствующую клетку таблицы записали число, соответствующее номеру самого верхнего прямоугольника, закрывающего эту клетку.
Требуется написать программу, которая определит положение и размеры прямоугольников. Гарантируется, что во входных данных содержится информация, которой достаточно для однозначного определения размеров прямоугольников.
Входные данные
Входной файл INPUT.TXT содержит в первой строке целые числа N, M, K (1<=N<=200, 1<=M<=200, 1<=K<=255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.
Выходные данные
В
ыходной
файл OUTPUT.TXT должен содержать K строк.
Каждая строка должна описывать
соответствующий ее номеру прямоугольник
четырьмя числами X1 Y1 X2 Y2 (X1 и Y1 должны
описывать координаты левого нижнего
угла прямоугольника, а X2 и Y2 — координаты
правого верхнего угла). Числа должны
разделяться пробелом.
Начало координат расположено в левом нижнем углу таблицы. Таким образом, координаты левого нижнего угла поля — (0,0), правого верхнего — (M,N).
Пример
№ |
INPUT.TXT |
OUTPUT.TXT |
1 |
4 5 2 0 2 2 2 2 0 2 2 2 2 1 1 2 2 2 1 1 0 0 0 |
0 0 2 2 1 1 5 4 |
Решение:
var
xmin,xmax,ymin,ymax:array[1..255] of integer;
x,y,w,h,k,i,j:integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(h,w,k);
for i:=1 to k do
begin
xmin[i]:=w;
ymin[i]:=h;
end;
for y:=h downto 1 do
for x:=1 to w do
begin
read(j);
if j>0 then
begin
if x<xmin[j] then xmin[j]:=x;
if y<ymin[j] then ymin[j]:=y;
if x>xmax[j] then xmax[j]:=x;
if y>ymax[j] then ymax[j]:=y;
end;
end;
for i:=1 to k do writeln(xmin[i]-1,' ',ymin[i]-1,' ',xmax[i],' ',ymax[i]);
close(output);
end.
Тема 1: «Работа с длинными числами»
«Число души»
Саша увлеклась нумерологией. Из книги по нумерологии Саша узнала, что любую цифровую последовательность можно свести к «числу души».
Алгоритм получения числа души следующий: рассмотрим любое натуральное число и найдем сумму его цифр, потом сумму цифр полученного числа и так далее, пока не получим одноцифровое число или числа 11, 12, 21.
Саша увлеклась и рассчитывала «число души» для любой цифровой последовательности, которая ей встречалась.
Напишите программу, которая облегчит Саше жизнь и рассчитает за нее «число души». Необходимо написать программу, которая для заданного N (N<10100) находит его «число души».
Входные данные: INPUT.TXT одна строка, которая содержит натуральное число N.
Выходные данные: OUTPUT.TXT одна строка, которая содержит число души числа N.
INPUT.TXT |
OUTPUT.TXT |
247 |
4 |
program chislo;
var
f: text; // файловая переменная
s, sum_n: word; {переменные для хранения итоговой суммы и промежуточной суммы}
ch:char; // переменная для хранения, считанного символа
begin
assign(f, 'input.txt'); //связываем файл и файловую переменную
reset(f); //открываем файл для чтения
s:=0; // обнуляем переменную, которая хранит сумму цифр
{Так как число может быть слишком большим осуществляем посимвольное считывание из файла. Полученный символ преобразуем в цифру}
while not eof(f) do // Считываем, пока не достигнем конца файла
begin
read(f, ch); // чтение из файла
s:=s+(ord(ch)-ord('0')); //подчет суммы цифр, заданного числа.
end;
close(f); // закрываем файл
while s>=10 do {пока сумма цифр не станет однозначным числом, считаем сумму цифр}
begin
if (s=11) or (s=12) or (s=21) then break;{если получено число 11, 12 или 21, то прервать работу цикла}
sum_n:=0; // обнуление промежуточной переменной для хранения суммы
{блок нахождения суммы цифр числа}
while s<>0 do
begin
sum_n:=sum_n+s mod 10;
s:=s div 10;
end;
s:=sum_n;// новое значение суммы цифр числа
end;
assign(f,'OUTPUT.txt');// связываем файл с файловой переменной
rewrite(f);// открываем файл для записи
writeln(f,s);//записываем результат
close(f);// закрываем файл
end.
