單循環路線公車,指的是公車在市區端透過繞行多段單行路線折返,如此一來就不用在市區內設置公車總站。下圖為聯營88路公車的路線圖,可以看到該路線公車在台北車站端,即透過一段總共三個車站(捷運台大醫院站、台北車站(青島)、臺大醫院)的單循環線進行折返。
AaW 非常喜歡單循環線公車。為什麼呢?因為AaW太常因為太專心看手機或是跟短尾矮袋鼠打架,而不小心公車坐過站了。不過,只要一條公車是單循環線,那就算坐過頭也可以坐回來。
因此,AaW 決定將所有的公車都改成單循環線。具體來說,AaW所規劃的公車路線圖如下:
設計完整套公車系統之後,AaW順便開發了一個公車App,然後他就很開心的去出別題題目了。
大家都知道,蔡摩卡是檸檬家裡的貓,
她的脾氣不太好,然後一直把沙發抓破。
但是,因為他太可愛了,所以你決定要跟檸檬借回家養個幾天。
為了預防他又鑽進紙箱裡,你已經把家裡所有紙箱都收起來了。
可是沒想到,他竟然趁你不注意的時候溜到街上的公車站裡,然後坐上1558路公車逃跑了。
聰明的你,立刻想要找一群最佳汪汪隊 $Repkironca$ 來幫你抓貓。 $Repkironca$ 會使用一種叫做 大步小步連滾帶爬 的技巧來找貓,非常厲害。
但是,每位 $Repkironca$ 只能幫你尋找一個車站,而如果你找來太多 $Repkironca$ 你會瘋掉,因此你決定使用 AaW 的公車APP來幫你找出總共有幾個相異車站。
無奈,老天爺不只愛跟你開玩笑,還很愛把系統開根號。
由於AaW不會寫程式,所以他寫的 APP 只有兩個功能,兩個都還有bug:
1. 詢問路線總站數 $n$ ,但此功能只有約 40% 的成功率。
2. 詢問從總站 正向/逆向 坐 $k$ 站公車會到哪一站,但此功能只能執行 90 次,超過這個次數,你的上機考成績會直接爛掉。
請問,你有辦法利用以上函式,求出這條公車路線 雙向站$a$ 和 單向站$b$ 的數值嗎?
本題為互動題,請不要輸入/輸出任何資料,以免發生無法預期的錯誤。
請在你程式當中,加上一行:
#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| \ge n$ ,即代表你坐過頭到總站裡面去了,程式會回傳無法預期的數字。
以上面Statement中的圖為例:
query(8) = 17
,而query(-8)
則為69
query(0)
= query(21)
= query(-21)
= 1,因為坐0站、正著坐21站和反著做21站都會回到總站。
而query(1) = query(20) = query(-1) = 2
,query(9) = query(-12) = 18
再次提醒,本函數呼叫次數有上限。
void report(int a, int b);
本函數只能呼叫一次,用來回傳你算出來的答案 $a$ 和 $b$。
保證題目中 $a \ge 40$
void report(int a, int b);
請呼叫此函數一次,用來回傳你算出來的答案 $a$ 和 $b$。
本題一共有4個subtask
- Subtask 1. (4%):$n \le 90$
- Subtask 2. (12%):$n \le 160$
- Subtask 3. (36%):$n \le 1000$ 且init
會回傳給你 $n$
- Subtask 4. (48%):$n \le 1000$
- 對於所有Subtask,保證中 $a \ge 40$
對於每一筆測資,其分數跟一個指數$t$有關
- 若$a, b$正確且query
次數$\le 90$,$t=1.0$
- 若$a, b$正確但query
次數$> 90$,$t=\max(\log_{2.2}(90)-\log_{2.2}(x)+1,\; 0.0)$ *
- 若$a, b$錯誤,$t=0.0$
一個合法但保證沒有任何分數的程式如下
#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;
}
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | $n \le 90$ | 4 |
2 | 2~7 | $n \le 160$ | 12 |
3 | 8~25 | $n \le 1000$ 且init 會回傳給你 $n$ |
36 |
4 | 26~48 | Subtask 4. (48%):$n \le 1000$ | 48 |