카드 숫자 곱을 최소로 만들기

면접 대비

시간 제한1초메모리 제한512 MB

요약

1부터 9까지의 숫자 n개가 주어질 때, 곱이 더 큰 숫자 n개의 집합 중 오름차순으로 이어 붙인 수가 가장 작은 집합을 찾습니다. 그런 집합이 없으면 -1을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 완전 탐색, 수학, 백트래킹
정답자: 아직 제출이 없습니다

문제

1부터 9까지의 정수가 하나씩 적힌 카드가 무수히 많이 있다. 이 중에서 $n$ 장의 카드를 고르자. 같은 정수가 적힌 카드를 여러 장 고를 수 있다. 내가 고른 $n$ 장의 카드 집합을 $A$ , 친구가 고른 $n$ 장의 카드 집합을 $B$ 라고 하자. 집합 $A$ 에 있는 카드에 적힌 정수의 곱을 $P(A)$ , 집합 $B$ 에 있는 카드에 적힌 정수의 곱을 $P(B)$ 라고 하자. 집합 $A$ 가 주어지면, $P(A) < P(B)$ 를 만족하는 집합 $B$ 를 하나 출력하자. 만족하는 집합 $B$ 가 여러 개면, $B$ 의 원소를 오름차순으로 정렬해 이어 붙인 수가 가장 작은 $B$ 를 출력하자. 만족하는 $B$ 가 없으면 $B = \{-1\}$ 을 출력하자.

입력

첫 번째 줄에 카드 개수 $n$ 이 주어진다. 두 번째 줄에 내가 고른 $n$ 장의 카드에 적힌 정수가 공백으로 구분되어 순서대로 주어진다.

출력

첫 번째 줄에 친구가 고른 집합 $B$ 의 원소를 오름차순으로 공백을 사이에 두고 출력한다.

제한

$1 \le n \le 7$

예제3

예제 1
입력
```
1
7
```
예상 출력
```
8
```
예제 2
입력
```
2
5 5
```
예상 출력
```
3 9
```
예제 3
입력
```
1
9
```
예상 출력
```
-1
```