Résolvez le problème de la dichotomie.
Essayer tous les nombres entiers vendus vous donnera un TLE. Par conséquent, nous devons bien réduire la quantité de calcul, nous utilisons donc la dichotomie. La dichotomie est une méthode de recherche de la solution souhaitée en rétrécissant la plage des deux extrémités. Explication détaillée. Le montant du calcul pour la dichotomie est $ O (log N) $, donc c'est dans le temps.
a,b,x = map(int,input().split())
max_n = 10**9+1 #La valeur maximale de n est 10**Parce que c'est 9+1
min_n = 0
while max_n - min_n > 1:
mid_n = (max_n+min_n)//2
if x < a*(mid_n)+b*len(str(mid_n)):
max_n = mid_n
else:
min_n = mid_n
print(min_n)
Si vous pouvez bien utiliser la dichotomie, vous pouvez réduire considérablement la quantité de calcul, je veux donc la maîtriser. à plus.
Recommended Posts