题目描述

题目译自 XVI OI Olimpiada Informatyczna – III etap Poszukiwania

年轻且深陷爱河的 Bajtek 和 Bajtyna 遭遇了巨大困境。邪恶的巫师 Bitocy 绑架了 Bajtyna，企图索取巨额赎金。Bajtek 不愿屈服——他并不富有，决定亲自救回心上人。Bitocy 厌恶近身战斗，提出另一种解决方案：若 Bajtek 能猜中 Bajtyna 被囚禁的塔楼楼层，巫师将放人。

塔楼楼层众多，从 $1$ 到 $n$ 编号。Bajtek 唯一的线索是向巫师提问，问题形式为「Bajtyna 是否在第 $x$ 层以上/以下？」。Bajtek 可选择「以上」或「以下」，并任意指定 $x$。Bitocy 总是如实回答，回答是需支付 $a$ 拜塔拉，否需支付 $b$ 拜塔拉。然而，若 Bajtek 花费过多而 Bitocy 大赚一笔，Bajtyna 可能选择留在巫师身边……

Bajtek 需谨慎选择提问策略。不幸的是，Bajtyna 能听到全部对话，包括 Bajtek 的问题和 Bitocy 的回答。她极为节俭，若 Bajtek 的花费（在最坏情况下）比确定她位置所需的最少拜塔拉多出哪怕 $1$，她将彻底生气并投向 Bitocy。具体而言，若某时刻对话表明，从此刻起，无论 Bitocy 如何回答，Bajtek 最多花费 $K$ 拜塔拉即可确定 Bajtyna 位置，但之后他花费超过 $K$，则他将彻底失去 Bajtyna（该测试得 $0$ 分）。请帮助 Bajtek！

交互方式

你需实现一个程序，利用提供的库（模拟巫师 Bitocy）解决 Bajtek 的问题。要使用库，程序需包含：

• C/C++：#include "poslib.h"
• Pascal：uses poslib;

库提供以下三个函数：

• inicjuj：返回楼层数 $n$ 及费用 $a, b$。程序开始时必须且仅调用一次。
  • C/C++：void inicjuj(int *n, int *a, int *b);
  • Pascal：procedure inicjuj(var n, a, b: longint);
• pytaj：参数 $c$ 表示问题类型（W 表示「以上」，N 表示「以下」），$x$ 为楼层编号。返回巫师的布尔回答。可多次调用。
  • C/C++：int pytaj(char c, int x);（$0$ 表示假，$1$ 表示真）
  • Pascal：function pytaj(c: char; x: longint): boolean;
• odpowiedz：通过此函数提交 Bajtyna 所在楼层编号。必须且仅调用一次，调用后程序终止。
  • C/C++：void odpowiedz(int wynik);
  • Pascal：procedure odpowiedz(wynik: longint);

程序不得打开文件或使用标准输入输出。解决方案将与库一起编译，命令如下：

• C：gcc -O2 -static poslib.c pos.c -lm
• C++：g++ -O2 -static poslib.c pos.cpp -lm
• Pascal：ppc386 -O2 -XS -Xt pos.pas

示例库文件和代码位于「文件」中，展示库用法。编译时，库文件需在当前目录。

样例

上述交互正确但非最优，故不会得分。优化的程序可在 $n=5, a=1, b=2$ 时，确保最坏情况下花费不超过 $4$ 拜塔拉。

数据范围与提示

$1 \leq n \leq 10^9$，$1 \leq a, b \leq 10000$。