TopCoder

Thumb uexby4s
Achi_kyw
對不起我只具備基礎程式能力

User's AC Ratio

75.0% (27/36)

Submission's AC Ratio

15.6% (62/397)

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

本題沒有任何輸出。

Sample Input

Sample Output

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 2
1 1000 131072 65536 1 2
2 1000 131072 65536 1 2
3 1000 131072 65536 1 2
4 1000 131072 65536 1 2
5 1000 131072 65536 1 2
6 1000 131072 65536 1 2
7 1000 131072 65536 1 2
8 1000 131072 65536 1 2
9 1000 131072 65536 1 2
10 1000 131072 65536 2
11 1000 131072 65536 2
12 1000 131072 65536 2
13 1000 131072 65536 2
14 1000 131072 65536 2
15 1000 131072 65536 2
16 1000 131072 65536 2
17 1000 131072 65536 2
18 1000 131072 65536 2
19 1000 131072 65536 2
20 1000 131072 65536 2
21 1000 131072 65536 2
22 1000 131072 65536 2
23 1000 131072 65536 2
24 1000 131072 65536 2