Ускова О.Ф., Горбенко О.Д. Олимпиадные задачи по программированию. Лучшие решения. Часть 3
Подождите немного. Документ загружается.
31
Следующий вызов рекурсивной функции решает задачу
подсчета числа снимаемых бусинок для точки разрыва,
отвечающей числу k:
Число _ бусинок:=
Number(k+N,-1,’w’)+Number(k+N+1,+1,’w’ );
где функция Number устроена так :
function Number (j,move:integer; c:char):integer;
begin
if (j>i-N) and (j<i+N) and ((c='w') or (A[j]='w') or (A[j]=c))
then
if c='w' then
Number:=1+Number(j+move,move,A[j])
else Number:=1+Number(j+move,move,c)
else Number:=0;
end;
В случае «вырожденнных» бус Число _ бусинок
получиться равным 2*N-1, и этот случай следует рассмотреть
отдельно. Заметим, что условие ((c='w') or (A[j]='w') or (A[j]=c))
можно заменить на более лаконичное (А[j], c] <>[‘b’,’r’]).
В основной программе нам осталось лишь найти
максимальное число снимаемых бусинок при различных
значениях i. Этот алгоритм и реализован в программе,
приведенной в приложении.
program bysi;
const NMax=100;
var A:array[1..3*NMax] of char;
i,N:integer;
procedure ReadData;
var s:string;
begin
32
readln(S);
while S[length(S)]=' ' do dec(s[0]);
N:=length(S);
move(S[1],A[1],N);
move(S[1],A[N+1],N);
move(S[1],A[2*N+1],N);
end;
function Number(j,move:integer; c:char):integer;
begin
if (j>i-N) and (j<i+N) and ((c='w') or (A[j]='w') or (A[j]=c))
then
if c='w' then
Number:=1+Number(j+move,move,A[j])
else Number:=1+Number(j+move,move,c)
else Number:=0;
end;
procedure Solve;
var k,Num,Max:integer;
begin
Max:=0;
for i:=N+1 to 2*n do
begin
Num:=Number(i,-1,'w')+Number(i+1,+1,'w');
if Num>Max then
begin
Max:=Num;
k:=i-N;
end;
if Max>=N then break;
33
end;
if Max>N then Max:=N;
if k<>N
then writeln(Max,'between',k,'and',k+1)
else writeln(Max,'between',N,'and', 1);
end;
begin
assign(input,'bys.dat');
assign(output,'bys.sol');
reset(input); rewrite(output);
while not seekeof do
begin
ReadData;
Solve;
end;
close(input);
close(output);
end.
Задача 3. " Прямоугольники".
Постановка задачи. N прямоугольников различных цветов
располагаются на белом листе бумаги , имеющем размеры А см в
ширину и В см в длину. Стороны прямоугольников параллельны
краям листа , а сами прямоугольники не выходят за пределы
листа . В результате образуются различные одноцветные
фигуры . Если два прямоугольника одного цвета имеют хотя бы
одну общую точку, то они являются частями одной фигуры .
Задача состоит в вычислении площади каждой из видимых
одноцветных фигур для каждого цвета . А и В – четные
положительные целые числа , не превосходящие 30.
Начало системы координат находиться в центре листа , а
оси параллельны краям листа . Наборы данных для нескольких
34
тестов записаны во входном файле и именем rectang.dat
следующим образом :
А ,В, N находятся в первой строке каждого набора данных и
разделены пробелом . В каждой из следующих строк находятся :
- целочисленные координаты точки , в которую помещена
левая нижняя вершина прямоугольника;
- за ними следуют целочисленные координаты точки , в
которую помещена правая верхняя вершина прямоугольника;
- затем следует цвет прямоугольника, заданный целым
числом от 1 до 64; белый цвет представлен числом 1.
Порядок строк соответствует порядку, в котором
прямоугольники размещались на листе от первого до
последнего .
Напишите программу, которая:
1. Читает очередной набор данных из входного файла с
именем rectang.dat
2. Вычисляет площадь каждой из одноцветных фигур.
3. Записывает в выходной файл с именем rectang.sol цвет и
площадь каждой одноцветной фигуры . Эти результаты
должны записываться в порядке возрастания номера
цвета .
Пример
входные данные выходные данные
20 12 5 1 177
-7 –5 –3 –1 4 2 39
-3 –3 5 3 2 4 23
-4 –2 –2 2 4 12 1
2 –2 3 –1 12
3 1 7 5 1
program pramoygolniki;
var Bar: array [-15..15,-15..15] of byte;
35
A,B,N: integer;
procedure ReadData;
var k,i,j,i1,i2,j2,c,j1:integer;
begin
read(A,B,N);
A:=A div 2;
B:=B div 2;
FillChar(Bar,sizeof(Bar),1);
for k:=1 to N do
begin
read(i1,j1,i2,j2,c);
for i:=i1 to i2-1 do
for j:=j1 to j2-1 do
Bar[i,j]:=c;
end;
end;
var Fig: array[0..30*30] of Record
squ,col:integer;
end;
Cnt,S,c:integer;
Procedure Rec(i,j:integer);
begin
if (i>=-A) and (i<A) and (j>=-B) and (j<B) and (Bar[i,j]=c) then
begin
inc(S); Bar[i,j]:=0;
Rec(i-1,j-1); Rec(i-1,j); Rec(i-1,j+1);
Rec(i,j-1); rec(i,j+1);
Rec(i+1,j-1); rec(i+1,j); Rec(i+1,j+1);
end;
36
end;
procedure Solve;
var i,j:integer;
begin
Cnt:=0;
for i:=-A to A-1 do
for j:=-B to B-1 do
if Bar[i,j]>0 then
begin
inc(Cnt);
c:=Bar[i,j];
S:=0;
Rec(i,j);
Fig[Cnt].col:=c;
Fig[Cnt].squ:=S;
end;
for j:=1 to Cnt do
for i:=Cnt-1 Downto j do
if Fig[i+1].col<Fig[i].col then
begin
Fig[0]:=Fig[i];
Fig[i]:=Fig[i+1];
Fig[i+1]:=Fig[0];
end;
end;
procedure Print;
var i: integer;
begin
37
for i:=1 to Cnt do
writeln(Fig[i].col, ' ', Fig[i].squ);
writeln;
end;
begin
assign(input,'rectang.dat');
assign(output,'rectang.sol');
reset(input); rewrite(output);
while not seekeof do
begin
ReadData;
Solve;
Print;
end;
close(input); close(output);
end.
Задача 4. "Лампы для праздника".
Для освещения заключительного вечера имеется N
цветных ламп, пронумерованных от 1 до N. Четыре кнопки
позволяют управлять лампами следующим образом :
кнопка 1 – изменяет состояние всех ламп: те , что были
включены , становятся выключенными, те , что были выключены
включаются ,
кнопка 2 – изменяет состояние всех ламп, имеющих не четные
номера,
кнопка 3 - изменяет состояние всех ламп, имеющих четные
номера,
38
кнопка 4 - изменяет состояние всех ламп, имеющих номера,
вычисляемые по формуле : 3k+1 (где k>=0), то есть 1,4,7,…
Имеется счетчик С, который учитывает (хранит)
суммарное число нажатий всех кнопок.
В начале вечера все лампы были включены , а счетчик С
был установлен в нуль.
Постановка задачи. Заданы значения счетчика С и информация
о конечном состоянии некоторых ламп. Напишите программу
для определения всех различных возможных конечных
(окончательных ) конфигураций N ламп, чтобы каждая
конфигурация соответствовала заданной информации.
Формат входных данных: Файл, имеющий имя PARTY.IN,
содержит четыре строки , задающих количество ламп N,
Конечное значение счетчика С нажатых клавиш и состояние
некоторых ламп в окончательной конфигурации.
В первой строке содержится число N, во второй строке –
конечное значение счетчика С . третья строка содержит список
номеров ламп, о которых известно, что в конечной
конфигурации они включены . Номера ламп в строке отделены
друг от друга одним пробелом , и список заканчивается числом –
1. Четвертая строка содержит список номеров ламп, о которых
известно, что в окончательной конфигурации они выключены .
Номера ламп в строке отделены друг от друга одним пробелом ,
и список заканчивается числом – 1.
Формат выходных данных: Файл PARTY.OUT должен
содержать все возможные различные окончательные
конфигурации (без повторений) всех ламп. Каждая возможная
конфигурация должна быть записана в отдельной строке.
Конфигурации могут быть перечислены в произвольном
порядке.
39
Каждая строка содержит N символов, где первый символ
представляет состояние лампы номер 1, а последний символ
представляет состояние лампы номер N. 0 (ноль) означает, что
лампа выключена, а 1 (единица ) означает, что лампа включена.
Пример
входные данные выходные данные
10 0000000000
1 0110110110
-1 0101010101
7 -1
Здесь видно, что имеются три возможные различные конечные
конфигурации:
- все лампы включены ;
- или лампы 1,4,7,10 выключены , а лампы 2,3,5,6,8,9
включены ;
- или лампы 1,3,5,7,9 выключены , а лампы 2,4,6,8,10
включены .
Ограничения
Параметры N и С ограничены : 10<=N<=100, 1<=C<=1000
Количество ламп, о которых известно, что в конечной
конфигурации они включены , меньше или равно 2.
Количество ламп, о которых известно, что в конечной
конфигурации они выключены , меньше или равно 2.
Гарантируется , что существует хотя бы одна конечная
конфигурация.
РЕШЕНИЕ
Суммарное количество нажатий различных клавиш
настолько велико, что сразу же становиться очевидной
невозможность перебора всех различных вариантов нажатия
40
кнопок. Однако легко показать, что этого делать и не нужно.
Заметим, что если любая из кнопок была нажата дважды, то
состояние всех ламп не изменится . Поэтому следует учитывать
лишь кнопки , которые были нажаты нечетное количество раз.
Общее число ламп также не влияет на сложность решения
задачи , так как на самом деле все лампы можно разделить на
четыре непересекающиеся группы : лампы с нечетными
номерами, не попадающими во множество ламп с номерами
{3k+1, k>=0}, аналогичные лампы с четными номерами, лампы
с нечетными номерами из множества {3k+1, k>=0} и лампы с
четными номерами из этого же множества. Все лампы каждой
из перечисленных групп одинаково реагируют на нажатие
любых кнопок. А именно: лампы из первой группы меняют свое
состояние лишь при нажатии кнопок 1 и 2, второй группы –
кнопок 1 и 3, третьей группы – кнопок 1,2 и 4, четвертой группы
– 1,3, и 4. Причем в конечном состоянии лампочка окажется
выключенной, если сумма нажатий влияющих на нее кнопок
окажется нечетной, и включенной в противном случае .
Опираясь на сказанное выше, будем решать задачу
следующим образом . Переберем все возможные
принципиальные варианты количества нажатий каждой из
кнопок. Так как для каждой кнопки в отдельности таких
вариантов всего 2: четное число нажатий, которое можно
обозначить 0, и нечетное – 1, то общее количество вариантов
равно 16. Для каждой из 16 комбинаций нажатий кнопок
определим, какие группы лампочек в этом случае окажутся
включенными, а какие выключенными. Полученную
информацию сравним с входными данными, и если
противоречия нет, то данные состояния лампочек можно