od jacube » 28. 6. 2006 17:25
Zadani druheho prikladu bylo:
System verejneho osvetleni
N lamp, az 50000 ocislovanych lamp
M prepinacu - i-ty prepinac ovlada urcity interval lamp (tzn. treba 10-ty prepinac ovlada lampu 1020 az lampu 3145)
- prepinac funguje takto - svitici lampu vypne, nesvitici zapne. a ma jen jednu akci - stisk. jednu lampu muze ovladat neomezene mnoho prepinacu.
na vstupu dostanete N a M a vsechny intervaly prislusne k prepinacum.
ma se urcit, jestli lze osvitit cele mesto nejakou kombinaci stisknuti prepinacu (efektivni program) a pokud mozno i jak se toho osviceni dosahne (tzn. jake prepinace se maji stisknout).
A jak jsem to resil:
Vytvoril jsem matici A - v radcich lampy a ve sloupcich prepinace. Cili rozmer MxN. Matice obsahuje pouze 1 a 0. Pokud i-tou lapmu ovlivnuje j-ty prepinac, priradim a_ij = 1. Jinak a_ij = 0. Potom jsem zjistil, ze pokud matici vynasobim zprava usporadanou m-tici obsahujici 0 a 1, vyjadri to kombinaci prepinacu, ktere sviti a ktere ne. Vse pocitam nad Z_2. Pokud tento soucin bude roven (1, 1, ..., 1), budou vsechny lampy svitit. Takze staci vyresit soustavu danou matici A s pravou stranou (1, 1, ..., 1) nad Z_2 a dostanu presne kombinaci prepinacu, ktere mam stisknout. Pokud soustava nema reseni, nelze mesto osvitit.
Musel jsem to docela dlouho vysvetlovat, ale nakonec rekl, ze je to v poradku.
Jinak prvni priklad jsem mel destruktivni sjednoceni dvou BVS a na ustnim quicksort a udelal jsem to.
Zadani druheho prikladu bylo:
System verejneho osvetleni
N lamp, az 50000 ocislovanych lamp
M prepinacu - i-ty prepinac ovlada urcity interval lamp (tzn. treba 10-ty prepinac ovlada lampu 1020 az lampu 3145)
- prepinac funguje takto - svitici lampu vypne, nesvitici zapne. a ma jen jednu akci - stisk. jednu lampu muze ovladat neomezene mnoho prepinacu.
na vstupu dostanete N a M a vsechny intervaly prislusne k prepinacum.
ma se urcit, jestli lze osvitit cele mesto nejakou kombinaci stisknuti prepinacu (efektivni program) a pokud mozno i jak se toho osviceni dosahne (tzn. jake prepinace se maji stisknout).
A jak jsem to resil:
Vytvoril jsem matici A - v radcich lampy a ve sloupcich prepinace. Cili rozmer MxN. Matice obsahuje pouze 1 a 0. Pokud i-tou lapmu ovlivnuje j-ty prepinac, priradim a_ij = 1. Jinak a_ij = 0. Potom jsem zjistil, ze pokud matici vynasobim zprava usporadanou m-tici obsahujici 0 a 1, vyjadri to kombinaci prepinacu, ktere sviti a ktere ne. Vse pocitam nad Z_2. Pokud tento soucin bude roven (1, 1, ..., 1), budou vsechny lampy svitit. Takze staci vyresit soustavu danou matici A s pravou stranou (1, 1, ..., 1) nad Z_2 a dostanu presne kombinaci prepinacu, ktere mam stisknout. Pokud soustava nema reseni, nelze mesto osvitit.
Musel jsem to docela dlouho vysvetlovat, ale nakonec rekl, ze je to v poradku.
Jinak prvni priklad jsem mel destruktivni sjednoceni dvou BVS a na ustnim quicksort a udelal jsem to.