문제
정올이는 쿠키를 만드는 것을 좋아한다. 그는
모든 상자에 대해서 그 상자에 들어있는 쿠키의 종류들은 서로 다르다.
모든 상자에 대해서 그 상자에 들어있는 쿠키의 개수는 다음
M 개의 숫자 중 하나와 같다:B_1,B_2,\dots,B_M .
정올이가 만든 쿠키의 정보와 쿠키를 상자에 담는 조건들이 주어졌을 때, 모든 쿠키를 상자에 담을 수 있는지 판단하는 프로그램을 작성하라. 또한, 모든 쿠키를 상자에 담을 수 있다면 최소한의 상자 개수로 쿠키를 담는 방법을 출력하라.
입력
다음 형태의 데이터가 표준 입력으로 주어진다.
제한
주어진 값들은 모두 정수이다.
출력
모든 쿠키를 상자에 담을 수 있고 조건들이 충족된다면 사용된 상자의 개수를
사용된 상자의 개수
모든 쿠키를 상자에 담을 수 없거나 조건들이 충족되지 않는다면 -1을 출력하라.
부분문제
번호 | 점수 | 조건 |
---|---|---|
#1 | 6점 |
|
#2 | 7점 |
|
#3 | 12점 | |
#4 | 45점 | |
#5 | 15점 | |
#6 | 15점 |
|
예제1
7
1 1 1 1 1 1 1
3
1 2 3
3
2 1 7
2 2 6
3 3 4 5
이 예제 입력에서,
쿠키의 종류가
인 쿠키들을 첫 번째 상자에 담는다. 각 종류의 쿠키를 한 개씩 담는다. 쿠키의 종류가
인 쿠키들을 두 번째 상자에 담는다. 각 종류의 쿠키를 한 개씩 담는다. 쿠키의 종류가
인 쿠키들을 세 번째 상자에 담는다. 각 종류의 쿠키를 한 개씩 담는다.
프로그램이 위와 같이 쿠키를 담는 방법을 출력하면 정답으로 인정된다. 왜냐하면,
이 예제 입력은 서브태스크 1, 3, 4, 5, 6의 제한을 충족한다.
예제2
5
5 3 1 2 4
1
4
-1
이 예제 입력에서는 조건을 충족하는 것이 불가능하다. 따라서 -1을 출력한다.
이 예제 입력은 서브태스크 2, 3, 4, 5, 6의 제한을 충족한다.
예제3
7
5 4 4 2 1 1 1
2
2 6
7
6 1 2 3 4 5 6
2 2 1
2 3 1
2 4 1
2 7 1
2 3 2
2 3 2
이 예제 입력은 서브태스크 4, 5, 6의 제한을 충족한다.
출처
JOI 2022/2023 Spring Training Camp