Przyznam sie, ze sam bylem w stanie rozwiazac to zadanie tylko dla 12 kul.
Pomimo wszelakich kombinacji z tym moim algorytmem, dla wiekszej ilosci kul, moje rozwiazanie zawsze mialo TLE.
Wychodzilo na to, ze musi to byc optymalny algorytm.
Rozwiązanie (nie moje - opis algorytmu znaleziony w internecie, autor: Jack Wert [alg]),
ktore zostalo zaakceptowane spelnialo wymaganie,
że liczba ważen nie może przekroczyć liczby, zależnej od liczby kul,
wg poniższej tabelki:
+----------+---------------------------------------------+
| #wazenia | liczba kul <= _ |
+----------+---------------------------------------------+
| 2 | 3 |
| 3 | 12 = 3 + 3*3 |
| 4 | 39 = 3 + 3*3 + 3*3*3 |
| 5 | 120 = 3 + 3*3 + 3*3*3 + 3*3*3*3 |
| 6 | 363 = 3 + 3*3 + 3*3*3 + 3*3*3*3 + 3*3*3*3*3 |
| ... . ... |
+----------+---------------------------------------------+
Czyli:
dla 3 kul wystarcza 2 wazenia,
od 4 do 12 kul wystarcza max 3 wazenia,
od 13 do 39 kul wystarcza max 4 wazenia,
od 40 do 120 kul wystarczy max 5 wazen,
itd.