Comprar un Entero

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 256M

Authors:

FrankHG, Albe, mdario

Problem types

Allowed languages

C, C++, Java, Pascal, Python, VB

Carl el erizo de Chantal fue a una tienda de enteros a comprar enteros obviamente.

La tienda vende enteros desde $1$ ~1~ hasta $10^9$ ~10^9~. El entero $N$ ~N~ se vende por $A * N + B * d(N)$ ~A * N + B * d(N)~ pesos, donde $d(N)$ ~d(N)~ es el número de dígitos en notación decimal de $N$ ~N~.

Encuentra el entero más grande que Carl puede comprar si el tiene $X$ ~X~ pesos. Si ningún entero puede ser comprado imprime $0$ ~0~.

Limites:

$1 \leq A \leq 10^9$ ~1 \leq A \leq 10^9~

$1 \leq B \leq 10^9$ ~1 \leq B \leq 10^9~

$1 \leq X \leq 10^{18}$ ~1 \leq X \leq 10^{18}~

Entrada:

La primera línea contiene tres enteros $A$ ~A~, $B$ ~B~ y $X$ ~X~.

Salida:

Imprime el mayor entero que puede comprar Carl. Si no puede comprar ningún entero imprime $0$ ~0~.

Entrada ejemplo 1:

10 7 100

Salida de ejemplo 1:

El entero $9$ ~9~ es vendido por $10 * 9 + 7 * 1 = 97$ ~10 * 9 + 7 * 1 = 97~ pesos y es el mayor entero que puede ser comprado. Alguno de los otros enteros son vendidos por:

$10: 10 * 10 + 7 * 2 = 114$ ~10: 10 * 10 + 7 * 2 = 114~ pesos

$100: 10 * 100 + 7 * 3 = 1021$ ~100: 10 * 100 + 7 * 3 = 1021~ pesos

$12345: 10 * 12345 + 7 * 5 = 123485$ ~12345: 10 * 12345 + 7 * 5 = 123485~ pesos

Entrada de ejemplo 2:

2 1 100000000000

Salida de ejemplo 2:

1000000000

Entrada de ejemplo 3:

1000000000 1000000000 100

Salida de ejemplo 3:

Entrada de ejemplo 4:

1234 56789 314159265

Salida de ejemplo 4:

Comments

2

LeandroGamer commented on Jan. 24, 2024, 8:07 p.m.

Observa que debemos comprar un número con el mayor número posible de dígitos, ya que cualquier número es estrictamente mayor que cualquier otro número con menos dígitos. Iteramos sobre los posibles números de dígitos en orden decreciente e imprimimos nuestra respuesta tan pronto como encontremos un número de dígitos con el que podamos comprar algún número.

Dado que queremos comprar un número de N dígitos, el más barato es 10^N-1, que costará 10N-1A+NB. Si esto es mayor que X, debemos probar con un valor menor de N. Si no, resolvamos el número máximo que podemos comprar. Supongamos que este número es M. Entonces, debemos tener MA+NB<=X, por lo que MA<=X-NB, por lo queM<=(X-NB)/A. Así, cualquier número de N dígitos que sea como máximo (X-NB)/A será lo suficientemente barato. Tenga en cuenta que, como hemos asumido que estamos comprando un número de N dígitos, M debe ser como máximo 10^N-1, incluso si (X-NB)/A es 10N o mayor. (Por ejemplo, si A=1, B=20 y X=40, está claro que no podemos comprar ningún número con al menos dos dígitos, y cuando consideramos un dígito, encontramos que (X-NB)/A=20. Sin embargo, como sólo estamos considerando números de un dígito, la mayor respuesta posible es 9).

A partir de aquí, podemos iterar sobre todos los valores posibles de N en orden decreciente e imprimir la respuesta correspondiente al primer valor suficientemente barato de N. Probablemente sea una buena idea comprobar por separado si podemos comprar 10^9, ya que este caso funciona de forma un poco diferente porque no podemos comprar ningún número mayor de 10 dígitos.

Tiempo de ejecución: O(logMX), donde MX es el mayor número entero vendido.

1

lrivero commented on Jan. 24, 2024, 8:08 p.m.

Muchas Gracias.

1

lrivero commented on Jan. 24, 2024, 8:00 p.m.

Alguna ayuda con este ejercicio?