얼음 블록

400점케이스 16출제 dongbinna

10월 30일에 올라온 문제입니다.

문제

어느 수산 시장의 냉동 저장고에는 직육면체 모양의 빈 공간이 있다. 이 공간의 가로 길이는 L, 세로 길이는 W, 높이는 H이고 세 값은 모두 자연수다. 관리자는 이 공간을 얼음 블록으로 빈틈없이 채워야 한다.

얼음 블록은 정육면체 모양이고 한 변의 길이는 언제나 2의 거듭제곱이다. 그래서 블록의 한 변은 1, 2, 4, 8, 16처럼 2를 거듭 곱한 값만 가진다. 블록을 넣을 때는 세 변을 저장고의 세 변과 나란히 두어야 하고, 블록을 쪼개거나 기울일 수는 없다. 블록끼리 겹쳐서도 안 되고 저장고 밖으로 나가서도 안 된다.

창고에 가지고 있는 블록은 한 변의 길이별로 개수가 정해져 있다. 가진 블록을 모두 쓸 필요는 없으며, 빈틈이 하나도 남지 않게 채우기만 하면 된다. 이때 쓰는 블록의 개수를 최소로 하려고 한다. 가진 블록으로는 빈틈없이 채울 수 없는 경우도 있는데, 그런 경우에는 -1을 답으로 한다.

저장고의 세 변의 길이와 가지고 있는 블록의 정보가 주어졌을 때, 빈틈없이 채우는 데 드는 블록의 최소 개수를 구하는 프로그램을 작성하여라.

예를 들어 저장고의 세 변이 모두 10이고, 가지고 있는 블록이 다음의 표와 같다고 해보자.

한 변의 길이	8	2	1
가진 개수	1	100	1000

이 저장고의 부피는 10과 10과 10을 곱한 1,000이다. 한 변이 8인 블록 하나를 한쪽 구석에 넣으면 512만큼이 채워지고, 남은 488은 한 변이 2인 블록 61개로 빈틈없이 채울 수 있다. 블록을 다 넣은 결과를 적으면 다음과 같다.

한 변의 길이	8	2	합
넣은 개수	1	61	62
차지한 부피	512	488	1000

부피 1,000을 빈틈없이 채웠고 쓴 블록은 62개다. 한 변이 1인 블록은 한 개도 쓰지 않았다. 한 변이 8인 블록은 하나뿐이므로 큰 블록을 더 넣을 수는 없고, 그 블록을 쓰지 않으면 한 변이 2인 블록 125개가 들어 더 많아진다. 따라서 현재 예시에서 정답은 62다.

반면에 세 변이 모두 2인 저장고에 한 변이 1인 블록 7개만 가지고 있다면, 부피 8을 채우려면 그 블록이 8개 있어야 하므로 빈틈없이 채울 수 없다. 이 경우의 답은 -1이다.

입출력 예시

예시 1

입력

출력

예시 2

입력

2 2 2
1
0 7

출력

-1

예시 3

입력

출력

입력 조건

가장 먼저 저장고의 가로 길이 L과 세로 길이 W와 높이 H가 첫째 줄에 공백 하나로 구분되어 차례대로 주어진다. 세 값은 모두 1 이상 1,048,575 이하의 자연수다(2의 20제곱보다 작다).
이어서 둘째 줄에 가지고 있는 블록의 종류 수 N이 주어진다. N은 1 이상 20 이하의 자연수다.
이어서 셋째 줄부터 N+2번째 줄까지 블록의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 지수 i와 개수 b가 공백 하나로 구분되어 차례대로 주어지며, 이는 한 변의 길이가 2의 i제곱인 블록을 b개 가지고 있다는 뜻이다. i는 0 이상 19 이하의 정수이고 b는 1 이상 1,000 이하의 자연수다. 같은 i가 두 번 주어지지는 않는다.

출력 조건

빈틈없이 채우는 데 드는 블록의 최소 개수를 첫째 줄에 출력한다. 가진 블록으로 빈틈없이 채울 수 없으면 -1을 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.

요구사항

입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
블록의 한 변은 2의 거듭제곱이고, 입력에는 지수 i로 주어집니다. 한 변의 길이는 2의 i제곱입니다
블록은 세 변을 저장고의 세 변과 나란히 두어야 하며, 쪼개거나 기울일 수 없습니다
가진 블록을 모두 쓸 필요는 없습니다. 빈틈없이 채우면서 개수를 최소로 하면 됩니다
가진 블록으로 빈틈없이 채울 수 없으면 -1을 출력합니다
입력의 줄 수는 N+2입니다. 첫째 줄에 세 수, 둘째 줄에 N, 그 뒤로 N개의 줄이 옵니다
채점은 출력을 기대값과 글자 하나까지 견줍니다
표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
쓸 수 있는 말은 파이썬, 자바스크립트입니다
메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
케이스는 16개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
케이스 16개를 전부 통과해야 해결입니다.

문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 16개를 전부 통과해야 해결입니다.

입력

기대 출력

2 2 2
1
0 7

-1

풀이

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 2.0ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

이 문제를 푼 사람

아직 없습니다. 첫 번째가 되실 수 있습니다.