PALMA junior
Úloha o obsluhe strojov

Autorské riešenie
[stiahni py]                                       

• Počet riešiteľov: 15 / 37 = 41  %                       

• Úspešnosť riešenia:  4.5 / 7 = 64 %                   

Jedno z možných riešení tejto úlohy spočívalo v nájdení stratégie, ktorá kombinuje postupnú návštevu strojov podľa dĺžky výdrže batérií na týchto strojoch a tiež vzdialenosť obsluhy od týchto strojov. Jedno z takýchto riešení by sme mohli popísať nasledovne:

• vypočítame priority strojov ako hodnoty rozdielu medzi vzdialenosťou strojov a dĺžkou výdrže batérie na týchto strojoch (napríklad, ak dĺžka výdrže piatich strojov je postupne 5,4,3,2 a 7 minút a moje vzdialenosti od strojov sú postupne 1,2,3,4 a 5 minút, tak priority týchto strojov predstavujú rozdiel týchto dvoch zoznamov, a teda priority -4, -2, 0, 2, -2)
• nájdeme stroj (jeho index) s najväčšou prioritou (najväčšiu prioritu s hodnotou 2 má v predchádzajúcom príklade stroj vo vzdialenosti 4),
• vymeníme batériu na stroji s najväčšou prioritou,
• zaznamenám čas, ktorý uplynul, kým sa obsluha dostala k stroju a vymenila batériu (v príklade ubehlo 4+1 minúta),
• aktualizujem časy vybitia jednotlivých batérii (čas vybitia vymenenej batérie nastavím na maximum, od ostatných strojov odpočítam uplynutý čas (teda nové aktuálne časy vybitia sú 0, -1, -2, 2, 2, pričom -2 znamená, že batérie je už 2 minúty vybitá),
• aktualizujem moje nové vzdialenosti od ostatných strojov (ak som vymenil batériu na štvrtom stroji, nové vzdialenosti budú 3,2,1,0,1,
• ak som vymenil už tretiu batérie, vrátim sa na stanicu a zoberiem ďalšie tri nabité batérie.

Nasleduje možný zdrojový kód v jazyku Python:

# Python
def instrukcie(casy_vybitia_strojov, pocet_vymien):

  uplynuty_cas = 0
  prikazy = []
  pocet_strojov = len(casy_vybitia_strojov)
  aktualne_casy_vybitia = casy_vybitia_strojov.copy()
  for pocitadlo in range(pocet_vymien):
    print("**** CISLO NABIJANIA: ******", pocitadlo)
    if (pocitadlo % 3 == 0):
        # start alebo navrat do nabijacej stanice
        vzdialenost_strojov = list(range(1, pocet_strojov+1))
        prikazy.append(0)
    
    # vypocet priorít strojov
    priorita_stroja = list()
    for i in range(pocet_strojov):
      rozdiel = vzdialenost_strojov[i] - aktualne_casy_vybitia[i]
      priorita_stroja.append(rozdiel)
    print("Priority strojov:", priorita_stroja)

    # nájdenie stroja s najväčšou prioritou
    maximum = priorita_stroja[0]
    pozicia_maximum = 0
    for i in range(pocet_strojov):
      if (priorita_stroja[i]>maximum):
        maximum = priorita_stroja[i]
        pozicia_maximum = i 
    pozicia_vybraneho_stroja = pozicia_maximum + 1
    print("Vymeň batérie na stroji: ", pozicia_vybraneho_stroja)
  
    
    prikazy.append(pozicia_vybraneho_stroja)
    # počítam čas, ktorý uplynul, kým sa obsluha dostala k stroju a 
    # vybila sa batéria + 1 minúta na výmenu
    
    uplynuty_cas = vzdialenost_strojov[pozicia_vybraneho_stroja-1] + 1
  
    print("Uplynul čas: ", uplynuty_cas)
    # počítam čas, o koľko sa znížila výdrž batérií, ale na vymenenom 
    # stroji ostane plná batéria
        
    for i in range(pocet_strojov):
      aktualne_casy_vybitia[i] = aktualne_casy_vybitia[i] - uplynuty_cas


    aktualne_casy_vybitia[pozicia_vybraneho_stroja-1] = \
      casy_vybitia_strojov[pozicia_vybraneho_stroja-1]

    print("Aktualne_casy_vybitia: ",aktualne_casy_vybitia)
    
    
    for i in range(pocet_strojov):
      vzdialenost_strojov[i] = abs(i + 1 - pozicia_vybraneho_stroja)

    print("Nové vzdialenosti strojov: ",vzdialenost_strojov)
  return prikazy

casy_vybitia_strojov = [5,4,3,2,7]
pocet_vymien = 6

prikazy = instrukcie(casy_vybitia_strojov, pocet_vymien)
print(prikazy)

Vaše zaujímavé riešenia a najčastejšie chyby

Úlohu riešilo 15 tímov. 4 tímy našli jednu z možných stratégií pre výmenu batérií. Výborne spracovali aj počítanie času, určovanie priorít a výpis príkazov. Niektoré ďalšie tímy spracovali stratégiu, ale len pre jeden návrat na stanicu, teda len pre výmenu 3 batérii. V zadaní bolo uvedené, že obsluha tieto batérie mení postupne na všetkých strojoch. Ďalšie riešenia menili batérie náhodne bez stratégie, alebo hľadaním najkratšej cesty bez použitia časov vybitia batérií. Jeden tím to vyriešil aj pre viacero návratov na stanicu, ale po každom návrate sa menili batérie len na tých istých strojoch.