本題沒有輸入，請引入 lib0046.h，並且實作函式 void solve(int problem_type)。problem_type 會是一個 $1$ 到 $4$ 的數字，決定問題的類型（和上面敘述同）。請依照該問題類型呼叫題目敘述中的操作。

本地測試細節

請下載 abacus.zip，裡面會有一些檔案。
檔案的意義分別為：

• abacus.cpp：這是你要寫的程式，並且最後繳交的檔案。
• lib0046.h：你的程式和 grader.cpp 會引入的標頭檔。
• grader.cpp：範例評分程式。
• compile.sh, compile.bat 在用 Linux/Windows 時，可以執行它來在電腦上編譯。

執行範例評分程式時，先輸入一個 $1$ 到 $4$ 的整數 problem_type，代表問題的類型。然後再輸入一個浮點數 $x$ 代表要測試的數字。評分程式會呼叫 solve 並且用 $x$ 來計算，並且判斷結果是否正確。如果輸出為 "... out of range"，就代表你呼叫的操作的某個數字不在正確範圍內。如果輸出為 "WA: ..." 則你計算的答案不正確，如果輸出為 "AC: ..."，代表輸出的答案正確。

請不要嘗試撰寫題目指定需要函式以外的任何東西，例如自行輸入、輸出等。grader.cpp 可能與實際使用的評分程式上有落差。

除了題目中的操作之外，你還可以呼叫

• print(int x)，Debug 用，會在本地測試時將 $a_x$ 目前的數值印出。
• printstr(int x)，Debug 用，會在本地測試時將 $a_x$ 的二進位 $a_{x,0}{a}_{x,1}\dots$ 印出。 這兩個操作不會被算在總操作次數內，直接上傳含有這兩個操作的程式碼也不會有錯。

舉例來說，如果輸入是：

1
2.36

那麼一個正確的程式可能會輸出：

Total Operations: 8
Error: 0.0000000192
AC: Calculated 4.7199999094, Judge Answer 4.7200000000

請不要輸入任何東西到標準輸出串 (stdout)，否則會出現不可預期的後果。計算完成時，請呼叫 void answer(int x) 來回答，x 代表最終算完的答案是 $a_x$。answer() 只能被呼叫一次，否則你會獲得 Wrong Answer。

評分方式

假設 $Q$ 是你的程式在某一種問題總共呼叫的操作數（不含 print、printstr、answer）。該子題的得分會是子題總分乘上比例 $p$。

• 如果 $Q\le 512$，則 $p=1.0$。
• 如果 $512<Q\le 768$，則 $p=1-\frac{Q-512}{256}$。
• 如果 $768<Q$，則 $p=0$。

評測程式會將若干組 $x$ 的輸入用你的計算步驟得到對應的輸出。對於每個輸出，答案會被視為正確若絕對或相對誤差小於 ${10}^{-5}$。所有輸入的答案都需要是正確的才能拿到該子題的分數。

在遇到 Sine 問題時，雞塊想起了他學過的 CORDIC 演算法，敘述如下：

對於一個二維向量 $\overrightarrow{v}=\left(\begin{array}{c}x\\ y\end{array}\right)$，假設 $\overrightarrow{v}$ 與 $x$ 軸正向夾 $\theta$ 角，則 $\sin (\theta )=\frac{y}{\sqrt{x^2+y^2}},\cos (\theta )=\frac{x}{\sqrt{x^2+y^2}}$。如果要對 $\overrightarrow{v}$ 旋轉 $\varphi$ 度，則和角公式告訴我們

$\cos (\theta +\varphi )=\cos (\varphi )\cos (\theta )-\sin (\varphi )\sin (\theta )$
$\sin (\theta +\varphi )=\sin (\varphi )\cos (\theta )+\cos (\varphi )\sin (\theta )$

所以對應的旋轉矩陣為

$M=\left(\begin{array}{cc}\cos (\varphi )& -\sin (\varphi )\\ \sin (\varphi )& \cos (\varphi )\end{array}\right)$

也就是說，$M\overrightarrow{v}$ 會是 $\overrightarrow{v}$ 向逆時針旋轉 $\varphi$ 度之後得到的向量。我們可以將 $\cos (\varphi )$ 提出得到

$M=\cos (\varphi )\left(\begin{array}{cc}1& -\tan (\varphi )\\ \tan (\varphi )& 1\end{array}\right)$

如果我們想要旋轉 $\theta$ 度，可以把它拆成一些角度 ${\varphi }_0,{\varphi }_1,\dots$ 的組合。更進一步的，我們可以使用「神奇序列」 ${\varphi }_0={45}^{\circ }=\mathrm{atan}(1),{\varphi }_1=\mathrm{atan}(\frac{1}{2}),\dots ,{\varphi }_i=\mathrm{atan}(2^{-i})$（註：$\mathrm{atan}(x)$ 是 $\tan$ 的反函數，會符合 $\tan (\mathrm{atan}(x))=x$）。因為 $\mathrm{\forall }i\ge 0,{\varphi }_i\le 2\times {\varphi }_{i+1}$，所以我們可以用倍增的方式，把任何一個 $0$ 到 $90$ 度的角度 $\theta$ 用一些 ${\varphi }_i$ 乘上 $1$ 或 $-1$ 的和來估計。而且，對於某個 ${\varphi }_i$，對應的旋轉矩陣 $M_i$ 會變成

$M_i=\cos ({\varphi }_i)\left(\begin{array}{cc}1& -2^{-i}\\ 2^{-i}& 1\end{array}\right)$

如果我們選固定的 $N$ 項 ${\varphi }_i$ 來估計此角度（以 $N=30$ 舉例），那麼我們可以預處理 $K=\prod _{i=0}^{29}\cos ({\varphi }_i)$。一開始先令 $\overrightarrow{v}=\left(\begin{array}{c}1\\ 0\end{array}\right)$，角度 $\alpha =0$。那如果 $\alpha <\theta$，就將 $\overrightarrow{v}$ 乘上 $\left(\begin{array}{cc}1& -2^{-i}\\ 2^{-i}& 1\end{array}\right)$，否則可以做相反方向的旋轉，乘上$\left(\begin{array}{cc}1& 2^{-i}\\ -2^{-i}& 1\end{array}\right)$。最後再把 $\overrightarrow{v}$ 乘以常數 $K$ 之後取 $y$ 值就是答案。

對於 Log 問題，可以用類似的方法解決，而前面提到的「神奇序列」可以改為 $8,4,2,\frac{3}{2},\frac{5}{4},\frac{9}{8},\dots$，做法就請各位自己想想囉 :)

IOICamp 2024 Day5 pD
題敘靈感：https://twitter.com/kuma_d_fes/status/1730817079450960143
Inspiration: https://www.youtube.com/watch?v=bre7MVlxq7o&t=934s
Grader 參考自 APIO 2023 pC - Alice, Bob, and Circuit