$ cd preparacion/editoriales/clasificatoria-2026/somarithmo

Somarithmo faltante

Una sucesión infinita de números y ceros, un tramo visto por telescopio y un hueco. Para saber quién falta basta mirar al vecino correcto.

Autor: Raul Ronald Zárate Murillo 100 puntos · 5 subtareas

// el problema

La historia, en corto

Los Somarithmos viven formados en una fila infinita hacia la izquierda que termina en 1. Hay dos tipos: los números positivos (los Zahlen+) y los ceros (los Oudens). El final de la fila se ve así:

… 0 0 0 0 0 5 0 0 0 0 4 0 0 0 3 0 0 2 0 1

La regla: cada Zahlen+ k tiene justo antes k Oudens, y antes de ellos está k + 1. El 3 tiene tres ceros a su izquierda, el 2 tiene dos, el 1 tiene uno.

Con un telescopio se ve un tramo de K Somarithmos seguidos, de cualquier parte de la fila. Uno de ellos se perdió y quedó un hueco. Hay que decir quién falta: un Ouden (0) o un Zahlen+ (su valor). Siempre se ve al menos un Zahlen+.

El telescopio· adivina quién falta

Este es el ejemplo 3 del enunciado. Piensa quién está en el hueco y después pide una pista o la respuesta. Con «Nuevo tramo» aparece otro al azar.

// qué hay que programar

Una función que recibe el tramo

Tu función faltante recibe el tramo en un vector, con el hueco marcado como −1, y devuelve 0 si falta un Ouden o el valor del Zahlen+ que falta. El grader lee el archivo (donde el hueco es un *), arma el vector, llama a tu función y escribe Ouden o Zahlen+{k}.

archivo de prueba
5
* 0 0 0 3
grader (lo pone la OBI) lee la entrada y llama a faltante({-1, 0, 0, 0, 3})
tu función, en somarithmo.cpp int faltante(std::vector<int> a);
el grader escribe
Zahlen+{4}

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

// la escalera de puntos

Del regalo a la regla completa

Cada bloque es una subtarea, tan ancho como sus puntos. Tócalo para ir a su explicación.

La subtarea 1 se gana con fuerza bruta. Las demás son situaciones: cada una te deja pensar en un solo caso (el hueco junto a un número, el que falta es un número, hay un número a la izquierda) y la última los junta.

Subtarea 1

Generar la sucesión

+12 puntos

Todos los valores son ≤ 500

Si todos los valores son a lo más 500, podemos construir el final de la sucesión y buscar en ella el tramo. Es más fácil generarla de derecha a izquierda: 1, 0, 2, 0, 0, 3, 0, 0, 0, 4, … (cada k seguido de k ceros). Hasta el 501 son unos 126 mil elementos.

Después tomamos un Zahlen+ que se vea, en la posición p del tramo, y lo buscamos en la sucesión generada: está en la posición q. Como cada Zahlen+ aparece una sola vez, eso ubica todo el tramo. El hueco está p − h lugares más a la izquierda (o a la derecha, si es negativo), y como generamos al revés, eso es avanzar en la lista.

somarithmo.cpp · subtarea 1 12 pts
#include "somarithmo.h"

#include <vector>
using namespace std;

// Subtarea 1 (todos los valores <= 500): generamos la sucesión leída de
// derecha a izquierda: 1, 0, 2, 0, 0, 3, 0, 0, 0, 4, ... hasta pasar el 501.
int faltante(vector<int> a) {
    vector<int> r;  // r[0] es el 1 final, r[1] el Ouden a su izquierda, ...
    for (int k = 1; k <= 501; k++) {
        r.push_back(k);
        for (int j = 0; j < k; j++) r.push_back(0);
    }
    int p = 0, h = 0;
    while (a[p] <= 0) p++;   // p: posición de un Zahlen+ visible
    while (a[h] != -1) h++;  // h: posición del hueco
    // Buscamos dónde está ese Zahlen+ en la sucesión.
    int q = 0;
    while (r[q] != a[p]) q++;
    // r va de derecha a izquierda: moverse a la izquierda en a es avanzar en r.
    return r[q + (p - h)];
}

¿Y si los valores llegan a 109? Para llegar al número v hay que generar unos v2 / 2 elementos:

¿Cuánto tarda?· límite: 1 segundo

Con valores cerca de 109 habría que generar 5 × 1017 elementos: ni el tiempo ni la memoria alcanzan. Hay que usar la regla sin construir nada.

Subtarea 2

Pegado a un número: es un cero

+3 puntos

El hueco está pegado a un Zahlen+ visible

Mira la sucesión: dos Zahlen+ nunca están juntos. Antes de cada k hay al menos un cero, y después de cada k (salvo el 1 final, que no tiene nada después) viene el 0 que precede a k − 1. Si el hueco está pegado a un Zahlen+ visible, en el hueco hay un Ouden.

somarithmo.cpp · subtarea 2 3 pts
#include "somarithmo.h"

#include <vector>
using namespace std;

// Subtarea 2 (el hueco está pegado a un Zahlen+ visible): junto a un Zahlen+
// siempre hay un Ouden (dos Zahlen+ nunca están juntos), así que la respuesta es 0.
int faltante(vector<int> a) {
    return 0;
}

Son solo 3 puntos, pero valen lo mismo que cualquier otros 3. Siempre revisa si alguna subtarea es casi gratis.

Subtarea 3

Si falta un número, mira al vecino

+18 puntos

El que falta es un Zahlen+

Si sabemos que falta un Zahlen+ m, los Zahlen+ más cercanos al hueco son sus vecinos en la fila: m + 1 a la izquierda y m − 1 a la derecha. Entonces basta encontrar el Zahlen+ visible más cercano al hueco:

  • si está a la izquierda y vale u, falta u − 1;
  • si está a la derecha y vale u, falta u + 1.
somarithmo.cpp · subtarea 3 18 pts
#include "somarithmo.h"

#include <vector>
using namespace std;

// Subtarea 3 (el que falta es un Zahlen+): miramos el Zahlen+ visible más
// cercano al hueco. Si está a la izquierda, el que falta es uno menos; si está
// a la derecha, es uno más.
int faltante(vector<int> a) {
    int K = a.size(), h = 0;
    while (a[h] != -1) h++;
    for (int d = 1; d < K; d++) {
        if (h - d >= 0 && a[h - d] > 0) return a[h - d] - 1;
        if (h + d < K && a[h + d] > 0) return a[h + d] + 1;
    }
    return 0;
}

Esto ya no genera nada: revisa como mucho el tramo, O(K). Lo que le falta es decidir cuándo el hueco es un Ouden.

Subtarea 4

Bajar desde un número de la izquierda

+28 puntos

Hay un Zahlen+ visible a la izquierda del hueco

Supongamos que hay un Zahlen+ u visible a la izquierda del hueco. Leyendo hacia la derecha, después de u vienen u − 1 ceros y luego el Zahlen+ u − 1. O sea, u − 1 está exactamente u lugares a la derecha de u.

5 0 0 0 0 4 el 4 está a 5 lugares del 5

Tomamos el Zahlen+ visible más cercano por la izquierda, a distancia d del hueco. Si d = u, el hueco es justo donde va u − 1. Si no, cae en uno de los ceros.

somarithmo.cpp · subtarea 4 28 pts
#include "somarithmo.h"

#include <vector>
using namespace std;

// Subtarea 4 (hay un Zahlen+ visible a la izquierda del hueco): tomamos el más
// cercano, u, en la posición i. A su derecha vienen u - 1 Oudens y después el
// Zahlen+ u - 1, que está exactamente a distancia u.
int faltante(vector<int> a) {
    int h = 0;
    while (a[h] != -1) h++;
    for (int i = h - 1; i >= 0; i--) {
        if (a[i] > 0) {
            int u = a[i];
            if (h - i == u) return u - 1;  // el hueco cae justo donde va u - 1
            return 0;                      // si no, es uno de los Oudens
        }
    }
    return 0;
}
Subtarea 5

Las dos direcciones

+39 puntos

Sin restricciones adicionales

Falta el caso en que el Zahlen+ más cercano está a la derecha. Leyendo hacia la izquierda, antes de u hay u ceros y luego u + 1. Así que u + 1 está a u + 1 lugares a la izquierda de u:

4 0 0 0 3 el 4 está a 4 lugares del 3

Juntando todo, con el Zahlen+ visible u más cercano al hueco, a distancia d:

  • si está a la izquierda: falta u − 1 si d = u, y si no, un 0;
  • si está a la derecha: falta u + 1 si d = u + 1, y si no, un 0.
somarithmo.cpp · solución completa 100 pts
#include "somarithmo.h"

#include <vector>
using namespace std;

// Solución completa, O(K). Buscamos el Zahlen+ visible u más cercano al hueco,
// que está a distancia d.
// - Si u está a la izquierda: el siguiente Zahlen+ hacia la derecha es u - 1,
//   a distancia u.
// - Si u está a la derecha: u está precedido por u Oudens, y antes de ellos
//   está u + 1, a distancia u + 1.
// Cualquier otra posición es un Ouden.
int faltante(vector<int> a) {
    int K = a.size(), h = 0;
    while (a[h] != -1) h++;
    for (int d = 1; d < K; d++) {
        if (h - d >= 0 && a[h - d] > 0) {
            int u = a[h - d];
            return d == u ? u - 1 : 0;
        }
        if (h + d < K && a[h + d] > 0) {
            int u = a[h + d];
            return d == u + 1 ? u + 1 : 0;
        }
    }
    return 0;
}

// para la próxima

Errores comunes

  • Suponer que el tramo termina en el 1 final. El tramo puede estar en cualquier parte de la fila.
  • Confundir las distancias: hacia la izquierda es u + 1, hacia la derecha es u.
  • Olvidar que el 1 final también se puede perder (ejemplo 5: 2 0 * → falta el 1).
  • Desbordes en la versión con posiciones absolutas.