← 返回题目列表

Codeforces · 1692/H

H. 赌博

中文机器翻译题面 查看原题

玛丽安在赌场。赌场的游戏是这样进行的。

每轮之前,玩家选择 $$$1$$$ 和 $$$10^9$$$ 之间的数字。之后,滚动一个面为 $$$10^9$$$ 的骰子,从而出现 $$$1$$$ 和 $$$10^9$$$ 之间的随机数。如果玩家猜对了数字,他们的总钱就会加倍,否则他们的总钱就会减半。

Marian 预测了未来,并且知道骰子在接下来的 $$$n$$$ 轮中将显示的所有数字 $$$x_1, x_2, \dots, x_n$$$。

他将选择三个整数 $$$a$$$、$$$l$$$ 和 $$$r$$$ ($$$l \leq r$$$)。他将打 $$$r-l+1$$$ 轮(包括 $$$l$$$ 和 $$$r$$$ 之间的轮次)。在每一轮中,他都会猜测相同的数字$$$a$$$。开始时(在 $$$l$$$ 回合之前)他有 $$$1$$$ 美元。

Marian 要求你确定整数 $$$a$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \leq a \leq 10^9$$$, $$$1 \leq l \leq r \leq n$$$),这样他最后赚的钱最多。

请注意,在减半和乘法过程中,没有舍入,也没有精度误差。因此,例如在游戏过程中,Marian 的资金可能等于 $$$\dfrac{1}{1024}$$$、$$$\dfrac{1}{128}$$$、$$$\dfrac{1}{2}$$$、$$$1$$$、$$$2$$$、$$$4$$$ 等($$$2^t$$$ 的任意值,其中 $$$t$$$ 是任何标志)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) — 轮数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$1 \leq x_i \leq 10^9$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 轮中骰子上的数字。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,输出三个整数 $$$a$$$、$$$l$$$ 和 $$$r$$$,以便 Marian 通过他的策略赌博赚到最多的钱。如果有多个答案,您可以输出其中任何一个。

示例

输入 #1

4
5
4 4 3 4 4
5
11 1 11 1 11
1
1000000000
10
8 8 8 9 9 6 6 9 6 6

输出 #1

4 1 5
1 2 2
1000000000 1 1
6 6 10

注意

对于第一个测试用例,最佳选择是 $$$a=4$$$、$$$l=1$$$、$$$r=5$$$,游戏将如下进行。

- 玛丽安从一美元开始。
- 第一轮结束后,他最终获得​​了 $$$2$$$ 美元,因为数字与所选数字一致。
- 第二轮结束后,他最终获得​​了 $$$4$$$ 美元,因为数字再次重合。
- 第三轮结束后,他最终得到了 $$$2$$$ 美元,因为他猜测 $$$4$$$,尽管 $$$3$$$ 是正确的选择。
- 第四轮结束后,他再次获得 $$$4$$$ 美元。
- 在最后一轮中,他最终赢得了 $$$8$$$ 美元,因为他再次猜对了。

第二个测试用例有很多可能的答案,但可以证明 Marian 最终不会得到超过 $$$2$$$ 美元,因此 $$$l = r$$$ 以及适当的 $$$a$$$ 的任何选择都是可以接受的。