本題沒有輸入，請引入 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 \leq 512$，則 $p = 1.0$。
• 如果 $512 < Q \leq 768$，則 $p = 1 - \frac{Q - 512}{256}$。
• 如果 $768 < Q$，則 $p = 0$。

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

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

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

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

所以對應的旋轉矩陣為

$M = \begin{pmatrix}
\cos(\phi) & -\sin(\phi) \\
\sin(\phi) & \cos(\phi)
\end{pmatrix}$

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

$M = \cos(\phi) \begin{pmatrix}
1 & -\tan(\phi) \\
\tan(\phi) & 1
\end{pmatrix}$

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

$M_i = \cos(\phi_i) \begin{pmatrix}
1 & -2^ {-i} \\
2^ {-i} & 1
\end{pmatrix}$

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

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

題敘靈感：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