À partir d'aujourd'hui, je résoudrai atcoder avec python.
https://atcoder.jp/contests/abc146/tasks/abc146_c Ce problème est le problème le plus typique de la dichotomie. Dichotomie, la théorie est simple, mais si vous la mettez en œuvre, vous pouvez ou non WA à la frontière. Cependant, si je me limite aux deux derniers, je ne veux pas être boueux pour essayer de répondre à la fois ww
Cette fois, est une dichotomie qui se remplit du côté gauche (un type de dichotomie qui recherche le nombre qui ne dépasse pas un certain nombre)
l = 0
r = 1000000001
a, b, x = tuple(map(int, input().split(" ")))
while l < r - 1:
m = l + (r - l) // 2
p = m * a + b * len(str(m))
if p > x:
r = m
else:
l = m
print(l)
#l = left, m = middle, r = right
Le point de cette fois pour éviter les bugs à la frontière
if p > x:
r = m
else:
l = m
C'est la partie de. Pourquoi est-ce le point! ??
C'est l + (r --l) // 2 Regardez ici. Réécriture, (l + r) // 2 Voilà la partie. (Ne dépassez pas le nombre de chiffres. J'entends souvent la théorie selon laquelle PYTHON n'est pas nécessaire)
Cette valeur est 10,5 ou 1000,5 lorsque l + r divisé par // est impair, et quand il est flottant, une fraction apparaît et elle est arrondie vers le bas. En d'autres termes, m dépend du sentiment de gauche </ font>
Certaines personnes peuvent se mettre en colère en lisant ceci et en disant: "C'est trop bâclé! Ne soyez pas stupide!"
Je veux dire fort à ces gens.
~~ Je suis désolé ~~
Je ne peux pas y revenir, alors je pense que c'est correct de donner l'impression que ça vient de la gauche Il s'agit de l'idée.
À bientôt
Recommended Posts