2211 . 函數愛蛋餅
TopCoder
Tags
Description
蛋餅是個熱愛函數的建中學生，無論是多項式函數、三角函數、指對數函數，蛋餅都研究得十分透徹。最近他發現了一個十分有趣的函數，決定好好研究一番。
這個函數十分的特別，他的輸入只能是一個介於$1$到$N$之間的正整數，而他的輸出也會是一個介於$1$到$N$之間的正整數。更特別的是，任意兩個不一樣的數字代入函數當中，得到的輸出都不相同。
蛋餅最喜歡對函數做一件事，他把這件事稱作「函數的迭代」。具體來說，就是把剛從函數得到的值，再代入函數。一個數對某個函數的「$k$次迭代」就是指將一個數連續代入函數$k$次，所得到的值。舉例來說，蛋餅有個數字叫做$x$，那麼$x$的零次迭代就是$x$，$x$的一次迭代就是$f(x)$，$x$的二次迭代就是$f(f(x))$或記作$f^ 2(x)$，$x$的三次迭代就是$f(f(f(x)))$或記作$f^ 3 (x)$...以此類推。
由於上一次你幫忙他寫了一個程式分析函數，蛋餅感到十分感激，作為回報，他問了你以下的問題：
「如果我可以每次詢問$f^ b(a)$是多少，那我有沒有辦法在$800$次以內的詢問找到唯一的$y$，使得$f(y)=1$呢?」
請寫一個程式，解決這個問題。
Input Format
本題是互動題，請在程式碼的開頭引入標頭檔 #include "lib2211.h"，程式碼請勿輸入或輸出任何東西。如果你輸入了任何東西可能會導致各種不可預期的結果。
可以呼叫以下函式:
int Init(): 請在開頭呼叫本函式一次，回傳值為一個整數$n$，代表$f$的範圍。對於所有測資，$n \leq 10 ^ 5 $
int Query(int a, int b): 輸入為兩個整數 $a, b$，其中須符合$1 \leq a, b \leq N$，回傳為一個整數，代表 $f ^ b(a)$ 的值。此函式若呼叫超過800次，你會得到一個WA。
void Report(int a): 輸入為一個整數 $a$，代表你的答案，如果不滿足$1 \leq a \leq N$，或是$f(a) \neq 1$，你會得到一個WA。請在呼叫本函式之後終止程式。
Output Format
本題沒有任何輸出。
Hints
以下是一個可以編譯（但一定不會答對）的範例程式碼:
#include <iostream>
#include "lib2211.h"
using namespace std;
int main() {
int n = Init();
int q = Query(1, n - 1);
Report(q);
}
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $n \leq 800$ | 36 |
| 2 | 0~24 | 無其他限制 | 64 |