Řešení úloh ústředního kola (2. soutěžní den) 45. ročníku
druhý soutěžní den 26.4.1996
P-III-4
Budeme nejprve řešit trochu obecnější úlohu: předpokládejme, že
na začátku nemusí být všechny lampy vypnuté. Stav lamp si budeme
pamatovat v poli l, kde l[i]=true, pokud je i-tá lampa zapnutá
a l[i]=false, jestliže je vypnutá. Řešením této úlohy budeme
rozumět takovou podmnožinu přepínačů, že pokud je všechny
přepneme, všechny lampy budou zapnuté. Pokud N=0, řešením úlohy
je zřejmě prázdná množina. Nechť tedy N>0. Mohou nastat dva
případy:
l[1]=false
Jestliže žádný interval nezačíná lampou 1, úloha zjevně nemá
řešení. V opačném případě najdeme nejkratší interval, který
začíná lampou 1 (nechť jeho konec je b). Změníme všechna l[i]
z tohoto intervalu na opačná a všem intervalům, které začínají
lampou 1, změníme začátek na b+1 (intervaly, které se tím stanou
prázdnými, už dále neuvažujeme). Dostáváme tak novou úlohu pro
lampy 2,3,...,N, která má řešení právě tehdy, má-li řešení
původní úloha.
Důkaz: Nechť pozměněná úloha má řešení R. Potom když přepneme
lampy z původní úlohy přepínači z R, budou svítit jen lampy
s čísly většími než b. Nechť R obsahuje k intervalů, kterým jsme
začátek změnili z 1 na b+1. Nechť R' vznikne z R tak, že těmto
intervalům změníme začátek zpět na 1. Jestliže je k liché, každou
lampu z intervalu <1,b> jsme oproti řešení R přepnuli ještě lichý
počet krát, tedy zůstane zapnutá. V tomto případě je tedy R'
řešením naší původní úlohy. Pokud je k sudé, lampy z intervalu
<1,b> zůstanou vypnuté a proto k R' je třeba ještě přidat
interval <1,b>.
Naopak, nechť naše původní úloha má řešení R. Počet intervalů
z R, které obsahují lampu 1, je jistě lichý. Když všem těmto
intervalům změníme začátek na b+1 a vyhodíme intervaly nulové
délky, dostaneme řešení změněné úlohy.
l[1]=true
Protože lampa 1 už svítí, není třeba, aby se dala nějakým
přepínačem přepnout. Jestliže neexistuje interval, který začíná
lampou 1, úloha má řešení právě tehdy, má-li řešení úloha pro
lampy 2,3,...,N a stejnou množinu intervalů. Pokud existuje
interval, který začíná lampou 1, opět z nich vezmeme nejkratší,
změníme začátky intervalů stejně jako v předchozím případě, ale
neměníme hodnoty pole l. Takováto pozměněná úloha má opět řešení
právě tehdy, když má řešení původní úloha.
Důkaz je obdobný jako v případě, kdy l[1]=true (uvědomte si však,
že počet intervalů, které obsahují lampu 1, musí být tentokrát
samozřejmě sudý).
Naším úkolem však není nalézt řešení, ale pouze zjistit, zda
nějaké řešení existuje. Je proto třeba na začátku nastavit
všechny prvky pole l na false a podle uvedených úvah postupovat
od první lampy až do poslední, přičemž modifikujeme pole
l a začátky příslušných intervalů. Dostáváme tak algoritmus
s časovou složitostí O(NM) a paměťovou O(N+M).
program Lampy;
const maxn=100; maxm=100;
var l:array[1..maxn] of boolean;
{l[i]=true ... i-tá lampa svítí}
a,b:array[1..maxm] of integer; {intervaly}
n,m:integer;
uloh,u:integer;
i,j,min,mini:integer;
ok:boolean;
fin,fout:text;
begin
assign(fin,'lampy.in'); reset(fin);
assign(fout,'lampy.out'); rewrite(fout);
readln(fin,uloh);
for u:=1 to uloh do begin
readln(fin,n,m); {načtení vstupu}
for i:=1 to m do
readln(fin,a[i],b[i]);
for i:=1 to n do {"vypnutí" lamp}
l[i]:=false;
i:=1; {cyklus přes všechny lampy}
ok:=true;
repeat
min:=n+1; mini:=0;
{hledáme nejkratší interval se začátkem v i}
for j:=1 to m do
if (a[j]=i) and (b[j]<min) then begin
mini:=j; min:=b[j];
end;
if mini=0 then begin
{nenašel se interval se začátkem v i}
if not l[i] then ok:=false
end
else begin
if not l[i] then {je-li třeba, přepneme lampy}
for j:=i to min do
l[j]:= not l[j];
j:=1; {změníme začátky intervalů z i na min+1}
while j<=m do begin
if a[j]=i then a[j]:=min+1;
if a[j]>b[j] then begin
{prázdný interval - vyhodíme z pole}
a[j]:=a[m];
b[j]:=b[m];
dec(m);
end
else inc(j);
end;
end;
inc(i);
until not ok or (i>n);
if ok then {výpis výsledku}
writeln(fout,'Lze')
else
writeln(fout,'Nelze');
end;
close(fin); close(fout);
end.
P-III-5
Je důležité uvědomit si, že můžeme jít jen směrem na východ nebo
na jih. Abychom se dostali z křižovatky (1,1) na křižovatku
(M,N), musíme přejít o M-1 ulic na jih a o N-1 ulic na východ. Je
jedno, v jakém pořadí střídáme směry, počet křižovatek, kterými
projdeme, je vždy M+N-1.
Počet různých cest také spočítáme jednoduše. Označme a[i,j] počet
různých cest z (1,1) do (i,j). Pokud se křižovatka (i,j)
opravuje, položíme a[i,j]=0. Na libovolnou křižovatku ležící na
východozápadní ulici číslo 1 (t.j. na nejsevernější ulici) se
můžeme dostat nejvýše jedním způsobem, a to tak, že půjdeme stále
na východ. Jestliže se však opravuje vozovka někde mezi touto
křižovatkou a křižovatkou (1,1), nemůžeme se tam dostat vůbec.
Totéž platí i pro severojižní ulici číslo 1.
Uvažujme nyní křižovatku (i,j), kde i,j>1 a tato křižovatka se
neopravuje. Na tuto křižovatku můžeme přijít buď z křižovatky
(i-1,j), nebo z křižovatky (i,j-1). Jestliže tedy známe hodnoty
a[i-1,j] a a[i,j-1], pak a[i,j]=a[i-1,j]+a[i,j-1]. Na základě
této úvahy můžeme sestrojit algoritmus, který bude postupně po
řádcích vyplňovat pole a. Nakonec budeme mít v a[M,N] počet
různých cest z (1,1) do (M,N). Je-li tento počet roven 0, žádná
taková cesta neexistuje.
Vzhledem k tomu, že musíme vyplnit celou tabulku velikosti MxN
a pro výpočet hodnoty každého políčka vykonáme konstantní počet
operací, časová složitost algoritmu je O(MN).
program Manhatan;
const max=100;
var a:array[1..max,1..max] of integer; {počet možných cest}
o:array[1..max,1..max] of boolean; {kde se opravuje}
m,n,k:integer;
i,j,x,y:integer;
uloh,u:integer;
fin,fout:text;
begin
assign(fin,'manhatan.in'); reset(fin);
assign(fout,'manhatan.out'); rewrite(fout);
readln(fin,uloh);
for u:=1 to uloh do begin
readln(fin,m,n); {načtení vstupu}
readln(fin,k);
for i:=1 to m do
for j:=1 to n do
o[i,j]:=false;
for i:=1 to k do begin
readln(fin,y,x);
o[y,x]:=true;
end;
a[1,1]:=1; {vypočítá okraje pole a}
for i:=2 to m do
if o[i,1] then a[i,1]:=0
else a[i,1]:=a[i-1,1];
for i:=2 to n do
if o[1,i] then a[1,i]:=0
else a[1,i]:=a[1,i-1];
for i:=2 to m do {vypočítá vnitřek pole a}
for j:=2 to n do begin
if o[i,j] then a[i,j]:=0
else a[i,j]:=a[i-1,j]+a[i,j-1];
end;
if a[m,n]=0 then {výpis výsledku}
writeln(fout,'Cesta neexistuje')
else
writeln(fout,a[m,n],' ',m+n-1);
end;
close(fin);
close(fout);
end.