FCTRL5 - Factorial (Again!)
Have you solved FCTRL problem?
In this problem you need to do the same task (given positive integer n < 10100 you need to count number of zeroes at the end of the decimal number of n!), seems easy(?) but this time only Brainf**k language allowed.
Input
First line of input there is an integer T ≤ 1000 denoting number of test case.
Next T lines containing an integer n.
Each line is terminated with newline character (ASCII:10)
Output
For each test case, output number of zeroes at the end of the decimal form of number n!
Example
Input: 6 3 60 100 1024 23456 8735373 Output: 0 14 24 253 5861 2183837
Other Info
Input: 100% random log-uniform.
This problem is using custom judge, so you can see the detail after you get AC/WA.
Judge output format is like this: ("Code Length (Valid Command only)")"Cell Used"("BF Command executed").
Click here to see my submission result for this problem.
Judge output for my BF code is: (1340)501(392776170) meaning that my Valid BF commands = 1340 commands and My code using 501 BF cell and 392776170 commands executed.
You can click (AC/WA) status for more detail.
My code running time is 0.59s and using 1.6MB of memory.
Time limit is ~16× my BF program speed.
hide comments
|
sawan1001:
2017-03-09 10:05:51
Hi Robert,
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2013-07-24 01:14:10
@Robert Gerbicz: Congratulations, actually your code is faster than mine (9.15% faster than mine on my own BF interpreter), but unfortunately on bff 1.0.3.1 the longer your code is the slower your running time (see my commennt on BITCNTR problem). Hope you enjoyed this problem :-)
|
|
Robert Gerbicz:
2013-07-23 16:18:17
Great problem, Tjandra, could you setup this problem in the challenge section? Score would be the number of BF commands executed.
|
|
|
(Tjandra Satria Gunawan)(曾毅昆):
2013-07-23 01:25:01
People may ask why I didn't solve FCTRL problem using Brainf**k, the answer is: that because my Brainf**k solution for that problem is too slow (or time limit is too strict for Brainf**k: 10^5 test case with 6sec time limit using pyramid cluster). I generate 10^5 worst case test case (fit on FCTRL constraints) on my pyramid tester problem and my current Brainf**k code (heavily optimized) run in 21sec (still 3.5× slower than FCTRL time limit), so I think it's impossible to solve FCTRL problem using Brainf**k with current time limit. |
| Added by: | Tjandra Satria Gunawan |
| Date: | 2013-07-15 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | BF |
| Resource: | This Problem |
RSS