소수 만들기

시간 제한2초메모리 제한128 MB

요약

1부터 30까지의 정수로 이루어진 배열의 모든 원소를 사칙연산과 괄호로 조합해 만들 수 있는 값 중 가장 작은 소수와 가장 큰 소수를 구하는 문제입니다.

난이도: 보통10점 중 6점
유형: 백트래킹, 완전 탐색, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

1 이상 30 이하의 정수로 이루어진 크기 N의 배열 A가 주어진다. 배열의 모든 원소를 각각 정확히 한 번씩 사용하고, 연산자 +, -, *, /와 괄호를 원하는 만큼 사용해 하나의 식을 만들 수 있다. 만들 수 있는 값 중 가장 작은 소수와 가장 큰 소수를 구하라.

배열 A에는 같은 수가 여러 번 나올 수 있다.

예를 들어 A = {1, 2, 3}이면 가장 작은 소수는 3 - 2 + 1 = 2이고, 가장 큰 소수는 3 * 2 + 1 = 7이다.

나눗셈을 사용할 때 두 피연산자는 모두 양의 정수여야 하며, 나누어떨어지는 경우에만 정수 나눗셈으로 사용할 수 있다.

입력

첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에 A의 원소 N개가 공백으로 구분되어 주어진다.

출력

첫째 줄에 만들 수 있는 가장 작은 소수를, 둘째 줄에 가장 큰 소수를 출력한다. 만들 수 있는 소수가 하나도 없으면 -1만 출력한다.

제한

1 ≤ N ≤ 6

예제6

예제 1
입력
```
2
1 2
```
예상 출력
```
2
3
```
예제 2
입력
```
3
1 2 3
```
예상 출력
```
2
7
```
예제 3
입력
```
6
1 2 3 4 5 6
```
예상 출력
```
2
719
```
예제 4
입력
```
6
2 3 5 7 11 13
```
예상 출력
```
2
15017
```
예제 5
입력
```
6
2 2 2 2 2 2
```
예상 출력
```
2
17
```
예제 6
입력
```
1
8
```
예상 출력
```
-1
```