Trol


Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem types
Arrays/Llistes, Optimització, Pensar!
Category
Extern
Allowed languages
Bash, C Hashtag, C++, Haskell, Java, Kotlin, PHP, Python

aireacondicionat Stjepan recibió recientemente su licenciatura en matemáticas de la Universidad de Zagreb. Naturalmente, sus padres están muy orgullosos y han decidido regalarle todos los números enteros positivos no superiores a \(2 ^{60}\). Para mantenerlos a salvo, rápidamente almacenó todos esos números en un Array \(A\), de modo que \(Ai = i\). Su celoso amigo Marin decidió hacerle una broma reemplazando repetidamente cada elemento de \(A\) con la suma de sus dígitos hasta que todos los elementos de \(A\) consistieran en un solo dígito. Por ejemplo, el valor inicial del elemento 197avo de A era 197. Marin primero cambió ese valor a \(1 + 9 + 7 = 17\) y luego cambió su valor nuevamente a \(1 + 7 = 8\). Stjepan está devastado y le ruega a Marin que devuelva su matriz a su estado inicial. Desafortunadamente, Marin no hará eso hasta que Stjepan responda correctamente a sus preguntas Q: "¿Cuál es la suma de los números del l-ésimo al r-ésimo elemento de A?". ¡Ayuda a Stjepan a responder esas consultas!

Entrada

La primera linea contiene un entero Q \(Q (1≤Q≤100)\) . Las siguientes \(Q\) lineas contienen dos enteros li y ri \((1≤li≤ri≤2^{60})\), que es los dos valores de la pregunta de Marin

Salida

Las respuestas a las preguntas de Marin. Cada respuesta en una línea separada y en el orden de las preguntas.

Ejemplo de Entrada 1

1
1 5

Ejemplo de Salida 1

15

Ejemplo de Entrada 2

2
9 13
44 45

Ejemplo de Salida 2

19
17

Ejemplo de Entrada 3

1
1998 2018

Ejemplo de Salida 3

102

Explicacion

En el ejemplo 2:

\(1a pregunta → A9=9, A10=1+0=1, A11=1+1=2, A12=1+2=3, A13=1+3=4 . A9+A10+A11+A12+A13=9+1+2+3+4=19.\)

\(2a pregunta → A44=4+4=8, A45=4+5=9. A44+A45=8+9=17.\)


Comments


  • -2
    dserrano1  commented on Oct. 22, 2022, 12:31 a.m. edited

    enter image description here


  • 0
    marc  commented on Sept. 14, 2020, 5:35 a.m.

    Para empezar a hacer el problema os recomiendo que os hagais el array "reordenado" del 1 al 30 a ver si veis algo.