Pista 1: Cada 10 galletas que Carter come, obtiene 1 galleta nueva

Si en algún momento Carter consume \(X\) galletas, entonces recupera \[ \left\lfloor \frac{X}{10}\right\rfloor \] galletas adicionales gracias a los restos que caen al plato.

Por lo tanto, cuando Carter come galletas en grupos de 10, conviene usar siempre la mayor cantidad de galletas que forme múltiplos de 10.

Pista 2: Podemos separar las galletas en grupos de 10 y sobrantes

Si Carter tiene \(S\) galletas, el mayor múltiplo de 10 que puede comer es: \[ X = S - (S \bmod 10) \]

• Carter come \(X\) galletas.
• Recupera: \[ \text{NUEVAS} = \frac{X}{10} \]
• Las galletas restantes son: \[ S_{\text{nuevo}} = (S - X) + \frac{X}{10} \]

Cuando ya no quedan suficientes para formar un grupo de 10, Carter simplemente come todas las galletas restantes.

Solución

Sea \(S\) el número inicial de galletas que Carter tiene en el plato.

Mientras \(S \ge 10\):

1. Calculamos el mayor múltiplo de 10 no mayor que \(S\): \[ X = S - (S \bmod 10) \]
2. Sumamos \(X\) al total de galletas comidas.
3. Recuperamos: \[ \frac{X}{10} \]
4. Actualizamos el número de galletas en el plato: \[ S = (S - X) + \frac{X}{10} \]

Cuando \(S < 10\), Carter se come todas las que quedan.

La respuesta es el total acumulado de galletas que Carter llega a comer.

Implementación en C++:

El_Festin_Infinito_de_Carter.cpp

Complejidad:

En cada paso el valor de \(S\) disminuye de forma significativa, por lo que el número de iteraciones es muy pequeño (del orden de \(\log S\)).

Por caso:

• Complejidad temporal: \(O(\log S)\)
• Memoria adicional: \(O(1)\)

Para \(T\) casos, la complejidad total es \(O(T \log S)\).