Person 1 has died and left M won, which is divided down the family tree.
People are numbered 1 to n, and everyone except person 1 is the child of exactly one person. Everyone is a descendant of person 1.
Each person is either alive or has already died (dead), and person 1 is dead.
First decide who can be an heir. A living person can be an heir. A dead person can be an heir only if at least one of their children can be an heir.
When person p receives X won, it is divided only among those of p's children who can be heirs. If there are c such children, each receives the quotient of X divided by c, and the remaining r won go 1 won each to the first r of those c children, eldest first.
A child who receives a share and is alive keeps it. If the child is dead, the share passes down to that child's children by the same rule.
Start this with person 1's M won. If none of person 1's children can be an heir, all M won go to the state treasury.
The first line gives n and M, and the next n lines give persons 1 to n in order as "status k child1 … childk". Values are separated by single spaces. The status is alive or dead, and children are listed from eldest to youngest (this may differ from their numbers).
On the first line, print the money each of persons 1 to n received and kept, separated by single spaces. Dead people and people who received nothing get 0.
On the second line, print the money that went to the treasury, or 0 if none did. Amounts are plain digits without commas.
Try writing one recursive function that decides who can be an heir and another that passes the money down.
Input
1 ≤ n ≤ 1,000, 0 ≤ M ≤ 1,000,000,000,000 (integer). k is 0 or more; everyone except person 1 appears exactly once as someone's child, and person 1 never appears as a child. Person 1's status is dead. The number of generations from person 1 to the farthest person is at most 1,000 (a family can be a single line)
Output
Two lines
Example 1 · stdin
7 101
dead 3 2 3 4
alive 0
dead 2 5 6
dead 1 7
alive 0
alive 0
dead 0
stdout
0 51 0 0 25 25 0
0
Example 2 · stdin
3 7
dead 2 2 3
dead 0
dead 0
stdout
0 0 0
7
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
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 same rule repeats on every branch of the family tree, so two recursive functions that 'settle everything below this person' solve it. One decides heirs from the bottom up (settle the children first, then the person), and the other sends shares from the top down. The tables both functions share (alive or not, children, money received) live in outer variables in Python/JS/TS, static fields or global arrays in Java/C#/C, global vectors in C++, and names created at the top level of the program in Craykon. Five traps: ① a dead person is an heir only if they have a child who can be an heir, not merely a child. If the children and grandchildren all died earlier, that person is not an heir and takes no share. That is why deciding heirs is recursive too. ② when deciding heirs, Python any(), JS/TS some() and || in C/C++/Java/C# stop at the first true and skip the remaining children without settling them. Settle every child first, then combine the results. ③ divide by the number of children who can be heirs. Dividing by all children loses the shares of children who are not heirs. The remainder goes 1 won each, eldest first. ④ a family in a single line makes the recursion go 1,000 levels deep. Python's default recursion limit is 1,000, so raise it with sys.setrecursionlimit. The other languages are fine at this depth, and Craykon also handles calls about 3,000 deep. ⑤ M goes up to 10^12, so read it as long long/long in C, C++, Java and C#; int only reaches about 2.1 billion. Python int is unbounded, and numbers in JS/TS/Craykon are exact up to 2^53, so they are fine. Quotient and remainder are Python divmod, JS/TS Math.floor(x / c) and %, Craykon Mathf.Quot(x, c) (수학.몫(x, c)) and %, and integer / and % elsewhere (money is never negative, so the rounding direction does not matter).
Pythonmain.py · 49 lines
import syssys.setrecursionlimit(10000) # 세대가 1,000까지 이어진다. 기본 한도(1,000)로는 모자란다lines = sys.stdin.read().split("\n")n, money = map(int, lines[0].split())alive = [False] * (n + 1)children = [[] for _ in range(n + 1)]for i in range(1, n + 1): p = lines[i].split() alive[i] = p[0] == "alive" children[i] = [int(c) for c in p[2:]]heir = [False] * (n + 1)def mark(p): """p가 상속인이 될 수 있는지 정한다. 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다.""" found = False for c in children[p]: if mark(c): # 자식을 모두 정해 두어야 하므로 any()로 일찍 멈추지 않는다 found = True heir[p] = alive[p] or found return heir[p]got = [0] * (n + 1)def share(p, amount): """p에게 온 amount를 p의 상속인 자식들에게 나눈다.""" heirs = [c for c in children[p] if heir[c]] each, rest = divmod(amount, len(heirs)) for i, c in enumerate(heirs): part = each + (1 if i < rest else 0) # 나머지는 맏이부터 1원씩 if alive[c]: got[c] += part else: share(c, part) # 먼저 떠난 자식의 몫은 그 자식들에게 내려간다mark(1)treasury = 0if any(heir[c] for c in children[1]): share(1, money)else: treasury = moneyprint(" ".join(map(str, got[1:])))print(treasury)
JavaScriptmain.js · 38 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, money] = lines[0].trim().split(" ").map(Number); // 10^12도 number(2^53까지 정확)로 충분하다const alive = [false];const children = [[]];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(" "); alive.push(p[0] === "alive"); children.push(p.slice(2).map(Number));}const heir = new Array(n + 1).fill(false);// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다function mark(p) { let found = false; for (const c of children[p]) if (mark(c)) found = true; // some()은 일찍 멈춰서 뒤의 자식을 정하지 못한다 heir[p] = alive[p] || found; return heir[p];}const got = new Array(n + 1).fill(0);// p에게 온 amount를 p의 상속인 자식들에게 나눈다function share(p, amount) { const heirs = children[p].filter((c) => heir[c]); const each = Math.floor(amount / heirs.length); const rest = amount % heirs.length; heirs.forEach((c, i) => { const part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 });}mark(1);let treasury = 0;if (children[1].some((c) => heir[c])) share(1, money);else treasury = money;console.log(got.slice(1).join(" "));console.log(String(treasury));
TypeScriptmain.ts · 40 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, money] = lines[0].trim().split(" ").map(Number); // 10^12도 number(2^53까지 정확)로 충분하다const alive: boolean[] = [false];const children: number[][] = [[]];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(" "); alive.push(p[0] === "alive"); children.push(p.slice(2).map(Number));}const heir: boolean[] = new Array<boolean>(n + 1).fill(false);// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다function mark(p: number): boolean { let found = false; for (const c of children[p]) if (mark(c)) found = true; heir[p] = alive[p] || found; return heir[p];}const got: number[] = new Array<number>(n + 1).fill(0);// p에게 온 amount를 p의 상속인 자식들에게 나눈다function share(p: number, amount: number): void { const heirs = children[p].filter((c) => heir[c]); const each = Math.floor(amount / heirs.length); const rest = amount % heirs.length; heirs.forEach((c, i) => { const part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 });}mark(1);let treasury = 0;if (children[1].some((c) => heir[c])) share(1, money);else treasury = money;console.log(got.slice(1).join(" "));console.log(String(treasury));
JavaMain.java · 59 lines
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main { static boolean[] alive, heir; static int[][] children; static long[] got; // p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다 static boolean mark(int p) { boolean found = false; for (int c : children[p]) if (mark(c)) found = true; heir[p] = alive[p] || found; return heir[p]; } // p에게 온 amount를 p의 상속인 자식들에게 나눈다 static void share(int p, long amount) { List<Integer> heirs = new ArrayList<>(); for (int c : children[p]) if (heir[c]) heirs.add(c); long each = amount / heirs.size(), rest = amount % heirs.size(); for (int i = 0; i < heirs.size(); i++) { int c = heirs.get(i); long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 } } public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]); long money = Long.parseLong(first[1]); // 10^12는 int를 넘는다 alive = new boolean[n + 1]; heir = new boolean[n + 1]; children = new int[n + 1][]; got = new long[n + 1]; for (int i = 1; i <= n; i++) { String[] p = in.readLine().trim().split(" "); alive[i] = p[0].equals("alive"); int k = Integer.parseInt(p[1]); children[i] = new int[k]; for (int j = 0; j < k; j++) children[i][j] = Integer.parseInt(p[2 + j]); } mark(1); boolean anyHeir = false; for (int c : children[1]) if (heir[c]) anyHeir = true; long treasury = 0; if (anyHeir) share(1, money); else treasury = money; StringBuilder out = new StringBuilder(); for (int i = 1; i <= n; i++) out.append(i > 1 ? " " : "").append(got[i]); out.append('\n').append(treasury).append('\n'); System.out.print(out); }}
C#Main.cs · 57 lines
using System;using System.Collections.Generic;using System.Linq;class Program{ static bool[] alive = Array.Empty<bool>(), heir = Array.Empty<bool>(); static int[][] children = Array.Empty<int[]>(); static long[] got = Array.Empty<long>(); // p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다 static bool Mark(int p) { bool found = false; foreach (int c in children[p]) if (Mark(c)) found = true; heir[p] = alive[p] || found; return heir[p]; } // p에게 온 amount를 p의 상속인 자식들에게 나눈다 static void Share(int p, long amount) { List<int> heirs = children[p].Where(c => heir[c]).ToList(); long each = amount / heirs.Count, rest = amount % heirs.Count; for (int i = 0; i < heirs.Count; i++) { int c = heirs[i]; long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else Share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 } } static void Main() { string[] first = Console.ReadLine()!.Trim().Split(' '); int n = int.Parse(first[0]); long money = long.Parse(first[1]); // 10^12는 int를 넘는다 alive = new bool[n + 1]; heir = new bool[n + 1]; children = new int[n + 1][]; children[0] = Array.Empty<int>(); got = new long[n + 1]; for (int i = 1; i <= n; i++) { string[] p = Console.ReadLine()!.Trim().Split(' '); alive[i] = p[0] == "alive"; children[i] = p.Skip(2).Select(int.Parse).ToArray(); } Mark(1); long treasury = 0; if (children[1].Any(c => heir[c])) Share(1, money); else treasury = money; Console.WriteLine(string.Join(" ", got.Skip(1))); Console.WriteLine(treasury); }}
C++main.cpp · 59 lines
#include <iostream>#include <string>#include <vector>int n;std::vector<bool> alive, heir;std::vector<std::vector<int>> children;std::vector<long long> got; // 10^12는 int를 넘는다// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다bool mark(int p) { bool found = false; for (int c : children[p]) if (mark(c)) found = true; // ||로 이으면 짧은 계산 때문에 뒤의 자식을 정하지 못한다 heir[p] = alive[p] || found; return heir[p];}// p에게 온 amount를 p의 상속인 자식들에게 나눈다void share(int p, long long amount) { std::vector<int> heirs; for (int c : children[p]) if (heir[c]) heirs.push_back(c); long long count = static_cast<long long>(heirs.size()); long long each = amount / count, rest = amount % count; for (long long i = 0; i < count; i++) { int c = heirs[i]; long long part = each + (i < rest ? 1 : 0); // 나머지는 맏이부터 1원씩 if (alive[c]) got[c] += part; else share(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 }}int main() { std::ios::sync_with_stdio(false); long long money; std::cin >> n >> money; alive.assign(n + 1, false); heir.assign(n + 1, false); children.assign(n + 1, {}); got.assign(n + 1, 0); for (int i = 1; i <= n; i++) { std::string st; int k; std::cin >> st >> k; alive[i] = st == "alive"; children[i].resize(k); for (int& c : children[i]) std::cin >> c; } mark(1); bool anyHeir = false; for (int c : children[1]) if (heir[c]) anyHeir = true; long long treasury = 0; if (anyHeir) share(1, money); else treasury = money; for (int i = 1; i <= n; i++) std::cout << (i > 1 ? " " : "") << got[i]; std::cout << '\n' << treasury << '\n';}
Cmain.c · 58 lines
#include <stdio.h>#include <string.h>#define MAXN 1001static int alive[MAXN], heir[MAXN];static int kidStart[MAXN], kidCount[MAXN], kids[MAXN]; /* p의 자식은 kids[kidStart[p]]부터 kidCount[p]개 */static long long got[MAXN]; /* 10^12는 int를 넘는다 *//* p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다 */static int mark(int p) { int found = 0; for (int j = 0; j < kidCount[p]; j++) if (mark(kids[kidStart[p] + j])) found = 1; heir[p] = alive[p] || found; return heir[p];}/* p에게 온 amount를 p의 상속인 자식들에게 나눈다 */static void share(int p, long long amount) { int count = 0; for (int j = 0; j < kidCount[p]; j++) if (heir[kids[kidStart[p] + j]]) count++; long long each = amount / count, rest = amount % count; int i = 0; for (int j = 0; j < kidCount[p]; j++) { int c = kids[kidStart[p] + j]; if (!heir[c]) continue; long long part = each + (i < rest ? 1 : 0); /* 나머지는 맏이부터 1원씩 */ i++; if (alive[c]) got[c] += part; else share(c, part); /* 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 */ }}int main(void) { int n; long long money; scanf("%d %lld", &n, &money); int used = 0; for (int i = 1; i <= n; i++) { char st[8]; scanf("%7s %d", st, &kidCount[i]); alive[i] = strcmp(st, "alive") == 0; kidStart[i] = used; for (int j = 0; j < kidCount[i]; j++) scanf("%d", &kids[used++]); } mark(1); int anyHeir = 0; for (int j = 0; j < kidCount[1]; j++) if (heir[kids[kidStart[1] + j]]) anyHeir = 1; long long treasury = 0; if (anyHeir) share(1, money); else treasury = money; for (int i = 1; i <= n; i++) printf(i > 1 ? " %lld" : "%lld", got[i]); printf("\n%lld\n", treasury); return 0;}
Craykonmain.cray · 89 lines
// 함수 안에서 쓰는 이름(p, c, found, amount, 상속자식, 몫, 나머지, part, j)은 아래 본문에서 쓰지 않는다:// 본문 맨 바깥에서 만든 이름(살아있음, 자식, 상속인, 받은돈)은 모든 호출이 함께 쓰는 하나가 된다// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다정하기(p){ found = false; foreach (c in 자식[p]) { if (정하기(c)) { found = true; } } 상속인[p] = 살아있음[p] || found; return 상속인[p];}// p에게 온 amount를 p의 상속인 자식들에게 나눈다나누어주기(p, amount){ 상속자식 = []; foreach (c in 자식[p]) { if (상속인[c]) { 상속자식.Add(c); } } 몫 = Mathf.Quot(amount, 상속자식.Count); 나머지 = amount % 상속자식.Count; for (j = 0; j < 상속자식.Count; j++) { c = 상속자식[j]; part = 몫; if (j < 나머지) { part = 몫 + 1; } if (살아있음[c]) { 받은돈[c] += part; } else { 나누어주기(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 } }}첫줄 = Console.ReadLine().Trim().Split(" ");n = 첫줄[0].ToNumber();돈 = 첫줄[1].ToNumber(); // 10^12도 2^53 안이라 정확하다살아있음 = NewList(n + 1, false);자식 = [[]];상속인 = NewList(n + 1, false);받은돈 = NewList(n + 1, 0);for (i = 1; i <= n; i++){ 칸 = Console.ReadLine().Trim().Split(" "); 살아있음[i] = 칸[0] == "alive"; 목록 = []; for (k = 2; k < 칸.Count; k++) { 목록.Add(칸[k].ToNumber()); } 자식.Add(목록);}정하기(1);상속인있음 = false;foreach (x in 자식[1]){ if (상속인[x]) { 상속인있음 = true; }}국고 = 0;if (상속인있음){ 나누어주기(1, 돈);}else{ 국고 = 돈;}받은돈.RemoveAt(0);Console.WriteLine(받은돈.Join(" "));Console.WriteLine(국고);