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

면접 대비

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

요약

1부터 9까지의 숫자 n개로 이루어진 집합 A가 주어질 때, 곱이 P(A)보다 큰 n개의 숫자 집합 B 중 원소를 이어붙인 수가 가장 작은 것을 찾는 문제이다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

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 ≤ n ≤ 7

예제3

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