시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 873 | 16 | 4 | 3.636% |
동혁건설에서는 이번에 새로운 건물을 짓게 되었다. 건물을 만들기 위해서는 짧은 길이의 강철 파이프가 N개 필요하다. 마침 공사 때 사용하고 남은 긴 길이의 파이프가 M개 있어서 이를 먼저 사용한 뒤 필요한 파이프를 추가 주문하기로 하였다. 동혁건설에서는 가급적이면 적은 개수의 파이프를 추가 주문하려 한다. 즉, 주어진 강철 파이프를 잘라서 최대한 많은 개수의 필요한 파이프를 만들어 내려 한다.
작은 길이의 파이프를 만들기 위해서는 긴 길이의 파이프를 자르면 된다. 자르는 과정에서 파이프의 길이에 손실이 있을 수도 있지만, 문제에서는 이를 무시해도 좋다. 또한, 파이프를 자를 때에는 여러 번 자를 수도 있다.
첫째 줄에 M(1 ≤ M ≤ 50)이 주어진다. 다음 줄에는 M개의 긴 강철 파이프의 길이가 주어진다. 각각의 길이는 100,000을 넘지 않는 양의 정수이다. 다음 줄에는 N(1 ≤ N ≤ 1023)이 주어진다. 다음 줄에는 만들고자 하는 파이프의 길이를 나타내는 정수가 N개 주어진다. 이 길이는 128 이하의 자연수이다.
첫째 줄에 만들 수 있는 필요한 파이프의 최대 개수를 출력한다.
4 30 40 50 25 10 15 16 17 18 19 20 21 25 24 30
7
Olympiad > USA Computing Olympiad > 1998-1999 Season > USACO Spring 1999 Contest > ? Division 1번