Ceremonija (2014)
Taškai: 6
Norint tinkamai suorganizuoti šventinę ceremoniją, reikia visus veiksmus atlikti tam tikra tvarka.
Pateiktoje schemoje pavaizduoti ceremonijos veiksmai. Rodyklės rodo, kokia tvarka jie turi būti atlikti. Pavyzdžiui, Būgnų mušimas arba Ilgos kalbos sakymas galimas tik po to, kai bus atlikta Sudainuoti dainą.
Suplanuokite ceremoniją! Tempdami langelius dešinėje esančioje lentelėje teisingai išdėliokite ceremonijos veiksmus. Viršuje turi būti pirmas ceremonijos veiksmas.
Sprendžiant šią užduotį atliekame topologinį grafo išrikiavimą. Tai suteikia galimybę suprasti grafo vaizdavimą, taip pat pirmenybės ryšius, išreikštus grafo briaunomis.
Galimas sprendimas:
Vienas iš būdų surikiuoti yra vykdyti tokį algoritmą.
Kol kiti veiksmai nėra atlikti, suraskite ir atlikite tokį veiksmą, į kurį rodantys visi veiksmai jau būtų atlikti. Pavyzdžiui, pradžioje „Sudainuoti dainą“ yra vienintelis veiksmas, į kurį nėra rodančių kitų veiksmų, taigi galime jį atlikti.
Toliau kiti du veiksmai „Ilga kalba“ ir „Būgnų mušimas“ turi rodykles tik iš „Sudainuoti dainą“, taigi kuomet „Sudainuoti dainą“ yra atlikta, tuomet šiuos du veiksmus bus taip pat galima atlikti. Pavyzdžiui, šiuo atveju pirmiausia pasirinksime „Būgnų mušimą“.
„Šokis“, į kurį nurodo „Būgnų mušimas“, dar negali būti atliktas, nes į jį yra nukreipta rodyklė iš „Ilga kalba“, taigi pasirenkame atlikti „Ilgą kalbą“.
Dabar galime atlikti „Šokį“, lygiai taip pat galime „Paskelbti nugalėtoją“. Pasirenkame „Šokį“.
Dabar galime „Sugroti trimitu“ arba „Paskelbti nugalėtoją“. Pasirenkame „Sugroti trimitu“.
Dabar galime paleisti „Fejerverkus“ arba „Paskelbti nugalėtoją“. Pasirenkame „Paskelbti nugalėtoją“.
Dabar jau nebeturime galimybės pasirinkti, kaip atlikti paskutinius du veiksmus. Atliksime „Fejerverkus“ o tik tada „Padėkosime visiems“.
Yra ir kitų galimų sprendimų, priklausančių nuo pasirinkto veiksmo pirmenybės.
Kitas galimas sprendimas:
