Frankenstein solution in java
unknown
plain_text
10 months ago
4.6 kB
13
Indexable
import java.util.*;
public class Frankenstein {
static Map<String, List<List<String>>> recipes = new HashMap<>();
static Map<String, Integer> memo = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.nextLine().trim());
// Read recipes
for (int i = 0; i < N; i++) {
String line = sc.nextLine().trim();
String[] parts = line.split("=");
String potion = parts[0].trim();
String[] ingArr = parts[1].split("\\+");
List<String> ingredients = new ArrayList<>();
for (String ing : ingArr) {
ingredients.add(ing.trim());
}
recipes.computeIfAbsent(potion, k -> new ArrayList<>()).add(ingredients);
}
// Target potion
String target = sc.nextLine().trim();
// Calculate and print minimum orbs
int result = getMinOrbs(target);
System.out.println(result);
}
static int getMinOrbs(String potion) {
if (memo.containsKey(potion)) return memo.get(potion);
// If potion is not in recipes, it is a base item
if (!recipes.containsKey(potion)) {
memo.put(potion, 0);
return 0;
}
int minOrbs = Integer.MAX_VALUE;
for (List<String> ingredients : recipes.get(potion)) {
int orbs = ingredients.size() - 1; // base orbs for combining ingredients
for (String ing : ingredients) {
orbs += getMinOrbs(ing); // add cost of brewing each ingredient
}
minOrbs = Math.min(minOrbs, orbs);
}
memo.put(potion, minOrbs);
return minOrbs;
}
}
}
}
}
}
}
}
}
}Editor is loading...
Leave a Comment