Un número escrito en binario y leído como si fuera decimal. Detrás de una serie rara se esconde un patrón de ochos, y se llega a él paso a paso.
Autor: Denilson Fiesta Inocente100 puntos · 6 subtareas
// el problema
La historia, en corto
A Redo le encantan los sistemas numéricos. Un día hizo este juego con cada número n = 0, 1, 2, 3, …:
Escribe n en binario (base 2). Por ejemplo, 4 se escribe 100.
Lee esos mismos dígitos como si fueran un número en base 10: 100 es cien.
Le resta el número original: 100 − 4 = 96.
Así obtuvo la serie 0, 0, 8, 8, 96, … El término número k corresponde a n = k − 1.
La pregunta: ¿cuánto sube la serie del término k − 1 al término k? Con
k hasta 1018, y una respuesta que puede ser tan grande que no cabe en ningún tipo de número de
C++.
La máquina de Redo· calcula la diferencia para cualquier k
// qué hay que programar
Una función que devuelve texto
El grader de la OBI lee k, llama a tu función diferencia y escribe lo que devuelve. Tú no lees
ni imprimes nada. Fíjate en algo raro: la función devuelve un string, no un número. Ya verás por qué.
archivo de prueba
5
→
grader (lo pone la OBI) lee la entrada y llama adiferencia(5)
→
tu función, en redos.cpp std::string diferencia(long long k);
Cada bloque es una subtarea, tan ancho como sus puntos. Tócalo para ir a su explicación.
Las primeras subtareas se ganan mirando una tabla, sin saber por qué funciona. Las últimas piden
entender el patrón. Es una muy buena forma de atacar un problema que no entiendes del todo: calcula a mano los
primeros casos y busca qué se repite.
Subtarea 1
k par: la respuesta es 0
+7 puntos
k es par y k ≤ 1000
Antes de programar nada, calcula la diferencia para los primeros valores de k. Puedes hacerlo a mano o
con la tabla de abajo. Aprieta los botones para pintar las filas:
Tabla de diferencias· k de 2 a 41
k
k − 1 en binario
diferencia
Con «k par» todas las filas pintadas tienen diferencia 0. Esto ya da 7 puntos: basta
con return "0"; cuando k es par. El código está junto con la subtarea 2, abajo.
Subtarea 2
k mod 4 = 3: la respuesta es 8
+9 puntos
k mod 4 = 3 y k ≤ 1000
Pinta ahora «k mod 4 = 3» (es decir, el residuo de dividir k entre 4 es 3: k = 3,
7, 11, 15, …). Todas dan 8. Un mismo programa puede ganar las dos subtareas:
redos.cpp · subtareas 1 y 216 pts
#include "redos.h"#include <string>using namespace std;// Subtareas 1 y 2: el patrón que se ve en una tabla.// Si k es par, la diferencia es 0. Si k % 4 == 3, es 8.string diferencia(long long k) { if (k % 2 == 0) return "0"; if (k % 4 == 3) return "8"; return "88"; // una adivinanza para los demás casos (no siempre acierta)}
El último return "88" es solo una adivinanza: no sirve para las demás subtareas, pero no hace daño.
Para seguir subiendo hay que calcular la diferencia de verdad.
Subtarea 3
Fuerza bruta: hacer lo que dice el enunciado
+14 puntos
k ≤ 1000
Con k ≤ 1000 podemos seguir la definición al pie de la letra: pasar n a binario,
leerlo como decimal y restar. Para pasar a binario se divide entre 2 una y otra vez; cada residuo es un dígito
binario, empezando por el último. Vamos poniendo cada dígito en la posición de las unidades, las decenas, las
centenas…
redos.cpp · subtarea 330 pts
#include "redos.h"#include <string>using namespace std;// Escribe n en binario y lee esos dígitos como si fueran un número en base 10.// Por ejemplo, 4 = 100 en binario, que leído en base 10 es cien.long long binario_como_decimal(long long n) { long long r = 0, p = 1; while (n > 0) { r += (n % 2) * p; // el dígito binario va en la posición p = 1, 10, 100, ... p *= 10; n /= 2; } return r;}long long termino(long long n) { return binario_como_decimal(n) - n;}// Subtarea 3 (k <= 1000): seguimos la definición al pie de la letra.// El k-ésimo término corresponde a n = k - 1.string diferencia(long long k) { return to_string(termino(k - 1) - termino(k - 2));}
Con k ≤ 1000, n tiene a lo más 10 dígitos en binario, y leído en base 10 queda menor que
1010: cabe sin problema en un long long. Este código gana las subtareas 1, 2 y 3.
Dato curioso: con long long este mismo código también ganaba la subtarea 4, porque los desbordes
de las dos restas se cancelan mientras la respuesta tenga como mucho 19 cifras. Así se llegaba a 36
puntos (7 + 9 + 14 + 6). Pero es suerte, no una idea: en la subtarea 5 ya no alcanza.
Subtarea 4
k − 1 es potencia de 10
+6 puntos
k − 1 es una potencia de 10
Esta subtarea es una curiosidad. Si k − 1 = 10m (10, 100, 1000…), la respuesta
tiene m ochos. Por ejemplo, para k = 101 la diferencia es 88. Pruébalo en la
máquina de Redo de arriba.
¿Por qué? Como 10m = 2m × 5m y
5m es impar, en binario 10m termina en exactamente m ceros.
Y la cantidad de ceros al final en binario es lo que importa (lo verás en la subtarea 6). Basta contar los ceros
al final de k − 1 escrito normal:
redos.cpp · subtarea 46 pts
#include "redos.h"#include <string>using namespace std;// Subtarea 4 (k - 1 = 10^m): como 10^m = 2^m * 5^m, en binario termina en// exactamente m ceros. La respuesta tiene tantos 8 como ceros tiene k - 1// al final, escrito en base 10.string diferencia(long long k) { long long n = k - 1; int ceros = 0; while (n > 0 && n % 10 == 0) { ceros++; n /= 10; } if (ceros == 0) return "0"; return string(ceros, '8');}
Subtarea 5
k − 1 es potencia de 2: ¡ochos como texto!
+26 puntos
k − 1 es una potencia de 2
Pinta en la tabla «k − 1 potencia de 2»: k = 3, 5, 9, 17, 33 dan 8, 88, 888, 8888, 88888. Si
k − 1 = 2t, la respuesta son t ochos.
Contar t es fácil: cuántas veces se puede dividir k − 1 entre 2 hasta llegar a 1. El reto es
otro: t puede llegar a 59, y un número de 59 ochos no cabe en ningún tipo entero de C++. Mueve el control:
¿Dónde cabe la respuesta?
La solución: no guardarlo como número. Un string puede tener tantos caracteres como queramos, y
string(t, '8') arma un texto con t ochos. Por eso la función devuelve texto.
redos.cpp · subtarea 526 pts
#include "redos.h"#include <string>using namespace std;// Subtarea 5 (k - 1 = 2^t): la respuesta son t ochos. Puede tener hasta 59// cifras, así que no cabe en long long: la armamos como texto.string diferencia(long long k) { if (k % 2 == 0) return "0"; // k - 1 = 2^t: dividimos entre 2 hasta llegar a 1 y contamos las veces. int t = 0; for (long long n = k - 1; n > 1; n /= 2) t++; return string(t, '8');}
Subtarea 6
Contar los ceros del final en binario
+38 puntos
Sin restricciones adicionales
Falta entender el caso general. Mira qué pasa en binario cuando le sumas 1 a n − 1. Si termina en
t unos, esos unos se vuelven ceros y el 0 anterior se vuelve 1, igual que 0999 + 1 = 1000 en base 10:
n − 1 = …0111 (t = 3 unos al final)
n = …1000 (t = 3 ceros al final)
Leído en base 10, el pedazo que cambia pasa de 111 a 1000: sube 1000 − 111 = 889. El resto de los dígitos no
cambia. Como n sube 1, el término sube 889 − 1 = 888. Con t ceros siempre
sale lo mismo:
10t − 11…1 − 1 = 88…8 (t ochos)
Entonces la respuesta tiene tantos ochos como ceros al final tiene k − 1 en binario. Y
todo lo anterior encaja: si k es par, k − 1 es impar y no termina en 0 (respuesta 0); si
k mod 4 = 3, k − 1 termina en 10 (un ocho); si k − 1 =
2t, termina en t ceros.
redos.cpp · solución completa100 pts
#include "redos.h"#include <string>using namespace std;// Solución completa, O(log k).// Al pasar de n - 1 a n en binario, los unos del final de n - 1 se vuelven// ceros. La diferencia es un 8 por cada cero al final de n = k - 1 en binario.string diferencia(long long k) { long long n = k - 1; if (n % 2 == 1) return "0"; // k par: n impar no termina en cero string respuesta = ""; while (n % 2 == 0) { // n >= 1, así que el bucle termina respuesta += '8'; n /= 2; } return respuesta;}
Cada vuelta del bucle divide n entre 2, así que da a lo más 60 vueltas: es O(log k).
// para la próxima
Errores comunes
Armar 88…8 como número (ans = ans * 10 + 8) en un long long. Funciona hasta 19 ochos y después se desborda.
Contar todos los dígitos binarios en vez de solo los ceros del final. Coincide cuando k − 1 es potencia de 2, pero no en general.
Usar int en la fuerza bruta: solo aguanta hasta 9 ochos.