GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Tuesday 14 June 2022

[Solution] Gambling Codeforces Solution | Codeforces Problem Solution 2022

H. Gambling
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Marian is at a casino. The game at the casino works like this.

Before each round, the player selects a number between 1 and 109. After that, a dice with 109 faces is rolled so that a random number between 1 and 109 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 x1,x2,,xn that the dice will show in the next n rounds.

He will pick three integers al and r (lr). He will play rl+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.

Solution Click Below:-  CLICK HERE

Marian asks you to determine the integers al and r (1a1091lrn) 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 11024112812124, etc. (any value of 2t, where t is an integer of any sign).

Input

The first line contains a single integer t (1t100) — the number of test cases.

The first line of each test case contains a single integer n (1n2105) — the number of rounds.

The second line of each test case contains n integers x1,x2,,xn (1xi109), where xi 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 2105.

Output

For each test case, output three integers al, 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.

No comments:

Post a Comment