Generar la sucesión
+12 puntosTodos 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.
#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:
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.