$ cd preparacion/editoriales/clasificatoria-2026/redos

Re 2

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 Inocente 100 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, …:

  1. Escribe n en binario (base 2). Por ejemplo, 4 se escribe 100.
  2. Lee esos mismos dígitos como si fueran un número en base 10: 100 es cien.
  3. 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 a diferencia(5)
tu función, en redos.cpp std::string diferencia(long long k);
el grader escribe
88

Más sobre el grader en la página de inicio de las editoriales.

// la escalera de puntos

Seis subtareas para descubrir un patrón

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
kk − 1 en binariodiferencia

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 2 16 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 3 30 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 4 6 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 5 26 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 completa 100 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.