Preparando programame: UVA 575 Pasar un número de Skew Binary a entero.

lunes, 12 de enero de 2015

UVA 575 Pasar un número de Skew Binary a entero.

Cuando un número es expresado en decimal, el dígito k-th representa un múltiplo de 10^k. (Los dígitos son numerados de derecha a izquierda, donde el dígito menos significante es el 0.) Por ejemplo,

$\begin{displaymath}81307_{10} = 8 \times 10^4 + 1 \times 10^3 + 3 \times 10^2 + ... ...mes 10^1 + 7 \times 10 0 = 80000 + 1000 + 300 + 0 + 7 = 81307. \end{displaymath}$

Cuando un número es expresado en binario, el dígito k-th representa un múltiplo de 2^k. Por ejemplo,

$\begin{displaymath}10011_2 = 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 16 + 0 + 0 + 2 + 1 = 19. \end{displaymath}$

En binario skew, el dígito k-th representa un múltiplo de 2^k+1 - 1.Los únicos dígitos posibles son el 0 y el 1, excepto que el menos significante dígito nonzero puede ser un 2.Por ejemplo,

$\begin{displaymath}10120_{skew} = 1 \times (2^5 - 1) + 0 \times (2^4-1) + 1 \tim... ...2 \times (2^2-1) + 0 \times (2^1-1) = 31 + 0 + 7 + 6 + 0 = 44. \end{displaymath}$

Los primeros 10 números en binario skew son el 0, 1, 2, 10, 11, 12, 20, 100 y 102. (Binario skew es útil en diferentes aplicaciones porque es posible añadir con un máximo acarreado. Sin embargo, esto no tiene nada que ver con el siguiente problema.)

Input

La entrada contiene una o mas líneas, cada cual contiene un entero n. Si n = 0 señaliza el final de la entrada, y de lo contrario n es un no negativo entero en binario skew.

Output

Por cada numero, sale el decimal equivalente.El valor decimal de n como máximo será 2³¹ - 1 = 2147483647.

Ejemplo de Entrada

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

Ejemplo de Salida

FUENTE: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=516

Autor traducción: Jesús Casasnovas Garde.

Preparando programame

Páginas