프로그램 명: five_card(special judge)
제한시간: 1 초
운명의 마술사 Fate는 카드놀이를 무척 좋아한다. 그는 N ( 5 ≤ N ≤ 2,000) 장의 카드 중에서 5장의 카드를 뽑아 K라는 수에 최대한 가깝게 만들려 하는데, 다음과 같은 두 조건으로 카드를 뽑기로 했다.
-
5장의 카드 중 숫자 M번째로 큰 카드가 있을 때, M-1번째로 큰 카드나 M+1번째로 큰 카드가 5장 안에 포함되어있지 않다면 해당 카드를 독립된 카드라 칭한다.
-
이 독립된 카드는 5장의 카드 중 2개 이하여야한다.
2 3 5 7 11 13 17 19 의 카드들이 있고, 43과 54 두 수를 만들려 한다.
-
43은 2 [3 5 7 11] 13 [17] 19 를 뽑으면 만들 수 있고 독립된 카드는 17 하나뿐이므로 성립한다.
-
54는 [2] 3 [5] 7 [11] 13 [17 19] 를 뽑으면 54를 만족할 수 있으나, 이는 독립된 카드가 2 5 11 3개이므로 조건을 위배했다.
따라서 54는 [2 3] 5 7 11 [13 17 19]로 54를 고르는 것이 최적이라는 것을 알 수 있다.
여러분은 Fate를 도와 내에서 5장의 최적의 카드 조합을 찾아주자.
입력
-
카드의 수 n이 입력되고,
-
다음 줄에는 n개의 수 An이 입력된다. ( |An| <= 100,000)
-
다음 줄에는 궁금한 수의 갯수 T가 입력되고, 각 줄에는 정수 K가 입력된다. ( T ≤ 5 )
출력
T개의 줄에 걸쳐 K에 가장 가까운 수를 출력하고, 그때의 더해지는 수들을 출력한다. 만약 정답의 경우가 여러가지 나올 수 있는 경우, 그 중 아무거나 하나만 출력한다.
입출력 예
입력
8
7 3 11 2 17 13 5 19
2
43
54
출력
43 3 5 7 11 17
54 2 3 13 17 19
출처:Fate(cafe.naver.com./koimeeting)
[질/답]
[제출 현황]
[푼 후(3)]