PALMA junior, súťaž pre mladých programátorov v Imagine

PALMA junior

Prírodovedecká fakulta Univerzity Pavla Jozefa Šafárika, Košice

 

Úloha o vstupných bránach

Autorské riešenie
[stiahni imp : py]

  • Počet riešiteľov: 2 / 4 = 50%

  • Úspešnosť riešenia:  7 / 8 = 88%

Úlohou bolo doplniť postupnosť číslic jednou (ak je dĺžka vstupu nepárna) alebo dvoma ciframi (ak je dĺžka vstupu párna) tak, aby súčet číslic na párnych pozíciách sa rovnal súčtu číslic na nepárnych pozíciách. Ak dopĺňame jednu cifru, riešenie neexistuje v prípade, že rozdiel je väčší ako 10 alebo súčet na párnych pozíciach je väčší ako súčet na nepárnych pozíciach. Ak dopĺňame dve cifry (zrejme jednu párnu a jednu nepárnu), tak v prípade, že rozdiel týchto súčtov je väčší ako 9, úloha tiež nemá riešenie. Naopak, ak tento rozdiel je menší ako 9, tak riešení je viacero. Na základe týchto jednoduchých úvah sa k správnemu riešeniu vieme dopracovať napríklad takýmto slovným algoritmom:

  1. Spočítaj súčet na párnych a nepárnych pozíciách a vypočítaj rozdiel týchto súčtov. Pokračuj krokom 2.
  2. Ak absolútna hodnota rozdielu je menšia ako 10 a zároveň dĺžka zadaného reťazca je najviac 7, pokračuj ďalej krokom 3. Inak pokračuj krokom 9.
  3. Ak počet cifier na vstupe je párny, pokračuj krokom 4. Inak pokračuj krokom 7.
  4. Ak je súčet na párnych pozíciach menší, doplň väčšou cifrou párnu pozíciu a pokračuj krokom 10.
  5. Ak je súčet na párnych pozíciach väčší, doplň väčšou cifrou nepárnu pozíciu a pokračuj krokom 10.
  6. Ak je absolútna hodnota rozdielu medzi súčtami menšia ako 9, cifry vieme doplniť viacerými spôsobmi. Vypíš oznam o viacerých riešeniach a pokračujme krokom 10.
  7. Počet cifier na vstupe je nepárny. Ak je súčet na párnych pozíciach menší, doplň poslednú cifru a pokračuj krokom 10.
  8. Počet cifier na vstupe je nepárny. Ak je súčet na párnych pozíciach väčší, pokračuj krokom 9.
  9. Vypíš, že úloha nemá riešenie a ukonč.
  10. Vypíš doplnený kód a ukonč.

Nasledujú možné riešenia v jazyku Imagine Logo a Python. Pripomeňme si, že v jazyku Imagine sa znaky reťazcov číslujú od hodnoty 1, v Pythone od 0.

;Imagine logo
viem dopln :kod
  urobTu "sucetParne 0
  urobTu "pocetOpakovani cpodiel (pocet :kod) 2
  opakuj :pocetOpakovani [
     urobTu "sucetParne :sucetParne + prvok (pocitadlo*2) :kod
  ]
  urobTu "sucetNeparne 0
  urobTu "pocetOpakovani (cpodiel (pocet :kod) 2) + (zvysok (pocet :kod) 2)
  opakuj :pocetOpakovani [
     urobTu "sucetNeparne :sucetNeparne + prvok pocitadlo*2-1 :kod
  ]
  urobTu "rozdiel :sucetParne - :sucetNeparne
  ak2 (zaroven abs(:rozdiel)<10 pocet :kod <= 7)
     [
       ak2 (zvysok pocet :kod 2 = 0)
       [
         ak2 (:rozdiel<0)
         [pis :kod * 100 - :rozdiel ]
         [pis :kod*100+:rozdiel*10 ]
         ak (abs(:rozdiel)<9) [pis "|Úloha má viac riešení, vypísali sme jedno z nich.|]
       ]
       [ ak2 (:rozdiel<=0)
         [(pis :kod*10+abs(:rozdiel))]
         [pis "|Úloha nemá riešenie|]
       ]
     ]
     [pis "|Úloha nemá riešenie|]
koniec

 

#Python
def    dopln(kod):
      '''
       Doplni "kod" jednou alebo dvoma ciframi tak, aby bol platnym kodom brany.
       :param kod: postupnost cisel ako kod brany
       :type kod: str
       :rtype: None
      '''
      sucetParne = 0
      for i in kod[1::2]:
         sucetParne +=int(i)
      sucetNeparne = 0
      for i in kod[::2]:
         sucetNeparne +=int(i)
   
      rozdiel = sucetParne-sucetNeparne
   
      if abs(rozdiel)<10 and len(kod)<=7:
         if len(kod)%2==0:
           if rozdiel<0:
             print(int(kod)*100-rozdiel)     
           else:       
             print(int(kod)*100+rozdiel*10)     
           if abs(rozdiel)<9:       
             print('Úloha má viac riešení, vypísali sme jedno z nich.')   
         else:
           if rozdiel<=0:
             print(int(kod)*10+abs(rozdiel))
           else:
             print('Úloha nemá riešenie')
      else:
        print('Úloha nemá riešenie')
   
    kod = input('Zadaj vstupný číselný kód: ')
    dopln(kod)
    input('stlac ENTER')

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

Úlohu riešili dva tímy, oba z nich v jazyku Python. Jeden z tímov úlohu vyriešil správne, navyše testoval aj prípady, v ktorom používateľ zadá nesprávne vstupy. V druhom tíme chýbalo ošetrenie hornej hranice dĺžky vstupného kódu a korektné dopĺňanie kódu v prípade nepárnej dĺžky vstupu.

© Univerzita Pavla Jozefa Šafárika v Košiciach, Prírodovedecká fakulta, Ústav informatiky

palmaj (zavinac) upjs.sk