309521: CF1692H. Gambling

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Gambling

题意翻译

### 题目描述 Marian 在一个赌场,赌场的游戏规则如下: 每一轮开始前,玩家选一个在 $1$ 到 $10^9$ 。然后,掷出一个有着 $10^9$ 面的骰子,会随机出现一个在 $1$ 与 $10^9$ 之间的数。如果玩家猜对了,他们的钱就会翻一番,否则他们的钱会被折半。 Marian 可以预测未来,他知道在接下来 $n$ 轮里骰子上的数,即 $x_1,x_2,...,x_n$。 Marian 会选择三个整数 $a,l$ 和 $r$($l \le r$)。他会玩 $r-l+1$ 轮。每一轮,他都猜同一个数 $a$。一开始(在第 $l$ 轮之前)他有 $1$ 美元。 Marian 请你帮助他决定 $a,l$ 和 $r$($1\le a\le 10^9,1\le l\le r\le n$),让他最后的钱最多。 注:在折半或翻番的过程中不会进行游戏,也不会有精度问题。举个例子,Marian 在游戏中可能会有 $\frac{1}{1024},\frac{1}{128},\frac{1}{2},1,2,4$ 等等(任何可以表示为 $2^t$ 的数,其中 $t$ 为非 $0$ 整数)。 ### 输入格式 第一行包含一个整数 $t$($1\le t\le 100$),即数据的组数。 每组数据的第一行包含一个整数 $n$($1\le n\le 2\times 10^5$)。 每组数据的第二行包含 $n$ 个整数 $x_1,x_2...x_n$($1\le x_i\le 10^9$),$x_i$ 表示骰子在第 $i$ 轮掷出的数字。 数据保证所有数据中的 $n$ 之和不大于 $2\times 10^5$。 ### 输出格式 每组数据输出三个整数 $a,l$ 与 $r$,使得 Marian 能得到最多的钱。如果有多个答案,可以输出它们中的任意一个。 ### 说明/提示 对于第一组数据,最好的选择是 $a=4,l=1,r=5$,游戏会这样进行: - Marian 最开始有 $1$ 美元。 - 第一轮结束后,Marian 会有 $2$ 美元,因为骰子上掷出的数与 Marian 猜的数相同。 - 第二轮结束后,Marian 会有 $4$ 美元,因为他又猜对了。 - 第三轮结束后,Marian 会有 $2$ 美元,因为他猜了 $4$,而 $3$ 是正确答案。 - 第四轮结束后,Marian 又会有 $4$ 美元,因为他又又猜对了。 - 最后一轮结束后,Marian 会 $8$ 美元,因为他又又又猜对了。 第二组数据有多种答案,但可以证明 Marian 最后最多只有 $2$ 美元,因此只要 $l=r$ 且 $a$ 的数字合理,都是正确答案

题目描述

Marian is at a casino. The game at the casino works like this. Before each round, the player selects a number between $ 1 $ and $ 10^9 $ . After that, a dice with $ 10^9 $ faces is rolled so that a random number between $ 1 $ and $ 10^9 $ appears. If the player guesses the number correctly their total money is doubled, else their total money is halved. Marian predicted the future and knows all the numbers $ x_1, x_2, \dots, x_n $ that the dice will show in the next $ n $ rounds. He will pick three integers $ a $ , $ l $ and $ r $ ( $ l \leq r $ ). He will play $ r-l+1 $ rounds (rounds between $ l $ and $ r $ inclusive). In each of these rounds, he will guess the same number $ a $ . At the start (before the round $ l $ ) he has $ 1 $ dollar. Marian asks you to determine the integers $ a $ , $ l $ and $ r $ ( $ 1 \leq a \leq 10^9 $ , $ 1 \leq l \leq r \leq n $ ) such that he makes the most money at the end. Note that during halving and multiplying there is no rounding and there are no precision errors. So, for example during a game, Marian could have money equal to $ \dfrac{1}{1024} $ , $ \dfrac{1}{128} $ , $ \dfrac{1}{2} $ , $ 1 $ , $ 2 $ , $ 4 $ , etc. (any value of $ 2^t $ , where $ t $ is an integer of any sign).

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 2\cdot 10^5 $ ) — the number of rounds. The second line of each test case contains $ n $ integers $ x_1, x_2, \dots, x_n $ ( $ 1 \leq x_i \leq 10^9 $ ), where $ x_i $ is the number that will fall on the dice in the $ i $ -th round. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式


For each test case, output three integers $ a $ , $ l $ , and $ r $ such that Marian makes the most amount of money gambling with his strategy. If there are multiple answers, you may output any of them.

输入输出样例

输入样例 #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

说明

For the first test case, the best choice is $ a=4 $ , $ l=1 $ , $ r=5 $ , and the game would go as follows. - Marian starts with one dollar. - After the first round, he ends up with $ 2 $ dollars because the numbers coincide with the chosen one. - After the second round, he ends up with $ 4 $ dollars because the numbers coincide again. - After the third round, he ends up with $ 2 $ dollars because he guesses $ 4 $ even though $ 3 $ is the correct choice. - After the fourth round, he ends up with $ 4 $ dollars again. - In the final round, he ends up $ 8 $ dollars because he again guessed correctly. There are many possible answers for the second test case, but it can be proven that Marian will not end up with more than $ 2 $ dollars, so any choice with $ l = r $ with the appropriate $ a $ is acceptable.

Input

题意翻译

### 题目描述 Marian 在一个赌场,赌场的游戏规则如下: 每一轮开始前,玩家选一个在 $1$ 到 $10^9$ 。然后,掷出一个有着 $10^9$ 面的骰子,会随机出现一个在 $1$ 与 $10^9$ 之间的数。如果玩家猜对了,他们的钱就会翻一番,否则他们的钱会被折半。 Marian 可以预测未来,他知道在接下来 $n$ 轮里骰子上的数,即 $x_1,x_2,...,x_n$。 Marian 会选择三个整数 $a,l$ 和 $r$($l \le r$)。他会玩 $r-l+1$ 轮。每一轮,他都猜同一个数 $a$。一开始(在第 $l$ 轮之前)他有 $1$ 美元。 Marian 请你帮助他决定 $a,l$ 和 $r$($1\le a\le 10^9,1\le l\le r\le n$),让他最后的钱最多。 注:在折半或翻番的过程中不会进行游戏,也不会有精度问题。举个例子,Marian 在游戏中可能会有 $\frac{1}{1024},\frac{1}{128},\frac{1}{2},1,2,4$ 等等(任何可以表示为 $2^t$ 的数,其中 $t$ 为非 $0$ 整数)。 ### 输入格式 第一行包含一个整数 $t$($1\le t\le 100$),即数据的组数。 每组数据的第一行包含一个整数 $n$($1\le n\le 2\times 10^5$)。 每组数据的第二行包含 $n$ 个整数 $x_1,x_2...x_n$($1\le x_i\le 10^9$),$x_i$ 表示骰子在第 $i$ 轮掷出的数字。 数据保证所有数据中的 $n$ 之和不大于 $2\times 10^5$。 ### 输出格式 每组数据输出三个整数 $a,l$ 与 $r$,使得 Marian 能得到最多的钱。如果有多个答案,可以输出它们中的任意一个。 ### 说明/提示 对于第一组数据,最好的选择是 $a=4,l=1,r=5$,游戏会这样进行: - Marian 最开始有 $1$ 美元。 - 第一轮结束后,Marian 会有 $2$ 美元,因为骰子上掷出的数与 Marian 猜的数相同。 - 第二轮结束后,Marian 会有 $4$ 美元,因为他又猜对了。 - 第三轮结束后,Marian 会有 $2$ 美元,因为他猜了 $4$,而 $3$ 是正确答案。 - 第四轮结束后,Marian 又会有 $4$ 美元,因为他又又猜对了。 - 最后一轮结束后,Marian 会 $8$ 美元,因为他又又又猜对了。 第二组数据有多种答案,但可以证明 Marian 最后最多只有 $2$ 美元,因此只要 $l=r$ 且 $a$ 的数字合理,都是正确答案

Output

**题目大意:**

Marian 在一个赌场玩一个游戏,游戏规则如下:

- 每一轮开始前,玩家选择一个 $1$ 到 $10^9$ 之间的数。
- 然后,掷出一个有 $10^9$ 面的骰子,随机出现一个 $1$ 到 $10^9$ 之间的数。
- 如果玩家猜对了,他们的钱就会翻一番;否则,他们的钱会被折半。

Marian 可以预测未来,他知道接下来 $n$ 轮骰子上的数,即 $x_1,x_2,...,x_n$。

Marian 会选择三个整数 $a, l$ 和 $r$($l \le r$),他会玩 $r-l+1$ 轮。每一轮,他都猜同一个数 $a$。一开始(在第 $l$ 轮之前)他有 $1$ 美元。

你的任务是帮助Marian决定 $a, l$ 和 $r$($1 \le a \le 10^9, 1 \le l \le r \le n$),以使最后的钱最多。

**输入输出数据格式:**

**输入格式:**

- 第一行包含一个整数 $t$($1 \le t \le 100$),即数据的组数。
- 每组数据的第一行包含一个整数 $n$($1 \le n \le 2 \times 10^5$)。
- 每组数据的第二行包含 $n$ 个整数 $x_1,x_2,...,x_n$($1 \le x_i \le 10^9$),$x_i$ 表示骰子在第 $i$ 轮掷出的数字。
- 保证所有数据中的 $n$ 之和不大于 $2 \times 10^5$。

**输出格式:**

- 对于每组数据,输出三个整数 $a, l$ 和 $r$,使得Marian能得到的钱最多。如果有多个答案,可以输出它们中的任意一个。**题目大意:** Marian 在一个赌场玩一个游戏,游戏规则如下: - 每一轮开始前,玩家选择一个 $1$ 到 $10^9$ 之间的数。 - 然后,掷出一个有 $10^9$ 面的骰子,随机出现一个 $1$ 到 $10^9$ 之间的数。 - 如果玩家猜对了,他们的钱就会翻一番;否则,他们的钱会被折半。 Marian 可以预测未来,他知道接下来 $n$ 轮骰子上的数,即 $x_1,x_2,...,x_n$。 Marian 会选择三个整数 $a, l$ 和 $r$($l \le r$),他会玩 $r-l+1$ 轮。每一轮,他都猜同一个数 $a$。一开始(在第 $l$ 轮之前)他有 $1$ 美元。 你的任务是帮助Marian决定 $a, l$ 和 $r$($1 \le a \le 10^9, 1 \le l \le r \le n$),以使最后的钱最多。 **输入输出数据格式:** **输入格式:** - 第一行包含一个整数 $t$($1 \le t \le 100$),即数据的组数。 - 每组数据的第一行包含一个整数 $n$($1 \le n \le 2 \times 10^5$)。 - 每组数据的第二行包含 $n$ 个整数 $x_1,x_2,...,x_n$($1 \le x_i \le 10^9$),$x_i$ 表示骰子在第 $i$ 轮掷出的数字。 - 保证所有数据中的 $n$ 之和不大于 $2 \times 10^5$。 **输出格式:** - 对于每组数据,输出三个整数 $a, l$ 和 $r$,使得Marian能得到的钱最多。如果有多个答案,可以输出它们中的任意一个。

加入题单

上一题 下一题 算法标签: