가장 큰 방 번호 2
시간 제한2초메모리 제한128 MB
숫자별 구매 비용과 예산이 주어질 때 만들 수 있는 가장 큰 방 번호를 구해 길이와 앞뒤 50자리를 출력하는 문제입니다.
문제
어떤 사무실의 방 번호를 정하려고 한다. 방 번호를 만들려면 숫자판을 구매해야 하며, 사용할 수 있는 금액은 M원이다.
숫자판에는 0부터 N-1까지의 숫자가 있고, 숫자 i의 가격은 P_i원이다. 같은 숫자는 여러 번 구매할 수 있으며, 필요한 만큼 항상 구매할 수 있다. 방 번호가 0이 아니라면 첫 자리에 0을 놓을 수 없다.
M원 이하를 사용해서 만들 수 있는 가장 큰 방 번호 X를 구한다. X가 매우 길 수 있으므로, 전체 문자열 대신 자릿수와 앞쪽/뒤쪽 일부만 출력한다.
입력
첫째 줄에 숫자의 개수 N이 주어진다.
둘째 줄에 P_0, P_1, ..., P_{N-1}이 공백으로 구분되어 주어진다.
셋째 줄에 사용할 수 있는 금액 M이 주어진다.
출력
첫째 줄에 만들 수 있는 가장 큰 방 번호 X의 자릿수를 출력한다.
둘째 줄에는 X의 처음 50자리를 출력하고, 셋째 줄에는 X의 마지막 50자리를 출력한다. X의 자릿수가 50보다 작으면 둘째 줄과 셋째 줄에 모두 X를 출력한다.
어떤 방 번호도 만들 수 없다면 첫째 줄에 0을 출력하고, 둘째 줄과 셋째 줄은 빈 줄로 출력한다.
제한
- 1 <= N <= 10
- 1 <= P_i <= 10^18
- 0 <= M <= 10^18
- N, P_i, M은 정수이다.