TopCoder

807
$\huge\boxed{學長對不起}$

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

41.3% (57/138)

Tags

Description

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

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

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

設計完整套公車系統之後,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| \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) = 2query(9) = query(-12) = 18

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


void report(int a, int b);

本函數只能呼叫一次,用來回傳你算出來的答案 $a$ 和 $b$。
保證題目中 $a \ge 40$

Output Format

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$

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;
}

Problem Source

Subtasks

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

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