daftacademy_2021

TASK

Masz za zadanie znaleźć ścieżkę w trójkącie zbudowanym z liczb od 0 do 9 (od górnego wierzchołka do podstawy trójkąta) z najmniejszą sumą liczb oraz sumę liczb w tej ścieżce. Wychodząc z dowolnej liczby w każdym wierszu trójkąta zawsze możesz pójść na dół, w lewo lub w prawo (poza ostatnim wierszem, którego cyfra kończy ścieżkę). Reprezentacje ścieżki uzyskujemy sklejając wszystkie cyfry ze ścieżki ze sobą.

Przykład trójkąta:

    9
   2 7
  2 9 1 
 2 6 8 6

Możliwe ścieżki:

9→7→1→6
9→7→1→8
9→7→9→8
9→7→9→6
9→2→9→8
9→2→9→6
9→2→2→6
9→2→2→2

Ścieżka z najmniejszą sumą: 9222 (sklejone 9→2→2→2)

Suma liczb z "najmniejszej" ścieżki: 15

Do tego zadania są 3 podpunkty. We wszystkich należy znaleźć ścieżkę (jako liczby) oraz podać sumę liczb ze ścieżki:

• very_easy.txt (1 pkt – 0.5 pkt za wskazanie sumy, 0.5 pkt za wskazanie ścieżki)
• easy.txt (3 pkt – 1 pkt za wskazanie sumy, 2 pkt za wskazanie ścieżki)
• medium.txt (6 pkt – 1 pkt za wskazanie sumy, 5 pkt za wskazanie ścieżki)

Trójkąt do każdego podpunktu zapisany jest w osobnym pliku o odpowiedniej nazwie. Pliki należy pobrać z tej strony. Uważaj na znaki końca linii w plikach. Odpowiedzi należy podać jako liczby bez opisywania rozwiązania.

Przykładowa odpowiedź na podpunkt:

a) Podaj najkrótszą ścieżkę trójkąta (przykładowy): 9222

b) Podaj sumę liczb z najkrótszej ścieżki trójkąta (przykładowy): 15

Odpowiedzi z innymi wartościami niż cyfry nie będą sprawdzane. Przykłady błędnych odpowiedzi:

9+2+2+2 9→2→2→2 9 2 2 2

9222 Rozwiązałem(am) metodą ...

W niektórych przypadkach istnieje więcej, niż jedna ścieżka minimalna. Wystarczy podać jedną lub więcej reprezentacji by uzyskać punkty, a jeśli uda się podać wszystkie, przewidziano extra punkty.

Format odpowiedzi dla podawania większej ilości ścieżek to oddzielone ścieżki znakami nowej linii np:
4638613421
4644532118
4644532118

Powodzenia 👍

1a Trójkąt very_easy suma liczb w najmniejszej ścieżce

18

1b Trójkąt very_easy najmniejsza ścieżka(i)

24471

2a Trójkąt easy suma liczb w najmniejszej ścieżce

44

2b Trójkąt easy najmniejsza ścieżka(i)

112833115217333

3a Trójkąt medium suma liczb w najmniejszej ścieżce

278

3b Trójkąt medium najmniejsza ścieżka(i)

54321171213632111411643331823271291141232141215224515221211315711241321233815221218172512222111431245111