[Blue15]

1. https://pl.spoj.com/problems/FR_08_07/ - chyba nie do końca rozumiem treść zadania. Rozrysowałem sobie to drzewo i wg mnie na wyjściu powinniśmy otrzymać: 1 1 1. W treści zadania oczekują: 1 1 5, a przecież na 3 poziomie mogą być maksymalnie 4 elementy...
2. https://pl.spoj.com/problems/AL_29_03/ - o ile wiem jak zsumować elementy w drzewie, to zastanawia mnie to: "Jak widać możemy wyróżnić trzy różne kształty drzew.". Jak mogę "rozpoznać" kształ drzewa?
Zerknie ktoś? :)
#programowanie #algorytmy

[ZdeformowanyKreciRyj]

@Blue15: w tym drugim dla każdej ozdoby przemapuj sobie ceny każdej bombki na liczby od 1 do liczby bombek w tej ozdobie. Wtedy dwie różne ozdoby maja różne kształty jeżeli mają inną liczbę bombek albo kolejność dokładania bombek jest inna. Potem wystarczy wybrać najtańsze z każdego kształtu

[j.....0]

@Blue15: co do 1) to nazwanie tego zbiorem to według mnie nadużycie (w zbiorze elementy nie mogą się powtarzać). Natomiast zadanie mówi jasno określ ile liczb z podanego zbioru znajduje się na i-tym poziomie drzewa binarnego a nie ilość liczb z drzewa binarnego znajdujących się w zbiorze. Czyli wynik to oficjalnie 4 (# # # # 7 6 # 6 6 6).

[Blue15]

@jaksa0: nadal nie ogarniam. Na i-tym, czyli na np. 3 znajduje się jedna liczba.

[j.....0]

@Blue15: dwie - 6 i 7, z czego 6 występuje w "zbiorze" 4 razy

[Blue15]

@ZdeformowanyKreciRyj: ale przecież w każdej ozdobie jest ta sama liczba bombek

[ZdeformowanyKreciRyj]

@Blue15: to co wyżej napisałem jednak nie do końca działa xd

[Blue15]

@jaksa0: ja widzę, że na 3 poziomie znajduje się jedna liczba, co robię źle? ( ͡° ʖ̯ ͡°)

[ZdeformowanyKreciRyj]

@Blue15: bo źle rozumiesz zadanie. Nie masz konstruować bst z tych podanych liczb tylko zakładasz, że masz pełne bst z wierzchołkami ponumerowanymi tak jak na obrazku i masz ospowiedziec na pytanie ile w danym multizbiorze jest takich liczb, że na ntym poziomie drzewa, któryś wierzchołek dostał taki numer

[Blue15]

@ZdeformowanyKreciRyj: to wszystko wyjaśnia. Często ciężko zrozumieć mi treść tych zadań, są pisane tak mocno formalnie.

[ZdeformowanyKreciRyj]

@Blue15: inna sprawa, że na spoju zadania często są po prostu słabo napisane. Jak nie przeszkadza Ci angielski to polecam np codeforces