Ускова О.Ф., Горбенко О.Д. Олимпиадные задачи по программированию. Лучшие решения. Часть 3
Подождите немного. Документ загружается.
41
печатать. При этом следует учитывать, что общее количество
нажатий кнопок не должно превышать С и что полученное
решение не должно совпадать с найденным ранее. Для
реализации последней подзадачи все найденные уникальные
решения, общее количество которых не может превосходить 16,
будем запоминать, а каждое новое найденное решение будем
сравнивать с уже запомненными лишь в случае его
уникальности также запоминать и печатать.
Реализацию описанного алгоритма на Паскале легко
произвести с помощью такого типа данных, как множество,
состоящее не более чем из четырех элементов, каждый из
которых описывает одну группу лампочек. Так , например, если
для одного из вариантов нажатия кнопок мы определили
множество включенных ламп s, а из входных данных задачи
известны множества действительно включенных ламп – on –
выключенных – off, то данный вариант нажатий допустим, если
(on<=s) and (off<=[1..4]-s. Здесь множество [1..4]-s обозначает
выключенные при данной комбинации нажатий лампы . В случае
использования для проверки подобных условий массивов
решение задачи становиться более громоздким.
Program lamp;
type t=set of 1..4;
var
c,i1,i2,i3,i4,m,n,j,i,k:integer;
on,off,s:t;
contr:array [1..16] of t;
flag:boolean;
procedure ReadData;
begin
assign(input,'party.in');
reset(input);
42
readln(n,c);
on:=[];
read(j);
while j<>-1 do
begin
if j mod 3<>1 then
if odd(j) then on:=on+[1]
else on:=on+[2]
else
if odd(j) then on:=on+[3]
else on:=on+[4];
read(j)
end;
off:=[];
read(j);
while j<>-1 do
begin
if j mod 3<1 then
if odd(j) then off:=off+[1]
else off:=off+[2]
else
if odd(j) then off:=off+[3]
else off:=off+[4];
read(j)
end
end;
procedure Solve;
begin
assign(output,'party.out');
rewrite(output);
i:=0;
43
for i1:=0 to 1 do
for i2:=0 to 1 do
for i3:=0 to 1 do
for i4:=0 to 1 do
begin
k:=i1+i2+i3+i4;
if c>=k then
begin
s:=[1..4];
for m:=1 to 4 do
case m of
1: if odd(i1+i2) then s:=s-[1];
2: if odd(i1+i3) then s:=s-[2];
3: if odd(i1+i2+i4) then s:=s-[3];
4: if odd(i1+i3+i4) then s:=s-[4];
end;
if (on<=s) and (off<=[1..4]-s) then
begin
flag:=true;
for j:=1 to i do
if s=contr[j] then flag:=false;
if flag then
begin
inc(i); contr[i]:=s;
for j:=1 to n do
if j mod 3<>1 then
if odd(j) then
if 1 in s then write(1) else write(0)
else if 2 in s then write(1) else write(0)
else
if odd(j) then
44
if 3 in s then write(1) else write(0)
else if 4 in s then write(1) else write(0);
writeln;
end
end
end
end
end;
begin
ReadData;
Solve;
readln;
end.
Задача 5. " Язык TURBU "
Задача была предложена на областной
олимпиаде школьников в 2000 году и на
межвузовской студенческой олимпиаде в 2001
году. Автор решения – один из победителей
олимпиады, ныне магистрант 2 года обучения
Ромащенко Алексей Геннадьевич.
В языке TURBU алфавит содержит 5 букв: "#",
"$", "&","*","@".
Все используемые в языке слова -
пятибуквенные, поэтому в словаре языка TURBU
первое слово - #####, последнее - @@@@@. На
каждой странице словаря напечатано N слов.
Определить:
1. Количество страниц Р, необходимое для
размещения всех слов языка TURBU в словаре.
45
2. Номер Q страницы, на которой
располагается задаваемое слово а.
3. Слова, которыми начинается и
заканчивается страница, содержащая задаваемое
слово b языка TURBU.
Технические требования.
Входные данные. Входной текстовый файл
input.txt содержит: в первой строке - число N,
во второй - слово а, в третьей - слово b.
Выходные данные. Выходной текстовый файл
output.txt должен содержать:
в первой строке - число страниц Р;
во второй строке - номер Q страницы,
содержащей слово а;
в третьей строке - первое слово на
странице, содержащей слово b;
в четвертой строке - последнее слово на
странице, содержащей слово b.
Пример.
input.txt output.txt
N 35 P 90
a ####$ Q 1
b ###$$ #####
##$$@
Алгоритм решения задачи основан на
переводе чисел из пятеричной системы счисления
в дестичную и обратно. Каждое слова языка
Turbu представляет собой число в пятеричной
системе счисления, если принять :
46
# за 0
$ за 1
& за 2
* за 3
@ за 4
Полученое число в пятеричной системе
счисления переводится в соответствующее число
в десятичной системе счисления и уже с ним
производятся необходимые действия для
получения требуемых результатов. При
вычислниях в десятичной системе получается
число, соответствующее слову в языке TURBU.
Это число переводится в соответствующее число
в пятеричной системе и, следовательно,
известно написание искомого слова. В
языкеTURBU всего 3125 слов.
Program TURBU;{автор Ромащенко А.Г.}
Type num5=string;
var a,b:num5;
n:integer;
p:integer;
Function To5(x:integer):num5;
{перевод числа в слово из языка TURBU}
var s:num5;
r:string;
k:integer;
begin
s:='';
While x>0 do
begin
47
k:=x mod 5;
x:=x div 5;
case k of
0:r:='#';
1:r:='$';
2:r:='&';
3:r:='*';
4:r:='@';
else Writeln('Error!!!!!')
end;
s:=r+s;
end;
To5:=s;
end;
Procedure ReadFile;
{чтение исходных данных из файла Input.txt:
N - число слов на странице
a - первое слово
b - второе слово }
var s:string;
f:text;
begin
Assign(f,'input.txt');
Reset(f);
Readln(f,n);
Readln(f,a);
Readln(f,b);
Close(f);
end;
Function To10(x:string):integer;
48
{перевод слова языка TURBU в число от 0 до
3124
каждый символ в языке TURBU представляет
собой цифру
пятеричной системы счисления от 0 до 4}
var i,pos,st,r:integer;
begin
pos:=0; st:=1;
for i:=length(x) downto 1 do
begin
case x[i] of
'#':r:=0;
'$':r:=1;
'&':r:=2;
'*':r:=3;
'@':r:=4;
else Writeln('Error!!!!!')
end;
pos:=pos+r*st;
st:=st*5;
end;
To10:=pos;
end;
Procedure DoLen5(var s:string);
{дополнение полученного слова до принятого в
языке TURBU
(необходимо когда в начале слова стоит
один(или несколько)
нулевой символ `#`, в этом случае код слова
в десятичной
системе счисления будет меньше 625)}
49
begin
While length(s)<5 do s:='#'+s;
end;
Procedure WriteToFile;
{запись в файл Output.txt и расчет выходных
данных}
var ttt,q,p:integer;
s1,s2:num5;
f:text;
begin
Assign(f,'output.txt');
Rewrite(f);
{расчет необходимого количества страниц}
p:=Trunc(3125/n+0.999999);
Writeln(f,p);
{расчет номера страницы, на которой находиться
слово a}
q:=To10(a) div n + 1;
Writeln(f,q);
{получение первого слова на странице, на
которой находиться
слово b}
ttt:=(To10(b) div n)*n;
s1:=To5(ttt);
{добавление в начало полученного слова нулевых
символов языка TURBU}
DoLen5(s1);
Writeln(f,s1);
50
{получение последнего слова на странице, на
которой находиться
слово b}
ttt:=(To10(b) div n)*n+n-1;
if ttt>3124 then ttt:=3124;
s2:=To5(ttt);
{добавление в начало полученного слова
нулевых символов языка TURBU}
DoLen5(s2);
Writeln(f,s2);
Close(f);
end;
{основная программа}
BEGIN
ReadFile;
WriteToFile;
END.
Задача 6. " Московское время "
Задача была предложена на всемирной
студенческой олимпиаде по программированию
(ACM) в 1999 году. Автор решения – один из
участников четвертьфинального тура олимпиады ,
неоднократный победитель межвузовских
олимпиад, ныне магистрант 2 года обучения
факультета ПММ ВГУ Якубенко Андрей Павлович.
Задано время в определенном часовом поясе.
Требуется определить время, которое сейчас в
Москве(GMT +0300).