- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
Mike and Sally work in the warehouse of Monster Inc. as storekeepers. Their daily tasks are to process incoming requests and update the inventory of the Warehouse. Requests only include buying, selling, unpacking, and packing containers. The warehouse includes goods and containers and has unlimited space. A container may contain goods or other containers as sub-containers.
The exact format of the requests is given below.
BUY <CONTAINER_DESCRIPTION>
SELL <CONTAINER_ID>
UNPACK <CONTAINER_ID>
PACK <CONTAINER_DESCRIPTION>
Each container which is not inside any other container is uniquely identified by a positive integer ID
. Assigning ID
s to containers is done sequentially and started from $1$. An ID
is valid if and only if its container exists in the warehouse, otherwise it is invalid.
A container description is enclosed in parentheses and lists the contents, which can be either goods or sub-containers. A good is identified exclusively by its name, which consists of non-case-sensitive English letters. Multiple units of a good may be available. To denote quantities, place a positive integer ‘$N$’ before or after the good name (separated by one white space), where $N < 100$ is the number of the
good. For example, ((tomato, potato), 4 celery, (wood, (silk 3, banana 2)))
describes a
container with four units of celery and two sub-containers.
The description of each request is as follows:
BUY
: A new container is transferred into the warehouse and an ID is assigned to it.SELL
: An existing container with the givenID
is ship out and its ID becomes invalid.UNPACK
: All goods and sub-containers are extracted from the container and added to the ware- house. Moreover, the sub-containers become new containers and get their ownID
. The assignment ofID
s to the new containers is based on the order of their appearance in the container description (from left to right). For instance, considering the following two lines as the first requests, results in adding one unit of celery and adding three containers withID
s $2$, $3$, and $4$ to the warehouse andID
$1$ becomes invalid.
BUY (celery , (Banana), (Celery), (celery ))
UNPACK 1
PACK
: Goods specified in aPACK
request are grouped into a new container, which is then assigned the next availableID
.
Mike and Sulley process the requests in the order they are received. Any request with an invalid
container ID
must be discarded. Moreover, for PACK
request they need to check if there exists enough
units of each good in the warehouse.
Roz, the agent of Monster Inc. has told Mike once ”I’m watching you, Wazowski. Always watching. Always.”, She rolled her desk into their office and asked for requests and reports. She is looking for every detail. She is reviewing each request and might ask a few questions. Her questions might be each of the following types:
? COUNT <good>
: How many units of the given good exist outside of containers?? CONTAINS <good>
: How many containers withID
have the given good, i.e. the good is in the container or there is a recursive sub-container which contains that good.? MIN <good>
: At least how many containers should be unpacked to reach one unit of the good. If it is impossible, the answer should be -1.
Mike and Sully are expected to answer these queries using just one integer
Before helping Mike and Sully, read samples carefully.
ورودی
The input consists of $n$ requests or queries from Roz while she is reviewing; each appears in a separated line. The name of each good is limited to 100 characters. Each container description might have at most 5000 characters and the input size is less than $10^6$ characters.
$$1 \leq n \leq 5000$$
خروجی
Each line of the report is associated with a request or Roz’s questions. After each BUY
, SELL
, PACK
, UNPACK
request, you should print OK
, if the request is not discarded. Otherwise, print DISCARD
. If the request is UNPACK
, after printing OK
, you should print the number of containers added to the warehouse (read samples for more details). For each Roz’s query, print just one integer in a line.
مثالها
ورودی نمونه ۱
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
ورودی نمونه ۲
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
ورودی نمونه ۳
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
ارسال پاسخ برای این سؤال