n recipes are given. Each recipe has a dish name and c ingredient lines, and an ingredient line is an ingredient name and an amount.
An amount is written as an integer "p" or a fraction "p/q" (p divided by q), and a fraction may not be reduced.
If the same ingredient appears on several lines of one recipe, the amount of that ingredient is their sum.
Two recipes have the same ratio if they use exactly the same set of ingredients and there is a positive number r such that, for every ingredient, one amount is r times the other.
Group the recipes with the same ratio together.
For each group, write the ratio with the smallest positive integers: integers that have the same ratio as any recipe in the group, are all positive, and have greatest common divisor 1.
On the first line print the number of groups.
Then print one line per group: the ingredients in string order of their names (by character code, so digits come before lowercase letters) as "ingredient:integer" separated by single spaces, then " = " and the dish names of the group in input order, separated by single spaces.
Groups are printed in the order of each group's earliest dish in the input.
Input
The first line has n, and the next n lines give each recipe as "name c ingredient₁ amount₁ … ingredient_c amount_c" separated by single spaces. 1 ≤ n ≤ 2,000, 1 ≤ c ≤ 10. Dish and ingredient names are 1 to 10 lowercase letters or digits, and dish names are distinct. An amount is "p" or "p/q" with integers 1 ≤ p ≤ 1,000 and 1 ≤ q ≤ 10
Output
The number of groups on the first line, then one line "ingredient:integer … = dish …" per group
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The heart of grouping is building 'a key that comes out the same for the same group'. Here that key is exactly the ratio to print: add each ingredient's amounts as fractions (a/b + p/q = (aq + pb)/(bq), reduced), multiply by the least common multiple of the denominators to get integers, then divide by their greatest common divisor to get the smallest integer ratio. Lay this ratio out in ingredient-name order and use it as the key, and one dictionary that keeps insertion order settles both the groups and the output order. Example: bread is flour 1/2 + 1/2 = 1 and sugar 1/2, so ×2 gives 2:1, and cake's 200:100 ÷100 is also 2:1. One ingredient's amount is at most 1,000 × 10 lines = 10,000 and the lcm of the denominators at most 2,520, so 25.2 million fits in an int. Trap one: not ordering by name makes sugar 1 flour 2 and flour 4 sugar 2 different keys. Trap two: overwriting instead of adding when an ingredient repeats is wrong. Trap three: adding amounts as double and comparing ratios as decimals makes 1/10 + 2/10 equal 0.30000000000000004, a different group from 3/10 — compute with fractions (two integers) as they are. Trap four: joining the key without separators turns both b1:2 c:1 and b:12 c:1 into b12c1 (names contain digits). What can be a key differs by language: Python uses a tuple (a list is unhashable, so it cannot be a key), Java List<String> (it builds equals and hashCode from its contents — a String[] array is equal only to the same object, so no group ever forms), C++ std::map compares std::vector<std::pair<…>> by contents and uses it directly, and JavaScript, TypeScript, C# and Craykon build a string (a JS Map treats arrays as equal only when they are the same object). Group order: Python dict, JS Map, Java LinkedHashMap and Craykon's Dict keys keep insertion order, but Java HashMap scrambles it and C# Dictionary promises no order, so keep a separate list of first appearances. Reading fractions differs too: Python Fraction("3/4") just works, C sscanf(s, "%d/%d", &p, &q) returns 1 on "2", and C++ std::stoi("3/4") stops at / without an error and gives 3, so a forgotten denominator goes unnoticed. Craykon splits with Split("/") and uses ToNumber().
Pythonmain.py · 25 lines
import sysfrom fractions import Fractionfrom math import gcd, lcmlines = sys.stdin.read().split("\n")n = int(lines[0])groups = {} # 비율 열쇠(재료 이름 차례로 늘어놓은 (이름, 정수) 튜플) → 요리 이름들. dict는 넣은 차례를 지킨다for i in range(1, n + 1): parts = lines[i].split() name, c = parts[0], int(parts[1]) amount = {} # 재료 → 양(분수). 같은 재료가 또 나오면 더한다 for j in range(c): ing, q = parts[2 + 2 * j], parts[3 + 2 * j] amount[ing] = amount.get(ing, Fraction(0)) + Fraction(q) # Fraction("3/4")도, Fraction("2")도 된다 # 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 den = lcm(*(a.denominator for a in amount.values())) whole = {ing: int(a * den) for ing, a in amount.items()} g = gcd(*whole.values()) key = tuple(sorted((ing, v // g) for ing, v in whole.items())) # 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 groups.setdefault(key, []).append(name)out = [str(len(groups))]for key, names in groups.items(): out.append(" ".join(f"{ing}:{v}" for ing, v in key) + " = " + " ".join(names))print("\n".join(out))
JavaScriptmain.js · 37 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));const n = Number(lines[0]);const groups = new Map(); // 비율 열쇠(문자열) → 요리 이름들. Map은 넣은 차례를 지킨다for (let i = 1; i <= n; i++) { const parts = lines[i].trim().split(" "); const name = parts[0]; const c = Number(parts[1]); const amount = new Map(); // 재료 → [분자, 분모](약분해 둔다). 같은 재료가 또 나오면 더한다 for (let j = 0; j < c; j++) { const ing = parts[2 + 2 * j]; const [p, q = "1"] = parts[3 + 2 * j].split("/"); // "3/4" → 3, 4 / "2" → 2, 1 const [a, b] = amount.get(ing) ?? [0, 1]; let num = a * Number(q) + Number(p) * b; let den = b * Number(q); const g = gcd(num, den); amount.set(ing, [num / g, den / g]); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 let lcm = 1; for (const [, den] of amount.values()) lcm = (lcm / gcd(lcm, den)) * den; const ings = [...amount.keys()].sort(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 const whole = ings.map((ing) => { const [num, den] = amount.get(ing); return num * (lcm / den); }); const g = whole.reduce(gcd); const key = ings.map((ing, k) => `${ing}:${whole[k] / g}`).join(" "); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 if (!groups.has(key)) groups.set(key, []); groups.get(key).push(name);}const out = [String(groups.size)];for (const [key, names] of groups) out.push(`${key} = ${names.join(" ")}`);console.log(out.join("\n"));
TypeScriptmain.ts · 42 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));type Frac = [num: number, den: number];const n = Number(lines[0]);const groups = new Map<string, string[]>(); // 비율 열쇠(문자열) → 요리 이름들. Map은 넣은 차례를 지킨다for (let i = 1; i <= n; i++) { const parts = lines[i].trim().split(" "); const name = parts[0]; const c = Number(parts[1]); const amount = new Map<string, Frac>(); // 재료 → [분자, 분모](약분해 둔다). 같은 재료가 또 나오면 더한다 for (let j = 0; j < c; j++) { const ing = parts[2 + 2 * j]; const [p, q = "1"] = parts[3 + 2 * j].split("/"); // "3/4" → 3, 4 / "2" → 2, 1 const [a, b] = amount.get(ing) ?? [0, 1]; const num = a * Number(q) + Number(p) * b; const den = b * Number(q); const g = gcd(num, den); amount.set(ing, [num / g, den / g]); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 let lcm = 1; for (const [, den] of amount.values()) lcm = (lcm / gcd(lcm, den)) * den; const ings: string[] = [...amount.keys()].sort(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 const whole: number[] = ings.map((ing) => { const [num, den] = amount.get(ing)!; return num * (lcm / den); }); const g = whole.reduce(gcd); const key = ings.map((ing, k) => `${ing}:${whole[k] / g}`).join(" "); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 const names = groups.get(key); if (names) names.push(name); else groups.set(key, [name]);}const out: string[] = [String(groups.size)];for (const [key, names] of groups) out.push(`${key} = ${names.join(" ")}`);console.log(out.join("\n"));
JavaMain.java · 45 lines
import java.io.*;import java.util.*;public class Main { static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); // 비율 열쇠 → 요리 이름들. LinkedHashMap은 넣은 차례를 지킨다(HashMap은 차례가 제멋대로) Map<List<String>, List<String>> groups = new LinkedHashMap<>(); for (int i = 0; i < n; i++) { String[] parts = br.readLine().trim().split(" "); String name = parts[0]; int c = Integer.parseInt(parts[1]); // 재료 → {분자, 분모}(약분해 둔다). TreeMap이라 이름 차례로 늘어선다 TreeMap<String, int[]> amount = new TreeMap<>(); for (int j = 0; j < c; j++) { String ing = parts[2 + 2 * j]; String[] pq = parts[3 + 2 * j].split("/"); int p = Integer.parseInt(pq[0]); int q = pq.length > 1 ? Integer.parseInt(pq[1]) : 1; int[] f = amount.getOrDefault(ing, new int[] {0, 1}); int num = f[0] * q + p * f[1], den = f[1] * q; // 같은 재료가 또 나오면 더한다 int g = gcd(num, den); amount.put(ing, new int[] {num / g, den / g}); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int lcm = 1; for (int[] f : amount.values()) lcm = lcm / gcd(lcm, f[1]) * f[1]; int g = 0; for (int[] f : amount.values()) g = gcd(g, f[0] * (lcm / f[1])); // 열쇠는 List<String>: List는 내용으로 equals·hashCode를 만든다(배열 String[]은 같은 객체일 때만 같다) List<String> key = new ArrayList<>(); for (Map.Entry<String, int[]> e : amount.entrySet()) key.add(e.getKey() + ":" + e.getValue()[0] * (lcm / e.getValue()[1]) / g); groups.computeIfAbsent(key, k -> new ArrayList<>()).add(name); } StringBuilder sb = new StringBuilder(); sb.append(groups.size()).append('\n'); for (Map.Entry<List<String>, List<String>> e : groups.entrySet()) sb.append(String.join(" ", e.getKey())).append(" = ").append(String.join(" ", e.getValue())).append('\n'); System.out.print(sb); }}
C#Main.cs · 52 lines
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b); static void Main() { int n = int.Parse(Console.ReadLine()!.Trim()); // 비율 열쇠(문자열) → 요리 이름들. 넣은 차례를 따로 적어 둔다(Dictionary의 열거 차례는 약속되어 있지 않다) var groups = new Dictionary<string, List<string>>(); var order = new List<string>(); for (int i = 0; i < n; i++) { var parts = Console.ReadLine()!.Trim().Split(' '); string name = parts[0]; int c = int.Parse(parts[1]); // 재료 → (분자, 분모)(약분해 둔다). 같은 재료가 또 나오면 더한다 var amount = new SortedDictionary<string, (int Num, int Den)>(StringComparer.Ordinal); for (int j = 0; j < c; j++) { string ing = parts[2 + 2 * j]; var pq = parts[3 + 2 * j].Split('/'); int p = int.Parse(pq[0]); int q = pq.Length > 1 ? int.Parse(pq[1]) : 1; var (a, b) = amount.TryGetValue(ing, out var f) ? f : (0, 1); int num = a * q + p * b, den = b * q; int g = Gcd(num, den); amount[ing] = (num / g, den / g); } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int lcm = amount.Values.Aggregate(1, (l, f) => l / Gcd(l, f.Den) * f.Den); int gAll = amount.Values.Aggregate(0, (g, f) => Gcd(g, f.Num * (lcm / f.Den))); // SortedDictionary라 이름 차례로 늘어선다. 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 string key = string.Join(" ", amount.Select(e => $"{e.Key}:{e.Value.Num * (lcm / e.Value.Den) / gAll}")); if (!groups.TryGetValue(key, out var names)) { names = new List<string>(); groups[key] = names; order.Add(key); } names.Add(name); } var sb = new StringBuilder(); sb.Append(groups.Count).Append('\n'); foreach (var key in order) sb.Append(key).Append(" = ").Append(string.Join(" ", groups[key])).Append('\n'); Console.Write(sb); }}
C++main.cpp · 56 lines
#include <iostream>#include <map>#include <numeric>#include <string>#include <utility>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; // 비율 열쇠 → 묶음 번호. 열쇠는 (재료, 정수) 쌍의 vector: std::map은 vector도 내용으로 견준다 std::map<std::vector<std::pair<std::string, int>>, int> index; std::vector<std::vector<std::pair<std::string, int>>> keys; // 묶음마다 열쇠(나온 차례대로) std::vector<std::vector<std::string>> names; for (int i = 0; i < n; i++) { std::string name; int c; std::cin >> name >> c; std::map<std::string, std::pair<int, int>> amount; // 재료 → (분자, 분모). std::map이라 이름 차례로 늘어선다 for (int j = 0; j < c; j++) { std::string ing, qs; std::cin >> ing >> qs; // std::stoi("3/4")는 '/' 앞에서 멈춰 3을 준다: 나눗셈 기호를 직접 찾아 자른다 auto slash = qs.find('/'); int p = std::stoi(qs.substr(0, slash)); int q = slash == std::string::npos ? 1 : std::stoi(qs.substr(slash + 1)); auto [it, fresh] = amount.try_emplace(ing, 0, 1); // 같은 재료가 또 나오면 더한다 auto &[num, den] = it->second; int nn = num * q + p * den, dd = den * q; int g = std::gcd(nn, dd); num = nn / g, den = dd / g; } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 int l = 1, g = 0; for (const auto &[ing, f] : amount) l = std::lcm(l, f.second); for (const auto &[ing, f] : amount) g = std::gcd(g, f.first * (l / f.second)); std::vector<std::pair<std::string, int>> key; for (const auto &[ing, f] : amount) key.emplace_back(ing, f.first * (l / f.second) / g); auto [it, fresh] = index.try_emplace(key, static_cast<int>(keys.size())); if (fresh) { keys.push_back(key); names.emplace_back(); } names[it->second].push_back(name); } std::cout << keys.size() << '\n'; for (size_t k = 0; k < keys.size(); k++) { for (size_t t = 0; t < keys[k].size(); t++) std::cout << (t ? " " : "") << keys[k][t].first << ':' << keys[k][t].second; std::cout << " ="; for (const auto &nm : names[k]) std::cout << ' ' << nm; std::cout << '\n'; }}
Cmain.c · 67 lines
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 2000#define MAXC 10#define KEYLEN 256 /* 재료 10개 × ("이름 10글자" + ":" + 수 8자리 + 빈칸) */typedef struct { char ing[11]; int num, den; /* 지금까지 더한 양(약분해 둔다) */} Item;static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }static int by_name(const void *x, const void *y) { return strcmp(((const Item *)x)->ing, ((const Item *)y)->ing); }static char keys[MAXN][KEYLEN]; /* 묶음마다 비율 열쇠(나온 차례대로) */static char names[MAXN][11]; /* 요리 이름 */static int group_of[MAXN]; /* 요리 → 묶음 번호 */int main(void) { int n, groups = 0; if (scanf("%d", &n) != 1) return 0; for (int i = 0; i < n; i++) { int c, k = 0; Item item[MAXC]; scanf("%10s %d", names[i], &c); for (int j = 0; j < c; j++) { char ing[11], qs[16]; int p, q = 1; scanf("%10s %15s", ing, qs); if (sscanf(qs, "%d/%d", &p, &q) < 2) q = 1; /* "2"는 2/1 */ int t = 0; while (t < k && strcmp(item[t].ing, ing) != 0) t++; /* 같은 재료가 또 나오면 더한다 */ if (t == k) { strcpy(item[k].ing, ing); item[k].num = 0, item[k].den = 1; k++; } int num = item[t].num * q + p * item[t].den, den = item[t].den * q; int g = gcd(num, den); item[t].num = num / g, item[t].den = den / g; } qsort(item, k, sizeof(Item), by_name); /* 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 */ /* 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 */ int lcm = 1, g = 0; for (int t = 0; t < k; t++) lcm = lcm / gcd(lcm, item[t].den) * item[t].den; for (int t = 0; t < k; t++) g = gcd(g, item[t].num * (lcm / item[t].den)); char key[KEYLEN]; int len = 0; for (int t = 0; t < k; t++) /* 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 */ len += snprintf(key + len, KEYLEN - len, "%s%s:%d", t ? " " : "", item[t].ing, item[t].num * (lcm / item[t].den) / g); int found = 0; while (found < groups && strcmp(keys[found], key) != 0) found++; /* 요리 2,000개라 앞에서부터 찾아도 빠르다 */ if (found == groups) strcpy(keys[groups++], key); group_of[i] = found; } printf("%d\n", groups); for (int g = 0; g < groups; g++) { printf("%s =", keys[g]); for (int i = 0; i < n; i++) if (group_of[i] == g) printf(" %s", names[i]); printf("\n"); } return 0;}
Craykonmain.cray · 72 lines
최대공약수(a, b){ while (b != 0) { t = a % b; a = b; b = t; } return a;}n = Console.ReadLine().Trim().ToNumber();groups = Dict(); // 비율 열쇠(문자열) → 요리 이름들. 사전의 열쇠목록은 넣은 차례를 지킨다for (i = 0; i < n; i++){ parts = Console.ReadLine().Trim().Split(" "); name = parts[0]; c = parts[1].ToNumber(); num = Dict(); // 재료 → 지금까지 더한 양의 분자(약분해 둔다). 같은 재료가 또 나오면 더한다 den = Dict(); // 재료 → 분모 for (j = 0; j < c; j++) { ing = parts[2 + 2 * j]; pq = parts[3 + 2 * j].Split("/"); // "3/4" → ["3", "4"], "2" → ["2"] p = pq[0].ToNumber(); q = 1; if (pq.Count > 1) { q = pq[1].ToNumber(); } if (!num.Contains(ing)) { num[ing] = 0; den[ing] = 1; } a = num[ing] * q + p * den[ing]; b = den[ing] * q; g = 최대공약수(a, b); num[ing] = a / g; den[ing] = b / g; } // 분모의 최소공배수를 곱해 정수로 만들고, 다시 최대공약수로 나눠 가장 작은 정수 비로 만든다 ings = num.Keys; ings.Sort(); // 이름 차례로 늘어놓아야 같은 비율이 같은 열쇠가 된다 lcm = 1; foreach (x in ings) { lcm = lcm / 최대공약수(lcm, den[x]) * den[x]; } g = 0; foreach (x in ings) { g = 최대공약수(g, num[x] * (lcm / den[x])); } 조각 = []; foreach (x in ings) { 조각.Add(x + ":" + num[x] * (lcm / den[x]) / g); // 빈칸과 :로 나눠야 b1:2와 b:12가 섞이지 않는다 } key = 조각.Join(" "); if (!groups.Contains(key)) { groups[key] = []; } groups[key].Add(name);}Console.WriteLine(groups.Count);foreach (key in groups.Keys){ Console.WriteLine(key + " = " + groups[key].Join(" "));}