DMPG '16 G1 - Explooooosion! - Olympiads Online Judge

DMPG '16 G1 - Explooooosion!

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

FatalEagle

Problem type

Megumin loves magical explosions. Since you are Megumin's most trusted adviser, you want to help her to create the most spectacular explosion ever.

Megumin currently has $N$ ~N~ magical components that must all be combined together to create an explosion. However, Megumin can combine the components in any order she wants, and the specific order which she does this will result in a differing size of the resulting explosion.

Each component $i$ ~i~ has a potency value $p_i$ ~p_i~. There are only two known ways to combine two components $i$ ~i~ and $j$ ~j~ into a single component:

Controlled combination: the two components will combine together to make a new component with potency $p_i + p_j$ ~p_i + p_j~.
Unstable combination: the two components will combine together to make a new component with potency $p_i \times p_j$ ~p_i \times p_j~.

After Megumin applies operations $N-1$ ~N-1~ times, the size of the resulting explosion is equal to the potency of the only remaining component. Since Megumin appreciates the beauty of both a small and intense and a large and flashy explosion, you would like to determine what the sizes of the smallest and largest explosions Megumin can possibly make are. Since these numbers may be very large, you should output the results modulo $10^9+7$ ~10^9+7~.

Input Specification

The first line of input will contain the integer $N$ ~N~.
The second line of input will contain $N$ ~N~ integers, $p_{1 \dots N}$ ~p_{1 \dots N}~.

Output Specification

The first line of output should contain the smallest explosion Megumin can make.
The second line of output should contain the largest explosion Megumin can make.

Constraints

For all subtasks:

$1 \le N \le 10^5$ ~1 \le N \le 10^5~

$1 \le p_i \le 1\,000$ ~1 \le p_i \le 1\,000~

Subtask 1 [20%]

$1 \le N \le 10$ ~1 \le N \le 10~

$1 \le p_i \le 5$ ~1 \le p_i \le 5~

Subtask 2 [35%]

At most $2$ ~2~ values of $p_i$ ~p_i~ will be equal to $1$ ~1~.

Subtask 3 [45%]

No additional constraints.

Sample Input

3
2 1 3

Sample Output

5
9

Explanation of Output for Sample Input

To make the smallest explosion, first Megumin should combine the components with potencies 2 and 3 with a controlled combination and then combine the remaining components with unstable combinations.
To make the largest explosion, first Megumin should combine the components with potencies 1 and 2 with a controlled combination and then combine the remaining components with unstable combinations.

Comments

0

aeternalis1 commented on July 24, 2017, 4:45 a.m.

Prevent stack overflow?

How can I prevent my submission from overflowing due to the excessively large integers resulting from multiplying the list?

1

wleung_bvg commented on July 24, 2017, 4:52 a.m. ← edit 2 →

Taking the modulus of a number after multiplication and addition won't affect the answer. (I'm guessing you meant number overflow rather than stack overflow)

1

aeternalis1 commented on July 24, 2017, 1:35 p.m.

Thank you my friend. Thank you.

2

KevinWan commented on April 27, 2017, 3:01 p.m.

pls help me I don't know why my submission is wrong?

3

wleung_bvg commented on April 28, 2017, 8:33 p.m.

I would look into what happens when you combine components of size 2 and 1 and how it compares to what happens when you just add 1 to the lowest component.