PALMA junior
Úloha o kompase s viacerými vedľajšími smermi

Autorské riešenie
[stiahni py]

• Počet riešiteľov:  11 / 23 = 47.8 %

• Úspešnosť riešenia:  2.09 / 7 = 29.9 %

Pri riešení úlohy je najdôležitejšou vecou prísť na princíp, podľa ktorého sú vytvárané smery určitej dĺžky.

Pri označeniach smerov si môžeme všimnúť niekoľko skutočností:

1. označenia smerov s dĺžkou 2 a viac končia len písmenami z množiny {V, Z},

2. smery ktoré sú v blízkosti niektorej svetovej strany {S, V, J, Z} začínajú písmenom danej svetovej strany,

3. v označení ľubovoľného smeru sa nachádzajú nanajvýš 2 rôzne písmená, pričom nie sú spolu uvedené smery z množiny {S, J} a ani z množiny {V, Z}, a tiež sa označené nevyskytujú všetky možné kombinácie smerov,

4. označenie smerov v jednolivých kvadrantoch {SV, JV, JZ, SZ} je symetrické.

Podľa 4. postrehu nám stačí nájsť pravidlo označenia smeru len v jednom kvadrante, ktoré potom aplikujeme aj na ďalšie 3 zvyšné kvadranty. Poďme sa bližšie pozrieť na smery v kvadrante SV.

Podľa zadania sme smeru S priradili uhol 0° a smeru V uhol 90°. Uhol smeru SV vypočítame ako aritmetický priemer uhlov týchto smerov, t.j. uhol SV = (S + V) / 2 = (0° + 90°) / 2 = 45°. Analogicky uhly trojpísmenových smerov SSV a VSV vypočítame:

uhol SSV= (S + SV) / 2 = (S +  (S + V) / 2 ) / 2 = (3S + 1V) / 4

uhol VSV= (V + SV) / 2 = (V +  (S + V) / 2 ) / 2 = (1S + 3V) / 4

A uhly štvorpísmenových smerov SSSV, SVSV, VSSV a VVSV vypočítame:

uhol SSSV= (S + SSV) / 2 = (S +  (S + SV) / 2 ) / 2 = (S +  (S + (S + V) / 2) / 2 ) / 2 = (7S + 1V) / 8

uhol SVSV= (S + VSV) / 2 = (S +  (V + SV) / 2 ) / 2 = (S +  (V + (S + V) / 2) / 2 ) / 2 = (5S + 3V) / 8

uhol VSSV= (V + SSV) / 2 = (V +  (S + SV) / 2 ) / 2 = (V +  (S + (S + V) / 2) / 2 ) / 2 = (3S + 5V) / 8

uhol VVSV= (V + VSV) / 2 = (V +  (V + SV) / 2 ) / 2 = (V +  (V + (S + V) / 2) / 2 ) / 2 = (1S + 7V) / 8

Pri lepšom prezretí týchto 4 vzťahov pre uhly štvorpísmenových smerov, si môžeme všimnúť, že všetky smery končia písmenom V a tiež, že výsledný uhol smeru súvisí s binárnym kódovaním prvých troch znakov smeru, kde písmeno S nahradíme číslicou 1 a písmeno V číslicou 0:

uhol SSSV= (7S + 1V) / 8 ... 111₂ = 7

uhol SVSV= (5S + 3V) / 8 ... 101₂ = 5

uhol VSSV= (3S + 5V) / 8 ... 011₂ = 3

uhol VVSV= (1S + 7V) / 8 ... 001₂ = 1

Analogicky uhly 5-písmenových smerov vypočítame podľa vzťahov:

uhol SSSSV= (15S + 1V) / 16

uhol SSVSV= (13S + 3V) / 16

uhol SVSSV= (11S + 5V) / 16

uhol SVVSV= (9S + 7V) / 16

uhol VSSSV= (7S + 9V) / 16

uhol VSVSV= (5S + 11V) / 16

uhol VVSSV= (3S + 13V) / 16

uhol VVVSV= (1S + 15V) / 16

Vo všeobecnosti môžeme pre každý smer pozostávajúci z postupnosti N písmen 4 svetových strán {S, V, J, Z} vypočítať jeho uhol tak, že:

• prepíšeme zápis smeru do dvojkovej sústavy - písmeno z množiny {S, J} nahradíme číslicou 1 a  písmeno z množiny {V, Z} nahradíme číslicou 0,

• poslednú číslicu (nulu) v tomto dvojkovom zápise vynecháme čím dostaneme N-1 ciferné nepárne dvojkové číslo, ktoré označíme ako C,

• ak označíme A uhol jedného z uvedených hlavných smerov z množiny {S, J} a B uhol jedného z uvedených hlavných smerov z množiny {V, Z}, tak výsledný uhol vypočítame ako vážený aritmetický priemer: (A * C + B * (2^N-1 - C)) / 2^N-1

Výsledné riešenie celej úlohy zapísané v jazyku Python môže vyzerať nasledovne:

#python

uhol = {'S':0,'V':90,'J':180,'Z':270}
def spocitaj_uhol(retazec, strana1, strana0, horna, dolna):
    ''' Vypočíta uhol pre smer kompasu zadaný reťazcom, 2 svetové strany a 
        ich 2 uhly
    :param retazec: smer kompasu zadaný reťazcom
    :param strana1: hlavný smer = S alebo J
    :param strana0: hlavný smer = V alebo Z
    :param horna: uhol smeru S alebo J
    :param dolna: uhol smeru V alebo Z
    :return:
    '''
    retazec = retazec.replace(strana1,'1')
    retazec = retazec.replace(strana0,'0')
    retazec = retazec[:-1]
    citatel = int(retazec, 2)
    menovatel = 2**len(retazec)
    return dolna + (horna - dolna) * citatel / menovatel

def vypocet(retazec):
    ''' Vypočíta uhol pre smer kompasu zadaný textovým reťazcom
    :param retazec: smer kompasu
    :return: uhol pre zadaný smer kompasu
    '''
    if len(retazec) == 1:
        if retazec in uhol:
            return uhol[retazec]
        else:
            return 'chyba'
    elif 'S' in retazec and 'V' in retazec:
        return spocitaj_uhol(retazec, 'S', 'V', uhol['S'], uhol['V'])
    elif 'S' in retazec and 'Z' in retazec:
        return spocitaj_uhol(retazec, 'S', 'Z', uhol['S'] + 360, uhol['Z'])
    elif 'J' in retazec and 'V' in retazec:
        return spocitaj_uhol(retazec, 'J', 'V', uhol['J'], uhol['V'])
    elif 'J' in retazec and 'Z' in retazec:
        return spocitaj_uhol(retazec, 'J', 'Z', uhol['J'], uhol['Z'])
    else:
        return 'chyba'

print(vypocet(input()))

Táto súťažná úloha je zameraná na použitie stratégie riešenia problému hľadanie vzoru, na prácu s reťazcami, využitie dvojkového kódovania čísel,  použitie slovníka, precvičenie príkazu vetvenia a zložených podmienok a funkcii s parametrami a výstupmi.

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

Do riešenia tejto úlohy sa zapojili 11 tímov kategórie GURU. Plný počet bodov získali 2 tímy Šedá eminencia dodekahedrónov a Bubák v.7 Amavet, k čomu im gratulujeme.

V riešeniach sme zaregistrovali nasledovné chyby:

• nesprávny výpočet uhlov smerov - ani tých, ktoré boli vykreslené na ilustratívnom obrázku v zadaní úlohy,
• nedokončené riešenia obsahujúce chyby, napr. použitie indexu reťazca mimo platný rozsah,
• len riešenia pre dvojpísmenové, či trojpísmenové smery,
• pri výpočte smerov v kvadrante SZ použitie hodnoty 0° namiesto správnej hodnoty 360°,
• neošetrenie chybných vstupov,