Strength Contest
Time limit1sMemory limit256 MB
For each split of a line of fighters into a left and right team, the max of each side fights; count which side wins more splits, or report a tie.
- Level
Medium5 of 10
- Topics
- Prefix sum, Array, Implementation, Brute force
- Solved
- No attempts yet
Problem
Mr. Strong, once famous as a fighter, organized a tournament called "Strength Contest" and advertised it nationwide. Many people gathered from all over the country after seeing the recruitment notice, but the notice never defined what "strength" means, which caused confusion.
People came with all kinds of strength, from muscular men who lift a combined total of 500 kg across the bench press, squat, and deadlift, to people with a high Strength (STR) stat in a famous RPG.
Mr. Strong suddenly recalled the famous saying, "Knowledge is power." He quantified the participants' strength through a trivia quiz in the preliminaries, and decided to select the finalists based on this number.
In this way, N participants advanced to the finals. However, contrary to expectations, the finals were held as a team match between two teams, the Red Team and the Blue Team.
The N participants stand in a single line. Mr. Strong will draw one ball at random from a box containing balls numbered 1 through N−1 to determine the dividing line. For example, if he draws the ball numbered 3, the dividing line falls between participants 3 and 4. Everyone to the left of the line is on the Red Team, and everyone to the right is on the Blue Team.
The game is a single round. The strongest person from each team steps forward and the two compete in strength. The stronger person wins and the game ends. If their strengths are equal, nobody wins.
Gambler Kim (hereafter Dr. Gamble) obtained the participant list before the game began! Now that he can tell in advance which team will win based on the position of the dividing line, Dr. Gamble plans to bet his entire fortune on the side with the higher chance of winning. Which team should Dr. Gamble bet his entire fortune on?
The dividing line can only fall between two participants, and each team must have at least one person.
Input
The first line gives the number of people N. N is even and less than or equal to 1,000,000.
The second line gives integers representing the strength of person 1 through person N. Each person's strength is a positive integer less than or equal to 10,000.
Output
If Dr. Gamble should bet on the Red Team, output R; if he should bet on the Blue Team, output B. If the two teams have an equal chance of winning, output X.