시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 2973 | 331 | 235 | 13.107% |
과학자 임문빈은 마법의 물약을 만든다. 임문빈은 많은 재료를 가지고 있고, 다음과 같은 식을 이용해서 만든다.
S=N1×S1+...+Nk×Sk
여기서 N1, ..., Nk는 1보다 크거나 같고, 9보다 작거나 같은 한 자리 숫자이고, S1, ..., Sk는 재료의 이름이다. 그리고, k는 1보다 크거나 같은 자연수이다. 마지막으로 S는 마법의 물약의 이름이다. 위의 식은 N1만큼 S1을 넣고, ..., Nk만큼 Sk를 넣으면 S가 1만큼 만들어 진다는 얘기와 같다.
같은 물약을 만드는데 여러 가지 재료법이 있을 수도 있다. 이때는, 아무거나 사용하면 된다. 마법의 물약은 또 다른 물약을 만드는데 재료가 될 수도 있고, 이 중 어떤 재료는 시장에서 살 수 있다.
임문빈은 이름이 LOVE인 마법의 물약을 만들려고 한다. (이 물약을 먹으면 임문빈을 사랑하게 된다) 시장에서 파는 재료와 그 가격이 주어지고, 임문빈이 만들 수 있는 모든 물약의 식이 주어진다. 이때, LOVE를 1만큼 만드는데 드는 비용의 최솟값을 출력한다.
첫째 줄에 시장에서 파는 재료의 개수 N과 임문빈이 만들 수 있는 물약의 식의 개수 M이 주어진다. 둘째 줄 부터 N개의 줄에는 시장에서 파는 재료의 이름과 그 가격이 공백으로 구분해서 주어진다. 재료의 이름은 오직 알파벳 대문자로만 이루어져 있고, 파는 재료는 중복되지 않는다. 그 다음 줄 부터 M개의 줄에는 물약의 식이 문제 상단과 같은 형식으로 주어진다. N은 50보다 작거나 같은 자연수이고, 재료의 이름의 길이는 최대 50이다. 가격은 100보다 작거나 같은 자연수이다. M은 50보다 작거나 같은 자연수 또는 0이다. 각 식의 길이도 최대 50이다.
첫째 줄에 LOVE를 1만큼 만드는데 드는 비용의 최솟값을 출력한다. 만약 그 값이 1,000,000,000보다 크다면 1000000001을 출력한다. 만약 LOVE를 만드는 것이 불가능 하다면 -1을 출력한다.
3 2 WATER 2 HONEY 6 HOP 9 LOVE=2WATER+4HONEY+2BEER BEER=1HOP+3WATER+1HOP
76
3 1 LOVE 100 WATER 1 HONEY 30 LOVE=5WATER+3HONEY
95
2 1 ORANGEJUICE 6 APPLEJUICE 4 JUICEMIX=1ORANGEJUICE+1APPLEJUICE
-1
3 2 WATER 1 HONEY 22 HOP 17 LOVE=7WATER+3HONEY LOVE=2HONEY+2HOP
73
2 3 OIL 60 WATER 70 FIRSTPOTION=1OIL+1SECONDPOTION SECONDPOTION=4WATER+1FIRSTPOTION LOVE=1FIRSTPOTION+1SECONDPOTION
-1
1 10 HONEYBIT 100 LOVE=6HONEYMEGABYTE HONEYMEGABYTE=2HONEYFIFTYTWELVEKBYTES HONEYFIFTYTWELVEKBYTES=8HONEYSIXTYFOURKBYTES HONEYSIXTYFOURKBYTES=8HONEYEIGHTKBYTES HONEYEIGHTKBYTES=8HONEYKBYTE HONEYKBYTE=2EIGHTBYEIGHTWORDS EIGHTBYEIGHTWORDS=8EIGHTWORDS EIGHTWORDS=8HONEYWORD HONEYWORD=8HONEYBYTE HONEYBYTE=8HONEYBIT
1000000001
1 1 WATER 1 LOVE=1LOVE
-1
3 8 MILK 6 WATER 1 HOP 14 NECTAR=4HOP+2MILK LOVE=5MILK+3BEER LOVE=2WATER+1LOVE LOVE=2MIX+1NECTAR MIX=1MILK+1WATER+1HOP BEER=5WATER+2HOP LOVE=1NECTAR+3WATER+3HOP NECTAR=3BEER+1MILK+2MILK
110