USACO 2022 US Open Contest, Bronze Problem 3. Alchemy

USACO 2022 US Open Contest, Bronze Problem 3. Alchemy

Always keen to learn new hobbies, Bessie the cow is learning how to transform metals. She has aiai (0≤ai≤1040≤ai≤104) units of metal ii for 1≤i≤N≤1001≤i≤N≤100. Furthermore, she knows KK (1≤K<N1≤K<N) recipes where she can combine one unit each of several metals to make one unit of a metal with a higher number than all constituent metals. It is additionally guaranteed that for each metal, Bessie knows at most one recipe to make it.

Compute the maximum number of units of metal NN Bessie can possibly have after some series of transformations.

 

 

 

SAMPLE INPUT:

5
2 0 0 1 0
3
5 2 3 4
2 1 1
3 1 2

SAMPLE OUTPUT:

1

In this example, the following is an optimal series of transformations:

1. Transform one unit of metal 1 into metal 2.
2. Transform one unit of metal 2 into metal 3.
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.

Problem credits: Nick Wu

USACO 2022 US Open Contest, Bronze Problem 3. Alchemy 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]
(Analysis by Nick Wu)
For notational convenience, if i>j, we'll say that metal i is more valuable than metal j. Note that all recipes take a single unit of some metals and produce one unit of a metal that is more valuable than all of the original metals.

To solve test case 2, every unit of metal can be converted into a unit of metal N, so the answer is the number of units of metal that Bessie has.

To solve test cases 3 and 4, if there is no recipe that can make metal N, then the answer is simply the number of units of metal N that Bessie starts out with. Otherwise, there is some less valuable metal that can be turned directly into metal N, so all of those units can also be converted into metal N. If that less valuable metal has no recipe, then we are done. Otherwise, we repeat this process and sum up the counts of the less valuable metals until we reach one which can't be made.

To solve the problem fully, we'll take advantage of how recipes can only turn less valuable metals into more valuable metals. If we want to gain one unit of metal N, we must use that recipe, and so that means we need one unit of some less valuable metals. If we already have one of each unit of the less valuable metals, we can directly consume those. If we don't have a unit of some metal, and no recipe for that metal exists, we cannot make any more of metal N, and the process ends. If there is a recipe, then we need one unit of each of the metals that are ingredients in that recipe.

Since more valuable metals cannot be used as ingredients in recipes for less valuable metals, we can loop over the metals in order from metal N down to metal 1, tracking at each point in time how many units of each metal we need in order to make one unit of metal N.

The while loop runs at most N⋅max(ai) times and takes O(N) time per iteration, for a time complexity of O(N2⋅max(ai)).

C++ code that does this iteratively:

#include <bits/stdc++.h>

using namespace std;

int main() {
int n;
cin >> n;
vector have(n);
for(auto& x: have) cin >> x;
int k;
cin >> k;
vector<vector> need(n);
while(k--) {
int want, m;
cin >> want >> m;
need[--want].resize(m);
for(auto& x: need[want]) {
cin >> x;
x--;
}
}
int ret = 0;
while(true) {
vector consume(n);
consume[n-1]++;
bool good = true;
for(int i = n-1; i >= 0; i--) {
if(consume[i] <= have[i]) {
have[i] -= consume[i];
continue;
}
if(need[i].size() == 0) {
good = false;
break;
}
int take = min(consume[i], have[i]);
consume[i] -= take;
have[i] -= take;
for(int out: need[i]) consume[out] += consume[i];
}
if(good) ret++;
else break;
}
cout << ret << "\n";
}
Java code that does this recursively:

import java.io.*;
import java.util.*;
public class Alchemy {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
StringTokenizer st = new StringTokenizer(in.readLine());
int[] have = new int[n];
for(int i = 0; i < n; i++) have[i] = Integer.parseInt(st.nextToken()); int ans = 0; int[][] recipes = new int[n][]; int k = Integer.parseInt(in.readLine()); while(k-- > 0) {
st = new StringTokenizer(in.readLine());
int gain = Integer.parseInt(st.nextToken())-1;
recipes[gain] = new int[Integer.parseInt(st.nextToken())];
for(int i = 0; i < recipes[gain].length; i++) recipes[gain][i] = Integer.parseInt(st.nextToken())-1; } while(canMake(recipes, have, n-1)) ans++; PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); out.println(ans); out.close(); } private static boolean canMake(int[][] recipes, int[] have, int want) { if(have[want] > 0) {
have[want]--;
return true;
}
if(recipes[want] == null) return false;
for(int component: recipes[want]) if(!canMake(recipes, have, component)) return false;
return true;
}

[/hide]