시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 911 | 258 | 155 | 25.452% |
주어진 숫자 카드와 사칙연산, 괄호 등을 조합하여 원하는 값을 만드는 게임이 있다. 이 게임을 좋아하는 ‘진’은 이번 IT공과대학 MT에서 이 게임을 하려고 카드를 챙겼다. 그러나 실수로 카드셋을 다 챙기지 못 했다. 연산자 카드는 오직 곱하기 카드만 챙기고, 숫자카드는 0에서 9까지 카드 중 N개의 종류의 카드만 챙겼다. 그래서 진은 게임의 종류를 곱셈 게임으로 변경하기로 하였다.
곱셈 게임은 정해진 숫자를 주어진 숫자카드와 곱셈카드를 조합하여 만드는 게임이다. 이 게임은 곱셈카드의 개수를 가장 적게 사용하는 팀이 승리하게 된다. 가져온 숫자카드의 종류가 주어졌을 때, 곱셈카드를 가장 적게 사용하여 게임을 승리할 수 있도록 하자. 카드는 각 종류별로 충분히 많이 가져와 부족한 경우는 없다.
예를 들어, 가져온 숫자카드의 종류가 2,3,6 일 때, 64는 32 x 2 로 곱하기 1개를 사용하여 만들 수 있고 이는 곱셈카드를 가장 적게 사용한 것이다.
입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 숫자 카드의 종류의 개수 N(1 ≤ N ≤ 10)과 N개의 숫자 카드의 종류가 공백을 구분으로 주어진다.
각 테스트 케이스의 두 번째 줄에는 질의의 수 M(1 ≤ M ≤ 20)이 주어진다.
다음 M개의 줄에는 만들고자 하는 자연수 K가 주어진다.(K ≤ 1,000,000)
각 질의마다 곱셈카드의 최소의 개수를 출력한다. 수를 만들 수 없는 경우에는 -1을 출력한다.
2 3 2 3 6 3 64 5 7 4 1 2 3 4 2 31 16
1 -1 -1 0 1
University > 인하대학교 > 2016 IUPC 인하대학교 프로그래밍 경진대회 F번