PALMA junior
Úloha o ovocnej aleji

Autorské riešenie
[stiahni alej.py]                                       

• Počet riešiteľov: 30 / 30 = 100 %

• Úspešnosť riešenia: 4,88 / 6 = 81,33 %                   

Prvým krokom pri riešení tejto úlohy je určiť počty stromov jednotlivých druhov. Zo zadania vieme, že tieto počty sa môžu líšiť najviac o jedna. Keďže na vstupe dostaneme celkový počet stomov, musíme tento počet rozdeliť na súčet troch čísel, ktorých rozdiely sú najviac 1. Pri delení čísla trojkou máme zvyšok 0, 1 alebo 2. Teda počty budú buď všetky rovnaké, alebo z jedného druhu bude počet o 1 vyšší, alebo dva druhy stromov budú mať počet o jedna vyšší.

Avšak musíme uvažovať všetky možnosti. Ak chceme zasadiť jeden strom, máme tri možnosti, buď to bude jedna jabloň alebo jedna hruška alebo jedna slivka. Aby sme vedeli generovať rôzne možnosti, zoznam s jednotlivými počtami stromov zamiešame, čím zabezpečíme generovanie rôznych počtov.

Ďalej vytvoríme zoznam obsahujúci znaky reprezentujúce druhy stromov a zoznam, kde budeme pridávať stromy vo výslednej postupnosti.

Na zabezpečenie požiadavky, že vedľa seba nemôžu byť stromy rovnakého druhu sme si vytvorili pomocnú funkciu kam_zaradit. Táto funkcia pracuje s paramatrami strom (aktuálny, ktorý sme vybrali zo zásoby) a stromoradie. Funckia vráti pozíciu v stromoradi, kam sa má nový strom vložiť. Ak je alej prázdna, vráti 0, teda nový strom bude prvý. Ak je nový strom rovnaký, ako prvý strom v aleji, hľadá prvé miesto, kde sa nový strom líši od nasledujúceho stromu. Ak také miesto nájde, vráti jeho pozíciu. Ak nám funkcia vráti index -1, strom vrátime do zásoby a pokračujeme v cykle.

Pri generovaní postupnosti však tiež musíme myslieť na rôzne možnosti. Napríklad pre počet stromov dva máme možnosti JH, JS, HJ, HS, SJ, SH. Zamiešanie zásoby nám zabezpečí rôzne poradie stromov.

Výsledné riešenie môže vyzerať nasledovne:

import random

def kam_zaradit(strom, stromoradie):
   
    if len(stromoradie) == 0:
        return 0
    if strom != stromoradie[0]:
        return 0
    for idx in range(len(stromoradie) - 1):
        if stromoradie[idx] != strom != stromoradie[idx + 1]:
            return idx + 1
    if stromoradie[-1] != strom:
        return len(stromoradie)
    return -1


def generuj_plan_aleje(pocet):
    
    pocty = [pocet // 3] * 3
    if pocet % 3 == 1:
        pocty[0] = pocty[0] + 1
    elif pocet % 3 == 2:
        pocty[0] = pocty[0] + 1
        pocty[1] = pocty[1] + 1

    random.shuffle(pocty)
    zasoba = ['j'] * pocty[0] + ['h'] * pocty[1] + ['s'] * pocty[2]
    random.shuffle(zasoba)
    stromoradie = []

    while zasoba:
        strom = zasoba.pop()
        idx = kam_zaradit(strom, stromoradie)
        if idx == -1:
            zasoba.insert(0, strom)
        else:
            stromoradie.insert(idx, strom)
    return stromoradie

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

Riešenia úlohy hodnotím veľmi pozitívne. Mnoho z vás dotiahlo riešenie úlpohy až do úspešného konca. Niektorým chýbalo len málo do plného počtu bodov. Najčastejšia chyba bola, že ste generovanie počtov stromov jednotlivých druhov nebolo náhodné. Pre vstup 1, to bola automaticky jedna jabloň a ďalšie možnosti ste neuvažovali. Na základe tejto chyby sa vyskytli aj ďalšie, už pri generovaní samotnej postupnosti. Tiež sa vyskytol prístup, kde ste postupnosť vytvárali v poradí jabloň, hruška, slivka a dookola, čo samozrejme podmienku spĺňalo, ale nie je to jediná možná postupnosť.

Všetkým tímom blahoželám k získaným bodom a prajem veľa elánu do ďalších kôl a ročníkov. :)