[PYTHON] AtCoder Ich kenne Tagebuch_2 ABC148E nicht

Einführung

Da D erstellt wurde, dachte ich, ich sollte mir auch E ansehen, also frage ich mich, ob es eine Formel gibt, die auf den ersten Blick zu schwer zu erkennen ist. Ich dachte und versuchte es. Aus der Schlussfolgerung habe ich überhaupt nicht verstanden. Dies ist das E-Problem ... Bis Sie die Grundlagen des Algorithmus richtig studiert haben, können Sie möglicherweise Ihr Bestes geben, bis D. Das Problem stammt aus dem E-Problem von ABC148. Das Folgende ist ein Zitat.

E - Double Factorial Definieren Sie für eine ganze Zahl n größer oder gleich 0 f (n) wie folgt: f (n) = 1 (wenn n <2) f (n) = nf (n - 2) (wenn n ≥ 2 ist) Angesichts der ganzen Zahl N. Finden Sie heraus, wie viele Nullen folgen, wenn f (N) in Dezimalschreibweise geschrieben wird.

Gedanken

① Denken Sie vorerst darüber nach, wie viele nachgestellte Nullen es gibt? Es ist dumm genug, sich zu schämen, zurückzublicken und zu schreiben. Mir wurde gestern gerade über den Rechenaufwand berichtet ...

Erstes Mal

import re
n = int(input())
i=n-2
while i >= 2:
    n *= i
    i -= 2
    ans = re.search('0+$' , str(n))
print(0 if n%10 !=0 or n < 2 else len(str(n))-ans.start())

Es war TLE. Ich habe wieder den gleichen Fehler gemacht ... blöd. Es tut mir leid, dass ich den Server unnötig überlastet habe. Ich nahm mir die Mühe, reguläre Ausdrücke zu studieren, und benutzte den ternären Operator, den ich neulich gelernt hatte.

Zweites Mal

① Wenn Sie mit einer ungeraden Zahl beginnen, gibt es keine 10 oder Scheiße. (2) Da 5 nicht angezeigt wird, ist nur die angezeigte Zahl 10 in Ordnung. Ich habe es jetzt bemerkt. Ist es das Extrem der Dummheit?

import re
n = int(input())
ans=0
#Birne, wenn es seltsam ist und wenn es zu klein ist
if n % 2 !=0 or n < 10:
    print(0)
else:
    while n >= 10:
        #Reduzieren Sie es vorerst auf ein Vielfaches von 10.
        if n % 10 != 0:
            n -= 2
        #Verringern Sie um 10 und addieren Sie die letzte 0
        else:
            z = re.search('0+$' , str(n))
            ans += len(str(n)) - z.start()
            n -= 10


    print(ans)

Das ist TLE. Es wurde vor einiger Zeit reduziert! Ich habe mich gefragt, ob ich gehen könnte, aber ich denke, ich könnte es kürzer machen. Es versteht sich von selbst, dass die Anzahl der Nullen regelmäßig ist. Ich weiß es überhaupt nicht. Einmachen

Antwort des starken Mannes (Tsuyobito)

――Die Antwort besteht darin, durch 2 zu teilen und den durch 5 geteilten Quotienten weiter zu addieren [^ 1]

Warum? !! Ich weiß es überhaupt nicht. Programmierer, IQ ist 300 [^ 2]? ?? ?? Ich frage mich, ob das die Grundlage eines Algorithmus ist. Ich werde den Algorithmus richtig studieren.

(Zusatz)

――Wenn 5 in der Fraktion erscheint, steigt 0 wieder an, wobei 2 in der Umgebung gerade enthalten ist. ――Da die ungerade Zahl ausgeschlossen ist, erscheint 5 im Bruch, wenn 2 * 5 ^{i </ sup> ――So sollten Sie jedes Mal zählen, wenn 2 * 5 i </ sup> erscheint.}

→ Teilen Sie weiter durch 5 oder n // 2 * 5 Fahren Sie fort mit ^{i </ sup> Aha!}

[^ 1]: Es gab mehrere andere, aber dies war derjenige, der am meisten in meinem Gehirn zu kauen schien. [^ 2]: Es gibt wahrscheinlich etwa IQ5000 starker Leute, die in einer Zeile landen.