Matematická olympiáda – kategorie P

Ř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.