Məsələlər
Full Steiner Topologies
Full Steiner Topologies
A \textit{full Steiner topology} for a given point set \textit{\textbf{P}}\textbf{ = \{}\textit{\textbf{p}}\textbf{_1},\textbf{ }\textit{\textbf{p}}\textbf{_2},\textbf{ …},\textbf{ }\textit{\textbf{p_n}}\textbf{\}} is an undirected tree \textit{\textbf{T}}\textbf{ = (}\textit{\textbf{V}},\textbf{ }\textit{\textbf{E}}\textbf{)} where \textit{\textbf{V}}\textbf{ = \{}\textit{\textbf{v}}\textbf{_1},\textbf{ }\textit{\textbf{v}}\textbf{_2},\textbf{ …},\textbf{ }\textit{\textbf{v_n}},\textbf{ }\textit{\textbf{v_n}}\textbf{_\{+1\}},\textbf{ …},\textbf{ }\textit{\textbf{v}}\textbf{_\{2n-2\}\}} is the set of vertices, and \textit{\textbf{E}} is the set of edges. The \textit{\textbf{n}} distinctly labeled leaves of \textit{\textbf{T}}, \textit{\textbf{v}}\textbf{_1}, \textit{\textbf{v}}\textbf{_2}, \textbf{…}, \textit{\textbf{v_n}}, correspond to \textit{\textbf{p}}\textbf{_1}, \textit{\textbf{p}}\textbf{_2}, \textbf{…}, \textit{\textbf{p_n}}, respectively; the remaining \textit{\textbf{n}}\textbf{ - 2} vertices, \textit{\textbf{v_n}}\textbf{_\{+1\}}, \textit{\textbf{v_n}}\textbf{_\{+2\}}, \textbf{…}, \textit{\textbf{v}}\textbf{_\{2n-2\}}, called the \textit{Steiner vertices}, are mutually indistinguishable and each have a degree of three. Figure 1 shows the only full Steiner topology for \textit{\textbf{P}}\textbf{ = \{}\textit{\textbf{p}}\textbf{_1}, \textit{\textbf{p}}\textbf{_2}, \textit{\textbf{p}}\textbf{_3\}}. Figure 2 shows all three different full Steiner topologies for \textit{\textbf{P}}\textbf{ = \{}\textit{\textbf{p}}\textbf{_1},\textbf{ }\textit{\textbf{p}}\textbf{_2},\textbf{ }\textit{\textbf{p}}\textbf{_3},\textbf{ }\textit{\textbf{p}}\textbf{_4\}}.
\includegraphics{https://static.e-olymp.com/content/08/08f6d4bb51b91370b4688671fdcd02c958b5c8de.jpg}
Figure 1: Full Steiner topology for \textit{\textbf{P}}\textbf{ = \{}\textit{\textbf{p}}\textbf{_1}, \textit{\textbf{p}}\textbf{_2}, \textit{\textbf{p}}\textbf{_3\}}
\includegraphics{https://static.e-olymp.com/content/c8/c81482b89d92f7f1ca3199819105adb8327e317c.jpg}
Figure 2: Full Steiner topologies for \textit{\textbf{P}}\textbf{ = \{}\textit{\textbf{p}}\textbf{_1},\textbf{ }\textit{\textbf{p}}\textbf{_2},\textbf{ }\textit{\textbf{p}}\textbf{_3},\textbf{ }\textit{\textbf{p}}\textbf{_4\}}
Given \textit{\textbf{n}}, the cardinality of \textit{\textbf{P}}, compute the number of distinct full Steiner topologies.
\InputFile
The input contains multiple test cases. Each test case consists of a single integer \textbf{n} (\textbf{3} ≤ \textbf{n} ≤ \textbf{10^7}) on a separate line. The input ends where \textbf{EOF} is met.
\OutputFile
E
For each test case, print the answer on a separate line. You shall print the answer rounded to four significant digits. Let \textbf{m · 10}\textit{\textbf{^e}} be the scientific form of the rounded answer, you shall print "\textbf{me}\textit{"}, giving all four significant digits of \textbf{m} and stripping any leading zeroes before \textbf{e}.
Giriş verilənləri #1
3 30 300 3000 30000 300000 3000000
Çıxış verilənləri #1
1.000E0 8.687E36 5.677E697 1.462E10024 1.983E130306 4.215E1603145 7.937E19031556