Problem : 119 - [Interactive]拯救兔子

Problem Statistics

Solved Member: 9　　Submission: 133　　User Tried: 11

Statement:

請在程式碼加入#include "interactive/119.h"方便與女巫玩遊戲。

大兔子養的一隻小兔子被邪惡的女巫抓走了，很邪惡的女巫把小兔子關在一個 N (N ≤ 1000000000)層的邪惡塔裡的某層樓，塔的樓層由下到上依序由 1 標號到 N。

其實寂寞的女巫只是想要與大兔子玩遊戲，他答應，如果大兔子贏了這場遊戲，就將小兔子還給他；反之，小兔子以及大兔子將被一起變成今晚的佳餚。

遊戲的規則是這樣，大兔子每次能詢問「小兔子被關在 x 樓的樓上/樓下嗎」(不包含 x 樓)，而女巫會回答「是」或者「不是」兩種答案，若答案為「是」，則必須花費 A，若答案為「不是」，則必須花費 B(1 ≤ A,B ≤ 10000)。
若大兔子能在女巫規定的花費之內正確的回答問題，便能獲得這場遊戲的勝利。並且，女巫保證他所規定的花費皆是在運氣最差的情況下也有辦法達成的。

大兔子擔心的天天睡不著覺，也沒辦法好好上課及備課，他決定請你來幫助他解圍，擺脫巫女(誤)的陰謀。

Task:

使用以下的函式來詢問以及回答：

void Init(int *n,int *a,int *b)：初始化 N,A,B的值。

int Ask(char c,int x)：若 c = 'W' 代表詢問小兔子是否在被關在 x 樓上，若 c = 'N' 代表詢問小兔子是否被關在 x 樓下。
其中 x 為 1 到 N 的正整數。若函式回答為「是」，將會回傳1，反之，則回傳0。

void Answer(int x)：回答小兔子在 x 樓，回答完畢程式將自動結束。

Input:Output:

大兔子拜託你別輸入。

女巫拜託你別輸出。

HINT:

範例：

詢問	結果
Init(&n, &a, &b);	n = 5, a = 1, b = 2
Ask('W',3);	回傳0，花費2單位。
Ask('N',2);	回傳0，花費2單位。
Ask('W',2);	回傳1，花費1單位。
Answer(3);	共花費5單位，回答正確。但女巫希望你能在花費4單位以內回答出問題。

Source:

POI 16 Stage 3

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1500ms	32768kb
1-ocen	1500ms	32768kb
1-1	1500ms	32768kb	7
1-2	1500ms	32768kb
1-3	1500ms	32768kb
2-ocen	1500ms	32768kb
2	1500ms	32768kb	7
3-ocen	1500ms	32768kb
3-1	1500ms	32768kb	7
3-2	1500ms	32768kb
3-3	1500ms	32768kb
4-ocen	1500ms	32768kb
4	1500ms	32768kb	7
5-ocen	1500ms	32768kb
5-1	1500ms	32768kb	7
5-2	1500ms	32768kb
5-3	1500ms	32768kb
6	1500ms	32768kb	7
7-1	1500ms	32768kb	7
7-2	1500ms	32768kb
7-3	1500ms	32768kb
8	1500ms	32768kb	7
9	1500ms	32768kb	7
10-1	1500ms	32768kb	7
10-2	1500ms	32768kb
10-3	1500ms	32768kb
11-1	1500ms	32768kb	7
11-2	1500ms	32768kb
11-3	1500ms	32768kb
12-1	1500ms	32768kb	7
12-2	1500ms	32768kb
12-3	1500ms	32768kb
13-1	1500ms	32768kb	8
13-2	1500ms	32768kb
13-3	1500ms	32768kb
14-1	1500ms	32768kb	8
14-2	1500ms	32768kb
14-3	1500ms	32768kb