Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024

2020-2022 2023 Regulations Schedule RODO info

Problem description


Waga czwórkowa
(waga-czworkowa)
Limit pamięci: 32 MB
Limit czasu: 1.00 s

W Januszeksie znowu potrzebują Twojej pomocy! Tym razem firma będzie sprzedawać węgiel (no co? na wszystkim da się zarobić!). Węgiel przed sprzedażą należy oczywiście zważyć. Tutaj pojawia się niestety problem. Firma na stanie ma jedynie prymitywną wagę szalkową, której trzeba będzie użyć do ważenia węgla. To jeszcze nie wszystko: firma dysponuje jedynie odważnikami o masach całkowitych (januszogramów) będących całkowitymi potęgami czwórki (1, 4, 16, ), po jednej sztuce na każdą potęgę czwórki. To powoduje, że nie każdą całkowitą masę węgla można odważyć.

Na przykład: worek o masie 11 januszogramów można zważyć, jeśli położy się go na lewej szalce wagi, wraz z odważnikami o masach 1 i 4. Na prawej szalce wystarczy tylko położyć odważnik o masie 16 i sprawa załatwiona. Gorzej jednak, jeśli przyszłoby na przykład odważyć węgiel o masie 7 januszogramów. Jest to niestety niemożliwe.

Prezes firmy, Pan Janusz, jest właśnie na spotkaniu z Bardzo Ważnym Klientem, który rozważa kupno co najmniej A i co najwyżej B kilogramów węgla. Pan Janusz chciałby wiedzieć ile różnych ofert będzie mógł przedstawić klientowi. Pomóż mu!

Napisz program, który: wczyta liczby A oraz B, wyznaczy ile jest całkowitych mas węgla z przedziału [A;B], które będzie można odważyć na wadze i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajdują się dwie liczby naturalne A oraz B, oddzielone pojedynczym odstępem, określające koniec przedziału mas węgla, którymi zainteresowany jest klient prezesa.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowita – liczbę różnych mas węgla z przedziału [A;B], które można odważyć z użyciem firmowej wagi oraz posiadanych odważników.

Ograniczenia

1 ≤ A ≤ B ≤ 1018.

Przykład

Wejście Wyjście Wyjaśnienie
2 12
5

Możliwe do zważenia masy węgla w tym przypadku to: 3, 4, 5, 11 oraz 12.