Link del problema: 2858 - Parsing Binary Strings
Dificultad: Fácil.
Problema: Dada una cadena S que solo tiene números binarios y letras minúsculas de la 'a' a la 'z' imprimir todos los caracteres excepto las cadenas de números binarios, a estas cadenas convertirlas a su representación decimal e imprimirlas junto a la cadena. A lo más serán 10,000 caracteres para lo cual es necesario sacar modulo 1000000007 (10^9 + 7) ya que el número puede ser muy grande.
Ejemplo:
Input:
Input:
saludosamis11amigosqueestana1010kilometrosdedistancia
Output:
saludosamis3amigosqueestana10kilometrosdedistancia
Complejidad: O(N) donde $1<=N<=10000$ es el número de caracteres dentro de la cadena.
Solución:
Este problema es muy simple ya que basta con ir recorriendo caracter a caracter y checar que si no es 1 ó 0 solo lo imprimamos el caracter pero ¡¿que pasa cuando es Binary String!?
Lo primero que se nos ocurriría es tratar la Binary String con corrimientos pero dado que el número puede ser muy grande esto no funcionaría así que con una simple operación de multiplicar por 2 cada que haya 0 o 1 será suficiente.
Primero hacemos un define de nuestro modulo para no tener que estar poniendo tanto 0 xD:
Así pues tendríamos dos decisiones:
Lo primero que se nos ocurriría es tratar la Binary String con corrimientos pero dado que el número puede ser muy grande esto no funcionaría así que con una simple operación de multiplicar por 2 cada que haya 0 o 1 será suficiente.
Primero hacemos un define de nuestro modulo para no tener que estar poniendo tanto 0 xD:
#define modulirri 1000000007
Así pues tendríamos dos decisiones:
numerote = 0;
if(S[i]=='1'){
numerote *= 2;
numerote += 1;
numerote %= modulirri;
}
Nótese que primero debemos multiplicar por dos nuestro número ya que si tenemos el caso que la cadena sea de tamaño N = 1 entonces nos daría la respuesta 2 porque primero sumamos uno y luego multiplicamos por dos pero basta con primero multiplicar y después sumarle el 1. La otra decisión:else if(S[i]=='0'){
numerote *= 2;
numerote %= modulirri;
}
Y no olviden ir multiplicando por dos para aumentar el número ;).Y bueno eso fue todo por esta ocasión si pueden y quieren compartir háganlo, mi equipo y yo estamos a la disposición de sugerencias de problemas de programación competitiva, saludos!!!
Por Adrián Fernández @ferprogramming
No hay comentarios on "Parsing Binary Strings (COJ)"