Runda 4 [Hard] - Kule śnieżne

13.12.2010 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

Runda 4; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 32MB


Kule śnieżne

Góry i doliny pokrył śnieżny puch. Tak się właśnie złożyło, że mały Jaś wybrał się na pieszą wycieczkę na szczyt najwyższej z gór. Zauważył, że na szczycie, wzdłuż przepaści poustawiane są śnieżne kule o wszystkich możliwych rozmiarach, wyrażonych liczbami naturalnymi, od jeden włącznie.

Jaś wie, że wystarczy mu sił aby zepchnąć w dół kule z pewnego przedziału - dokładnie, jeśli przypomni sobie ile kanapek zjadł rano, szybko znajdzie dwie liczby $ a $ i $ b $, $ a \leq b $, takie, że uda mu się zepchnąć w przepaść dokładnie kule o rozmiarach $ a $, $ a+1 $, ... , $ b-1 $, $ b $.   

Jaś wie dobrze, że sam rozmiar niekoniecznie świadczy o tym, ile kula narobi huku w przepaści. Pamięta opowieść starego górala - jeśli weźmie się rozmiar danej kuli i policzy, ile różnych cyfr występuje w jego zapisie dziesiętnym, to taki właśnie jest współczynnik huku tej kuli. Tak więc kula rozmiaru $ 12 $ wyda bardziej imponujący dźwiękowy owoc niż kula rozmiaru $ 99999 $

Jaś chciałby więc policzyć, ile wynosi suma współczynników huku kul z przedziału, który uda mu się zepchnąć w przepaść. Poprosił Cię o pomoc.

Wejście:

Pierwsza i jedyna linia wejścia zawiera jedną liczbę całkowitą $ t $ ($ 1 \leq t \leq 100 $) - liczbę przypadków testowych do rozważenia. Każdy przypadek testowy opisany jest w jednej linii przez dwie liczby $ a_{i} $ $ b_{i} $ ($ 1 \leq a_{i} \leq b_{i} \leq 10^{16} $).

Wyjście:

Dla każdego przypadku testowego należy wypisać w osobnej linii jedną liczbę całkowitą - sumę współczynników huku wszystkich kul o rozmiarach z przedziału $ a_{i}, a_{i}+1, ..., b_{i} $.

Przykład:

Wejście:

3
1 11
547892 547892
14 18

Wyjście:

12
6
10
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasKule śnieżne
1Damian Straszak1017:50:5110
2Bartosz Tarnawski1060:19:4410
3Piotr Bejda1061:33:0710
4Krzysztof Drab10132:02:3310
5Maciej Kisiel10387:37:5410
6Witold Długosz102245:32:3010
7Przemysław Derengowski5160:04:385
8Kamil Dębowski4158:13:544
9Michal Zgliczynski1435:53:071
3
Twoja ocena: Brak Ocena: 3 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com