BEBRO konkurso užduotys 2018

 

Kas su kuo apsistos?

Taškai: 9

Merginų informatikos klubo narės planuoja savaitgalio išvyką. Jos apsistos nakvynės namuose ir gyvens dideliuose šešių lovų kambariuose . Kas su kuo apsistos viename kambaryje?
Kiekviena mergina savo pageidavimus užrašo kortelėje:

  1. nurodydama merginas, su kuriomis būtinai nori gyventi (+), ir
  2. nurodydama merginas, su kuriomis jokiu būdu nenori apsistoti (–).

Klubo prezidentė nori, kad visos liktų patenkintos išvyka. Taigi jos tikslas – taip išskirstyti merginas į kambarius, kad išsipildytų visų norai.

Padėkite jai! Paskirkite merginai kambarį nutempdami kortelę su jos pageidavimais į vieną iš stačiakampių.

Paaiškinimas

Norėdama patenkinti visų merginų pageidavimus, klubo prezidentė svarsto, kaip suskirstyti merginas į kambarius, atsižvelgus į jų norus. Toks suskirstymas ir yra uždavinio sprendinys.

Kaip rasti sprendinį? Paprasčiausias būdas – perrinkinėti visus galimus variantus (suskirstymus į kambarius) ir turint konkretų suskirstymą, patikrinti, ar jis tenkina duotus ribojimus, kitaip tariant, ar yra sprendinys.

Ribojimų tenkinimo uždaviniai, panašūs į šį, gerai žinomi informatikoje. Sprendžiant tokius uždavinius, reikia paskirstyti resursus, jei norima išvengti konfliktų. Pavyzdžiui, kai reikia sudaryti lėktuvų kilimo ir tūpimo grafiką, t.y. naudojimosi tais pačiais pakilimo ir tūpimo takais, grafiką. Tokius uždavinius galima efektyviai išspręsti, taikant tinkamus algoritmus.

Raktiniai žodžiai: ribojimas, ribojimų tenkinimas, konfliktas.

Atsakymas

Norint patenkinti visus pageidavimus reikia koncentruotis į teigiamus pageidavimus. Imk bet kurią nenutemptą kortelę ir:

1. Jei kambarys tuščias,

  1. nutempk kortelę į tą tuščią kambarį;
  2. kitu atveju, nutempk kortelę į tą kambarį, kuriame ši mergina nėra nepageidaujamų sąraše (jei tokio kambario nėra – uždavinio sprendinys NEEGZISTUOJA).

2. Nutempk visų merginų, esančių  sąraše, korteles į tą patį kambarį. Jei nenutemptų kortelių neliko, uždavinys išspręstas.

3. Grįžk į pirmą žingsnį.

Taikant aprašytą procedūrą, gausime kambarių paskirstymą. Kito galimo sprendinio nėra: Alina turi būti kartu su Lile, bet Alina (taip pat ir Lilė) negali kartu apsistoti nei su Ema, nei su Zina. Taigi Alina negali būti kartu su Mija, kuri privalo apsistoti kartu su Ema ir Zina. Laura turi gyventi atskirame kambaryje, nes ji negali būti kartu nei su Lile (todėl negali ir su Alina), nei su Ema (todėl negali apsistoti nei su Mija, nei su Zina).

Kaip matote, šiam uždaviniui, sprendinys egzistuoja. Tačiau bendru atveju sprendinio gali ir nebūti. Pavyzdžiui, jei Alina norėtų būtinai gyventi kartu su Lile, bet Lilė jokiu būdu nenorėtų gyventi su Alina, atsidurtume aklavietėje,ir sprendinio nebūtų.

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39