Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Банк олимпиадных заданий.docx
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
375 Кб
Скачать
☆

Эффективные структуры данных

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.