Description

單循環路線公車,指的是公車在市區端透過繞行多段單行路線折返,如此一來就不用在市區內設置公車總站。下圖為聯營88路公車的路線圖,可以看到該路線公車在台北車站端,即透過一段總共三個車站(捷運台大醫院站、台北車站(青島)、臺大醫院)的單循環線進行折返。

AaW 非常喜歡單循環線公車。為什麼呢?因為AaW太常因為太專心看手機或是跟短尾矮袋鼠打架,而不小心公車坐過站了。不過,只要一條公車是單循環線,那就算坐過頭也可以坐回來。
因此,AaW 決定將所有的公車都改成單循環線。具體來說,AaW所規劃的公車路線圖如下:

  • 一路公車總共有 a 站雙向站,b 站單循環線站
  • 公車總站數 n=2a+b
  • 相異站數 m=a+b
  • 公車每個皆有一個 ID,ID 保證為介於1200000 之間的正整數,但不會按照順序
  • 總站(位於非循環線端)的 ID 為 1
  • 原本 AaW 想要保證 an,但AaW不會數學,所以a40

設計完整套公車系統之後,AaW順便開發了一個公車App,然後他就很開心的去出別題題目了。

大家都知道,蔡摩卡是檸檬家裡的貓,
她的脾氣不太好,然後一直把沙發抓破。
但是,因為他太可愛了,所以你決定要跟檸檬借回家養個幾天。
為了預防他又鑽進紙箱裡,你已經把家裡所有紙箱都收起來了。
可是沒想到,他竟然趁你不注意的時候溜到街上的公車站裡,然後坐上1558路公車逃跑了。
聰明的你,立刻想要找一群最佳汪汪隊 Repkironca 來幫你抓貓。 Repkironca 會使用一種叫做 大步小步連滾帶爬 的技巧來找貓,非常厲害。
但是,每位 Repkironca 只能幫你尋找一個車站,而如果你找來太多 Repkironca 你會瘋掉,因此你決定使用 AaW 的公車APP來幫你找出總共有幾個相異車站。

無奈,老天爺不只愛跟你開玩笑,還很愛把系統開根號。
由於AaW不會寫程式,所以他寫的 APP 只有兩個功能,兩個都還有bug:
1. 詢問路線總站數 n ,但此功能只有約 40% 的成功率。
2. 詢問從總站 正向/逆向k 站公車會到哪一站,但此功能只能執行 90 次,超過這個次數,你的上機考成績會直接爛掉。

請問,你有辦法利用以上函式,求出這條公車路線 雙向站a單向站b 的數值嗎?

Input Format

本題為互動題,請不要輸入/輸出任何資料,以免發生

請在你程式當中,加上一行:
#include "lib4544.h"

在此標頭檔當中,你可以使用以下三個函數。


int init();

請在你的主程式的最一開始呼叫這個函數。
此函數會回傳一個數值 n ,代表公車總站數。
但他有可能不會回傳 n,而是回傳 1,代表你要自己想辦法求出n為多少。
不論有沒有直接回傳給你,保證 n 為偶數。


int query(int k);

此函數代表可詢問你從總站(ID=1)搭公車 k 站到的車站的ID。
k 為 0,程式會回傳1,即從總站搭車 0 站還是在總站,因此回傳ID = 1。
k 為正整數,程式會回傳你 順向|k| 站會是哪一站。
k 為負整數,程式會回傳你 逆向|k| 站會是哪一站。
|k|n ,即代表你坐過頭到總站裡面去了,程式會回傳的數字。

以上面Statement中的圖為例:
query(8) = 17,而query(-8)則為69
query(0) = query(21) = query(-21) = 1,因為坐0站、正著坐21站和反著做21站都會回到總站。
query(1) = query(20) = query(-1) = 2query(9) = query(-12) = 18

再次提醒,本函數呼叫次數有上限。


void report(int a, int b);

本函數只能呼叫一次,用來回傳你算出來的答案 ab
保證題目中 a40

Output Format

void report(int a, int b);

請呼叫此函數一次,用來回傳你算出來的答案 ab

本題一共有4個subtask
- Subtask 1. (4%):n90
- Subtask 2. (12%):n160
- Subtask 3. (36%):n1000init會回傳給你 n
- Subtask 4. (48%):n1000
- 對於所有Subtask,保證中 a40

對於每一筆測資,其分數跟一個指數t有關
- 若a,b正確且query次數90t=1.0
- 若a,b正確但query次數>90t=max(log2.2(90)log2.2(x)+1,0.0) *
- 若a,b錯誤,t=0.0

Hints

一個合法但保證沒有任何分數的程式如下

#include <iostream>
#include "lib4544.h"

int main() {
    int n = init();
    for (int i = 0; i < 90; ++i) {
        int k = query(0);
    }
    report(1558, 48763);
    return 0;
}

Subtasks

No. Testdata Range Constraints Score
1 0~1 n90 4
2 2~7 n160 12
3 8~25 n1000init會回傳給你 n 36
4 26~48 Subtask 4. (48%):n1000 48

TopCoder

807

User's AC Ratio

100.0% (5/5)

Tags

Problem Source

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 2
3 1000 65536 65536 2
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 3
9 1000 65536 65536 3
10 1000 65536 65536 3
11 1000 65536 65536 3
12 1000 65536 65536 3
13 1000 65536 65536 3
14 1000 65536 65536 3
15 1000 65536 65536 3
16 1000 65536 65536 3
17 1000 65536 65536 3
18 1000 65536 65536 3
19 1000 65536 65536 3
20 1000 65536 65536 3
21 1000 65536 65536 3
22 1000 65536 65536 3
23 1000 65536 65536 3
24 1000 65536 65536 3
25 1000 65536 65536 3
26 1000 65536 65536 4
27 1000 65536 65536 4
28 1000 65536 65536 4
29 1000 65536 65536 4
30 1000 65536 65536 4
31 1000 65536 65536 4
32 1000 65536 65536 4
33 1000 65536 65536 4
34 1000 65536 65536 4
35 1000 65536 65536 4
36 1000 65536 65536 4
37 1000 65536 65536 4
38 1000 65536 65536 4
39 1000 65536 65536 4
40 1000 65536 65536 4
41 1000 65536 65536 4
42 1000 65536 65536 4
43 1000 65536 65536 4
44 1000 65536 65536 4
45 1000 65536 65536 4
46 1000 65536 65536 4
47 1000 65536 65536 4
48 1000 65536 65536 4