Waga czwórkowa
Limit pamięci: 32 MB
Smok Bajtazar zamierza zorganizować ucztę, na którą chce
zaprosić wielu gości.
Dla uświetnienia uczty, Bajtazar chce każdemu z gości podarować pewną ilość
złota.
Przy tym, każdy z gości powinien dostać tyle samo złota, aby nikt nie czuł się
pokrzywdzony.
Smok będzie odważał złoto dla kolejnych gości wagą szalkową.
Ma on do dyspozycji odważniki, których wagi w gramach są potęgami
czwórki.
Przy tym odważników każdego rodzaju ma dowolnie wiele.
Bajtazar będzie zawsze kładł złoto na lewej szalce wagi, a
odważniki na prawej lub na obu szalkach.
Bajtazar przy każdym ważeniu chce użyć najmniejszej możliwej liczby odważników.
Ponadto, aby gościom się nie nudziło, chce on każdemu z nich odważyć złoto w
inny sposób (tzn. używając innych odważników lub inaczej je rozdzielając
pomiędzy szalki).
Ponieważ smok nie umie za dobrze liczyć, polecił ci
napisanie programu, który obliczy ilu maksymalnie gości może
zaprosić, czyli wyznaczy maksymalną liczbę sposobów, na jakie
można odważyć gramów złota używając minimalnej liczby
odważników.
Jeśli dobrze się sprawisz, smok obsypie Cię złotem!
Zadanie
Napisz program który:
-
wczyta ze standardowego wejścia ile złota (w gramach)
Bajtazar zamierza dać każdemu z gości,
-
obliczy na ile sposobów można odważyć taką ilość złota za
pomocą minimalnej liczby odważników,
-
wypisze resztę z dzielenia wyniku przez na standardowe wyjście.
Wejście
W pierwszym i jedynym wierszu standardowego wejścia zapisania jest jedna
liczba całkowita , .
Jest to ilość złota (w gramach), jaką Bajtazar chce dać każdemu z gości.
Wyjście
Na standardowe wyjście należy wypisać jedną liczbę całkowitą -
resztę z dzielenia przez maksymalnej liczby gości, których Bajtazar
może zaprosić (czyli maksymalnej liczby sposobów, na jakie można odważyć
gramów złota używając minimalnej możliwej liczby odważników).
Przykład
Dla danych wejściowych:
166
poprawną odpowiedzią jest:
3
Do odważenia 166 gramów potrzeba użyć 7 odważników.
Ważenie można wykonać na następujące sposoby:
-
na lewej szalce złoto, na prawej odważniki 64, 64, 16, 16, 4, 1, 1,
-
na lewej szalce złoto i odważniki 64, 16, 16, na prawej odważniki 256, 4, 1, 1,
-
na lewej szalce złoto i odważniki 64, 16, 4, 4, 1, 1, na prawej
odważnik 256.
Autorzy zadania: Wojciech Rytter i Andrzej Walat.