INFOMAN брой 6
{ This is the input data:
10
22
4 -1
1 7 -1
ПРАЗНИЧНО ОСВЕТЛЕНИЕ
--------------------
(10-та международна олимпиада по информатика - ден I)
Дадени са N лампи. Лампите се управляват от четири бутона:
* бутон 1 - когато този бутон се натисне, всички лампи сменят състоянието
си - тези, които светят угасват, а тези, които са били угаснали, светват
* бутон 2 - сменя състоянието на лампите с нечетни номера
* бутон 3 - сменя състоянието на лампите с четни номера
* бутон 4 - сменя състоянието на лампите с които имат номера от вида 3k+1
т.е. (1,4,7,...)
Разполагаме с брояч C, който регистрира броя натискания на бутоните, но не
регистрирва точно кои бутони се натискат. Първоначално всички лампи светят.
Дадена е стойността на C и информация за състоянието на някои от лампите.Да
се напише програма, която намира всички различни възможни състояния на N-те
лампи, които са възможни при дадената конфигурация, т.е.могат да се получат
от началната чрез точно C натискания на бутон (с C операции).
Първият ред на файла съдържа броя на лампите N (0 < N < 100). На втория ред
на входния файл е числото C (0 < C < 10000). На третия ред са изброени лам-
пите, които светят, разделени с интервали, последвани от '-1'. На четвъртия
ред са изброени лампите, които са загасени. Списъкът завършва също с '-1'.
Да се изведат всички възможни конфигурации, всяка на отделен ред. Редът на
извеждане няма значение.
За да решим задачата, много е важно за забележим, че прилагането на коя
да е операция четен брой пъти води не води до промяна на конфигурацията. Съ-
що е важно да се забележи, че редът на прилагане на операциите няма никакво
значение.Ето защо всички възможни конфигурации, които трябва да проверим са
само 16 и те са резултатите от всичките възможни комбинации от операции: [],
[1], [2], [3], [4], [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [1,2,3], [1,2,
4], [1,3,4], [2,3,4] и [1,2,3,4]. За да проверим дали една комбинация от 16-
те може да се получи, първо трябва да проверим дали лампите, за които е да-
дено, че светят са светнати и дали лампите, за които е дадено, че не светят
са угасени. Ако C е четно число, трябва да се проверяват само комбинациите,
получени с четен брой натискания на бутони - [], [1,2], [1,3], [1,4], [2,3],
[2,4], [3,4], и [1,2,3,4], а когато е нечетно - операциите, които могат да
се получат с нечетен брой натискания на бутон. Освен това трябва да се про-
вери дали C не е по-малко от броя операции. Всичките тези проверки се извър-
шват от фунцкията Possible, която връща дали при натискане на комбинацията
от бутони (o1,o2,o3 и o4) от началното състояние (само светнати лампи) с C
натискания на бутон може да получи възможно крайно състояние.Алгоритъмът из-
ползва тази функция за да провери 16-те възможни комбинации от бутони и от-
печатва в резултатния файл само възможните комбинации. Трябва да отбележим,
че някои състояния могат да се получат по няколко начина (например операции-
те [1] и [2,3] са еквивалентни). Понеже всички еквивалентни операции обаче
са от различна четност (брой натискания на бутоните по модул 2), няма нужда
да се проверява дали състоянията, които отпечатваме са различни. Повторения
не могат да се получат.Казано най-накратко при четно C програмата проверява
четните комбинации от бутони, а при нечетно нечетните и отпечатва валидните
получени състояния, като внимава те да не се получават с повече от C опера-
ции.
}
CONST InFileName = 'PARTY.PAS';
OutFileName = '';
MaxN = 200;
TYPE TLamps = array[1..MaxN] of char; {състояние на лампите - 0, 1 или ?}
VAR L: TLamps; {Съдържа задължителните изисквания за някои от лампите}
N,C: integer;
Procedure ReadData; {Прочита входните данни - N, C и L[1..N]}
Var F: Text;
v: integer;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,N); Readln(F,C);
FillChar(L,SizeOf(L),'?');
repeat
Read(F,v);
if v = -1 then Break;
L[v]:='1';
until false;
ReadLn(F);
repeat
Read(F,v);
if v = -1 then break;
L[v]:='0';
until false;
Close(F);
End;
Procedure Solve; {Намира и отпечатва виски възможни състояния}
Var R: TLamps;
o1,o2,o3,o4: boolean;
OutF: Text;
Procedure Change(bit:integer); {Променя състоянието на лампата с номер bit}
Begin
if R[bit] = '0' then R[bit]:= '1'
else R[bit]:= '0';
End;
Procedure Op1; {Извършва над R операция 1}
Var i: integer;
Begin
for i:= 1 to N do Change(i);
End;
Procedure Op2; {Извършва над R операция 2}
Var i: integer;
Begin
for i:= 1 to N do
if odd(i) then Change(i);
End;
Procedure Op3; {Извършва над R операция 3}
Var i: integer;
Begin
for i:= 1 to N do
if not odd(i) then Change(i);
End;
Procedure Op4; {Извършва над R операция 4}
Var i: integer;
Begin
for i:= 1 to N do
if i mod 3 = 1 then Change(i);
End;
Procedure Print; {Отпечатва R[1..N] в резултатния файл}
Var i: integer;
Begin
For i:= 1 to N do
Write(outf,R[i]);
Writeln(outf);
End;
Function Possible: boolean; {Връща дали комбинацията, получаваща се от
комбинацията бутони o1,o2,o3,o4 е възможна при дадените C и L[1..N]}
Var i,NewC: integer;
Begin
Possible:=false;
NewC:= C - byte(o1) - byte(o2) - byte(o3) - byte(o4);
if (NewC < 0) or (odd(NewC)) then Exit;
FillChar(R,N,'1');
if o1 then Op1;
if o2 then Op2;
if o3 then Op3;
if o4 then Op4;
{Проверяваме дали R[1..N] отговаря на зададените изисквания в L[1..N]}
for i:= 1 to N do
if (L[i]='0') or (L[i]='1') then
if L[i] <> R[i] then Exit;
Possible:=true;
End;
Begin
Assign(OutF,OutFileName); Rewrite(OutF);
{Изпробват се състоянията, получаващи се от 16-те бутонни комбинации}
for o1:= false to true do
for o2:= false to true do
for o3:= false to true do
for o4:= false to true do
if Possible then Print;
WriteLn(OutF);
Close(OutF);
End;
BEGIN
ReadData;
Solve;
END.