An Animal Contest 3 P3 - Monkey Market

View as PDF

Points: 7
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Steven the monkey recently discovered something called the monkey stock market. He is given an array of integers. Each integer denotes the price of one stock share on the day. On each day he can:

• Spend all his money to buy stock shares. He gains shares, where denotes the amount of money he has. Then becomes .
• Sell all the shares he currently has. He gains dollars, where denotes the number of shares he has. Then becomes .
• Don't take action.

Being an extremely popular monkey influencer, he can control the stock market by reordering the stock prices any way he wants.

However, he is an extremely busy monkey, so he hires you to help him determine an order of the prices such that if he acts optimally, he can maximize the amount of money he has by the end of the days. Given that he starts with no stocks and an undetermined amount of money, output a list of directions as to which days he should buy, sell or skip on.

Input Specification

The first line contains the integer , the number of days.

The next line contains the space-separated integers .

Output Specification

On the first line, output some optimal permutation of the original array. On the next line, output letters without spaces in between — the letter denoting the action performed on the day, which is either B for buying, S for selling, or E for skipping. Remember that having shares is not the same as having money.

Note: Any valid output will be accepted.

Sample Input

3
4 2 2

Sample Output

2 2 4
BES

Explanation

Say we start with dollars. We first buy, so we end up with stocks. On the second day, we skip, and on the last day, we sell to obtain a total of dollars. This arrangement can be proven to be optimal.

• commented on Feb. 23, 2024, 3:17 a.m.

im not good w ad hoc is the optimal strat for the last 2 days to buy on the cheapest price, then sell on the highest price?

• commented on Feb. 23, 2024, 2:50 a.m. edited

What is it with the Presentation Error?

• commented on Nov. 29, 2022, 11:16 p.m. edited

My answer is in complexity but is considered too slow... Is it because I code in Python ?

• commented on Aug. 4, 2021, 4:15 a.m.

Steven 🤓 the monkey 🐒 on 👉👉 the 🙄 sigma ∑ male 😤🥵 grind 💪💪🏻💪🏼💪🏽💪🏾💪🏿 set 💸🤑💰💰💰