Ab heute werde ich atcoder mit Python lösen.
https://atcoder.jp/contests/abc146/tasks/abc146_c Dieses Problem ist das typischste Problem der Dichotomie. Dichotomie, die Theorie ist einfach, aber wenn Sie sie implementieren, können Sie WA an der Grenze oder nicht. Wenn ich mich jedoch auf die letzten beiden beschränke, möchte ich nicht matschig sein, um zu versuchen, beide zu beantworten
Dieses Mal ist eine Dichotomie, die von links ausgefüllt wird (eine Art Dichotomie, die nach der Zahl sucht, die eine bestimmte Zahl nicht überschreitet).
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
Der Punkt dieser Zeit, um Fehler an der Grenze zu verhindern, ist
if p > x:
r = m
else:
l = m
Es ist der Teil von. Warum ist das der Punkt! ??
Es ist l + (r - l) // 2 Schau hier. Umschreiben, (l + r) // 2 Das ist der Teil. (Überschreiten Sie nicht die Anzahl der Ziffern. Ich höre oft die Theorie, dass PYTHON unnötig ist.)
Dieser Wert ist 10,5 oder 1000,5, wenn l + r geteilt durch // ungerade ist und wenn es float ist, erscheint ein Bruch und es wird abgerundet. Mit anderen Worten, m hängt davon ab, dass sich links fühlt </ font>
Einige Leute werden vielleicht wütend, wenn sie dies lesen und sagen: "Es ist zu schlampig! Sei nicht albern!"
Ich möchte diesen Leuten laut sagen.
~~ Es tut mir leid ~~
Ich kann nicht darüber nachdenken, also denke ich, dass es in Ordnung ist, wenn es sich so anfühlt, als käme es von links Es geht um die Idee.
Bis bald
Recommended Posts