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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
// 함수 안에서 쓰는 이름(p, c, found, amount, 상속자식, 몫, 나머지, part, j)은 아래 본문에서 쓰지 않는다:// 본문 맨 바깥에서 만든 이름(살아있음, 자식, 상속인, 받은돈)은 모든 호출이 함께 쓰는 하나가 된다// p가 상속인이 될 수 있는지: 살아 있거나, 상속인이 될 수 있는 자식이 하나라도 있으면 된다정하기(p){ found = 假; 遍历 (c 在 자식[p]) { 如果 (정하기(c)) { found = 真; } } 상속인[p] = 살아있음[p] || found; 返回 상속인[p];}// p에게 온 amount를 p의 상속인 자식들에게 나눈다나누어주기(p, amount){ 상속자식 = []; 遍历 (c 在 자식[p]) { 如果 (상속인[c]) { 상속자식.添加(c); } } 몫 = 数学.商(amount, 상속자식.数量); 나머지 = amount % 상속자식.数量; 循环 (j = 0; j < 상속자식.数量; j++) { c = 상속자식[j]; part = 몫; 如果 (j < 나머지) { part = 몫 + 1; } 如果 (살아있음[c]) { 받은돈[c] += part; } 否则 { 나누어주기(c, part); // 먼저 떠난 자식의 몫은 그 자식들에게 내려간다 } }}첫줄 = 控制台.读行().去空白().分割(" ");n = 첫줄[0].转数字();돈 = 첫줄[1].转数字(); // 10^12도 2^53 안이라 정확하다살아있음 = 新列表(n + 1, 假);자식 = [[]];상속인 = 新列表(n + 1, 假);받은돈 = 新列表(n + 1, 0);循环 (i = 1; i <= n; i++){ 칸 = 控制台.读行().去空白().分割(" "); 살아있음[i] = 칸[0] == "alive"; 목록 = []; 循环 (k = 2; k < 칸.数量; k++) { 목록.添加(칸[k].转数字()); } 자식.添加(목록);}정하기(1);상속인있음 = 假;遍历 (x 在 자식[1]){ 如果 (상속인[x]) { 상속인있음 = 真; }}국고 = 0;如果 (상속인있음){ 나누어주기(1, 돈);}否则{ 국고 = 돈;}받은돈.按位置移除(0);控制台.输出(받은돈.连接(" "));控制台.输出(국고);