식당 주문
시간 제한1초메모리 제한256 MB
메뉴 가격과 주문 총액이 주어질 때 각 총액에 맞는 메뉴 조합을 복원하고, 없으면 Impossible, 여러 개면 Ambiguous를 출력합니다.
- 난이도
보통10점 중 6점
- 유형
- 동적 계획법
- 정답자
- 아직 제출이 없습니다
문제
식당에서 일하는 친구가 곤란해졌다. xkcd 팬 모임이 이 식당을 찾아오기 시작했는데, 아래 만화처럼 주문한다. 주문 하나를 풀어내는 데 시간이 오래 걸리니 프로그램으로 대신 처리하자.

그림 G.1: 만화 xkcd.com/287.
메뉴에 있는 각 항목의 가격과 주문 하나의 총액이 주어진다. 무엇을 주문했는지 알아내는 프로그램을 작성하라. 한 주문에 같은 항목이 여러 번 들어갈 수 있다. 가격이 같은 항목이 메뉴에 여러 개 있을 수 있고, 이런 항목도 서로 다른 항목으로 센다. 고른 항목의 번호만 다른 두 주문은 서로 다른 주문이다.
입력
첫 줄에 메뉴 항목의 개수 ()이 주어진다. 둘째 줄에 각 항목의 가격 이 공백으로 구분되어 주어진다. 가격은 스웨덴 크로나 단위의 양의 정수이고 1000을 넘지 않는다.
셋째 줄에 주문의 개수 ()이 주어진다. 넷째 줄에 개의 주문이 공백으로 구분되어 주어지며, 각 주문은 그 주문에 포함된 항목 가격의 총합 ()이다.
출력
주문마다 한 줄씩 출력한다. 총액이 가 되는 주문이 정확히 하나면 그 주문에 포함된 항목의 번호를 오름차순으로, 번호 사이에 공백 하나를 두고 출력한다. 같은 항목이 여러 번 들어 있으면 그 번호를 들어 있는 횟수만큼 출력한다. 메뉴의 첫 번째 항목이 1번, 두 번째 항목이 2번이고 이런 식으로 번호를 매긴다.
총액이 가 되는 주문이 없으면 Impossible을 출력한다. 총액이 가 되는 주문이 둘 이상이면 Ambiguous를 출력한다.