Comprar un Entero
Submit solution
Points:
100 (partial)
Time limit:
1.0s
Memory limit:
256M
Authors:
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 hasta . El entero se vende por pesos, donde es el número de dígitos en notación decimal de .
Encuentra el entero más grande que Carl puede comprar si el tiene pesos. Si ningún entero puede ser comprado imprime .
Limites:
Entrada:
La primera línea contiene tres enteros , y .
Salida:
Imprime el mayor entero que puede comprar Carl. Si no puede comprar ningún entero imprime .
Entrada ejemplo 1:
10 7 100
Salida de ejemplo 1:
9
El entero es vendido por pesos y es el mayor entero que puede ser comprado. Alguno de los otros enteros son vendidos por:
pesos
pesos
pesos
Entrada de ejemplo 2:
2 1 100000000000
Salida de ejemplo 2:
1000000000
Entrada de ejemplo 3:
1000000000 1000000000 100
Salida de ejemplo 3:
0
Entrada de ejemplo 4:
1234 56789 314159265
Salida de ejemplo 4:
254309
Comments
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 tenerMA+NB<=X
, por lo queMA<=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áximo10^N-1
, incluso si(X-NB)/A es 10N
o mayor. (Por ejemplo, siA=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.
Muchas Gracias.
Alguna ayuda con este ejercicio?