레이팅 미적용항상 새로운 취미를 배우고 싶어 하는 소 베시는 금속을 변환하는 법을 배우고 있다. 베시는 \(1 \le i \le N \le 100\)에 대해 금속 \(i\)를 \(a_i\) (\(0 \le a_i \le 10^4\))단위 가지고 있다. 또한 베시는 \(K\)개(\(1\le K
일련의 변환을 거친 후 베시가 가질 수 있는 금속 \(N\)의 최대 단위 수를 계산하여라.
Problem credits: Nick Wu
채점 방식
- 테스트 케이스 2에서는, \(1 \le i < N\)에 대해 금속 \(i\) 한 단위를 금속 \(i+1\) 한 단위로 변환할 수 있다.
- 테스트 케이스 3과 4에서는, 각 레시피가 한 금속 한 단위를 다른 금속으로 변환한다.
- 테스트 케이스 5부터 11까지는 추가 제약이 없다.
Problem credits: Nick Wu
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_i\)가 주어진다.
셋째 줄에 \(K\)가 주어진다.
다음 \(K\)개의 줄은 두 정수 \(L\)과 \(M\) (\(M\ge 1\))으로 시작하고, 그 뒤에 \(M\)개의 정수가 주어진다. 마지막 \(M\)개의 정수는 금속 \(L\) 한 단위를 만드는 레시피에 사용되는 재료 금속들을 나타낸다. \(L\)은 마지막 \(M\)개의 정수보다 큼이 보장된다.
0번 이상의 변환을 적용한 후 베시가 가질 수 있는 금속 \(N\)의 최대 단위 수를 출력한다.
5
2 0 0 1 0
3
5 2 3 4
2 1 1
3 1 21In this example, the following is an optimal series of transformations:
- Transform one unit of metal 1 into metal 2.
- Transform one unit of metal 2 into metal 3.
- Transform one unit of metal 3 and metal 4 into metal 5.
Now Bessie is left with one unit of metal 1 and one unit of metal 5. She cannot
form any additional units of metal 5.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Bronze