This page is still under construction.

Parts of this page are still being built. What you see may change.

Factorial

Time limit1sMemory limit512 MB

Summary
Output a single integer N between 7 and 10^14 that maximizes a score based on how close N! times a power of ten lands to an integer, avoiding floating-point traps.
Level

Hard8 of 10

Topics
Number theory, Math, Brute force, Implementation
Solved
No attempts yet

Problem

You have probably seen the following problem before.

TODO: insert problem 1984 here

Items (2) and (3) are easy, so we focus especially on (1).

At first glance it seems that summing logarithms carefully will do the job, but if you simply write the code that way, floating-point error is a concern.

Kipa is setting this problem, and intends to include as test cases the situations where floating-point error is likely to occur when solving (1).

Help Kipa.

Input

There is no input.

Output

Output one positive integer. The integer you output must be at least 7 and at most 100000000000000.

Constraints

(The source states no constraints.)

Scoring

Let the number you output be NN, and define the following real number xNx_{N}.

xN:=N!⋅101−⌊log⁡10(N!)⌋x_{N} := N! \cdot 10^{1 - \left\lfloor \log_{10}(N!) \right\rfloor}

For the value ε=1.5×10−14\varepsilon = 1.5 \times 10^{-14} fixed in advance by the judges, the real number SS related to your score is as follows.

S=998244353⋅min⁡{1,ε∣xN−⌊xN+0.5⌋∣}S = 998244353 \cdot \min\left\{1, \frac{\varepsilon}{\left|x_{N} - \left\lfloor x_{N} + 0.5 \right\rfloor \right|}\right\}

If S=998244353S = 998244353, you receive 998244353 points. Otherwise, the difference between your score and SS is guaranteed to be at most 0.020.02.

Your score is always an integer multiple of 0.010.01.

Examples1

  1. Example 1

    Input
    Expected output
    7