몬스터 창고

시간 제한1초메모리 제한2048 MB

요약

중첩된 컨테이너가 있는 창고에서 BUY, SELL, UNPACK, PACK 요청을 처리하고 COUNT, CONTAINS, MIN 질의에 답합니다.

난이도: 보통10점 중 5점
유형: 시뮬레이션, 트리, 문자열, BFS
정답자: 아직 제출이 없습니다

문제

Mike와 Sally는 Monster Inc.의 창고에서 창고지기로 일한다. 이들의 일일 업무는 들어오는 요청을 처리하고 창고의 재고를 갱신하는 것이다. 요청은 컨테이너의 구매, 출하, 풀기(UNPACK), 포장(PACK)의 네 종류뿐이다. 창고에는 상품과 컨테이너가 있으며 공간은 제한이 없다. 컨테이너에는 상품이나 다른 컨테이너를 하위 컨테이너로 담을 수 있다.

요청의 정확한 형식은 아래와 같다.

BUY <CONTAINER_DESCRIPTION>
SELL <CONTAINER_ID>
UNPACK <CONTAINER_ID>
PACK <CONTAINER_DESCRIPTION>

다른 컨테이너 안에 들어 있지 않은 컨테이너는 양의 정수 ID로 하나씩 구분된다. ID는 1부터 순서대로 부여된다. ID가 유효한 것은 해당 컨테이너가 창고에 존재할 때뿐이다. 그렇지 않으면 무효이다.

컨테이너 설명은 괄호로 감싸며, 내용물로 상품이나 하위 컨테이너를 나열한다. 상품은 대소문자를 구분하지 않는 영문 알파벳 이름으로만 식별된다. 같은 상품이 여러 개 있을 수 있다. 수량을 나타내려면 상품 이름 앞이나 뒤에 양의 정수 N을 두고, 그 사이를 공백 하나로 구분한다. 여기서 $N < 100$ 은 해당 상품의 개수이다. 예를 들어 ((tomato, potato), 4 celery, (wood, (silk 3, banana 2)))는 celery 4개와 두 개의 하위 컨테이너를 가진 컨테이너를 나타낸다.

각 요청의 내용은 다음과 같다.

BUY: 새 컨테이너가 창고로 옮겨지고 ID를 받는다.
SELL: 주어진 ID의 컨테이너가 출하되며, 그 ID는 무효가 된다.
UNPACK: 컨테이너의 모든 상품과 하위 컨테이너를 꺼내 창고에 추가한다. 하위 컨테이너는 새 컨테이너가 되어 각자 ID를 받는다. 새 컨테이너의 ID는 컨테이너 설명에 나타난 순서(왼쪽에서 오른쪽)에 따라 부여된다. 예를 들어 다음 두 줄이 처음 두 요청이라면 celery 1개가 추가되고, ID 2, 3, 4인 컨테이너 세 개가 창고에 추가되며, ID 1은 무효가 된다.

BUY (celery , (Banana), (Celery), (celery))
UNPACK 1

PACK: PACK 요청에 명시된 상품을 묶어 새 컨테이너를 만들고, 다음 사용 가능한 ID를 부여한다.

Mike와 Sully는 요청을 받은 순서대로 처리한다. 유효하지 않은 컨테이너 ID가 포함된 요청은 폐기한다. PACK 요청에서는 창고에 각 상품이 필요한 수량만큼 있는지도 확인해야 한다.

Monster Inc.의 요원 Roz는 예전에 Mike에게 이렇게 말한 적이 있다. "I'm watching you, Wazowski. Always watching. Always." 그녀는 책상을 사무실 안으로 굴려 들여놓고 요청과 보고서를 요구했다. 그녀는 모든 세부 사항을 살핀다. 각 요청을 검토하며 몇 가지 질문을 던질 수 있다. 질문은 다음 유형 중 하나이다.

? COUNT <good>: 컨테이너 밖에 있는 주어진 상품의 개수는 몇 개인가?
? CONTAINS <good>: 주어진 상품을 가진 ID 컨테이너가 몇 개인가? 즉 상품이 컨테이너 안에 직접 들어 있거나, 재귀적인 하위 컨테이너 안에 그 상품이 들어 있는 경우를 센다.
? MIN <good>: 상품 하나를 얻으려면 최소 몇 개의 컨테이너를 풀어야 하는가? 불가능하면 -1이다.

Mike와 Sully는 이 질문들에 정수 하나씩으로만 답해야 한다.

Mike와 Sully를 돕기 전에 예제를 주의 깊게 읽어라.

입력

입력은 Roz가 검토하는 동안 보내는 n개의 요청 또는 질문으로 이루어진다( $1 \le n \le 5000$ ). 각 요청은 별도의 줄에 있다. 상품 이름은 최대 100자이다. 각 컨테이너 설명은 최대 5000자까지 가질 수 있으며, 입력 전체의 크기는 $10^6$ 자 미만이다.

출력

BUY, SELL, PACK, UNPACK 요청마다 요청이 폐기되지 않았다면 OK를, 폐기되었다면 DISCARD를 출력한다. UNPACK 요청이면 OK를 출력한 뒤, 창고에 추가된 컨테이너 개수를 출력한다. 자세한 내용은 예제를 참고한다. Roz의 각 질문에는 한 줄에 정수 하나를 출력한다.

예제3

예제 1

입력

BUY (10 apple, 10 carrot, 10 banana, ())
UNPACK 1
UNPACK 2
PACK (3 apple, (5 cArrot, 2 banana))
PACK (3 apple, (5 carrOt, 1 banana))
PACK (5 apple, (3 banana))
? MIN apple
? MIN CaRRoT
? CONTAINS apple

예상 출력

OK
OK, 1 container added.
OK, No containers added.
OK
OK
DISCARD
0
2
2

예제 2

입력

BUY (apple, (banana, 3 carrot))
BUY ((banana, apple), (banana, carrot))
? MIN apple
UNPACK 1
? COUNT apple
? COUNT carrot
? CONTAINS banana

예상 출력

OK
OK
1
OK, 1 container added.
1
0
2

예제 3

입력

BUY ((duck 2, carrot), 1 celery)
? MIN duck
? MIN carrot
? MIN celery
? MIN test
SELL 10
PACK (celery)
UNPACK 1
UNPACK 1
PACK (celery)
? COUNT celery
? COUNT carrot
? CONTAINS celery
? CONTAINS carrot
BUY ((duck 8, carrot), ((7 duck), celery))
UNPACK 4
UNPACK 5
UNPACK 6
? COUNT DUCK
? MIN duck

예상 출력

OK
2
2
1
-1
DISCARD
DISCARD
OK, 1 container added.
DISCARD
OK
0
0
1
1
OK
OK, 2 containers added.
OK, No containers added.
OK, 1 container added.
8
0