Since D was created, I thought I should take a look at E as well, so I wonder if there is a mathematical formula that is too difficult to see at first glance. I thought and tried it. From the conclusion, I didn't understand at all. This is the E problem ... Until you study the basics of the algorithm properly, you may be able to do your best until D. The problem is from the E problem of ABC148. The following is a quote.
E - Double Factorial For an integer n greater than or equal to 0, define f (n) as follows: f (n) = 1 (when n <2) f (n) = nf (n−2) (when n ≥ 2) Given the integer N. Find how many zeros follow when f (N) is written in decimal notation.
① For the time being, do you think about how many trailing 0s there are? It's stupid enough to be embarrassed to look back and write. I was just told about the amount of calculation yesterday ...
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())
It was TLE. I made the same mistake again ... stupid. I'm sorry for unnecessarily overloading the server. I took the trouble to study regular expressions, and I immediately used the ternary operator I learned.
① If you start with an odd number, there will be no 10 or shit. (2) Since 5 does not appear, only the number of 10 that appears is ok. I noticed it now. Is it the extreme of stupidity?
import re
n = int(input())
ans=0
#Pear when odd and too small
if n % 2 !=0 or n < 10:
print(0)
else:
while n >= 10:
#For the time being, reduce it to a multiple of 10.
if n % 10 != 0:
n -= 2
#Decrease by 10 and add up by counting the trailing 0s
else:
z = re.search('0+$' , str(n))
ans += len(str(n)) - z.start()
n -= 10
print(ans)
This is TLE. It's been reduced a while ago! I was wondering if I could go, but I think I could make it shorter. It is self-evident that the number of 0s has regularity. I don't know at all. Cheat
――The answer is to divide by 2 and continue to add the quotient divided by 5 [^ 1]
why? !! I don't know at all. Programmer, IQ is 300 [^ 2]? ?? ?? I wonder if that is the basis of some kind of algorithm. I will study the algorithm properly.
(Addition)
――When 5 appears in the divisor, 0 increases again with 2 included in the surrounding even numbers. --Since odd numbers are excluded, 5 appears in the divisor when 2 * 5 i </ sup> ――So, you should count every time 2 * 5 i </ sup> appears.
→ Continue to divide by 5 or n // 2 * 5 Continue to i </ sup> I see!
[^ 1]: There were several others, but this was the one that seemed to chew most in my brain. [^ 2]: There are probably about IQ5000 of strong people who end up in one line.
Recommended Posts