پاسخ سوال رییس و کارخانه شکلات‌سازی کوئرا

پاسخ سوال رییس و کارخانه شکلات‌سازی کوئرا

در این نوشته تمرین “کارخانه شکلات‌سازی” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال رییس و کارخانه شکلات‌سازی کوئرا

بعد از انقلاب صنعتی، مربّاها در کارخانه‌های ویژه‌ای که توسط انسان‌ها اداره می‌شود، تولید می‌شوند. در این کارخانه‌ها مراتب اداری از هر چیز دیگری مهم‌تر است. مراتب اداری در این کارخانه‌ها به این صورت است که آقای شماره‌ی ۱، رییس کارخانه است و همه‌ی کارهای کارخانه زیر نظر او انجام می‌گیرد. پس از رییس کارخانه، کارگران رتبه‌ی اول قرار دارند که همگی تحت فرمان مستقیم رییس کارخانه هستند. هم‌چنین به ازای هر i > 1، هر کارگر رتبه‌ی iام تحت فرمان مستقیم دقیقا یکی از کارگرهای رتبه‌ی $i-1$ هستند. بعلاوه، اگر انسان $x$ تحت فرمان انسان $y$ است و انسان y تحت فرمان انسان z باشد، انسان x تحت فرمان انسان z هم هست و هیچ‌کس دیگری در هیچ‌حالتی (به جز دو حالت تحت فرمان مستقیم و با واسطه که گفته شدند) تحت فرمان کس دیگری نیست. این سلسله مراتب سخت اداری، برای جلوگیری از فساد به وجود آمده؛ بدین صورت که اگر یک روز i نفر از افراد تحت‌فرمان مستقیم انسان x فساد کنند، انسان $x$ علاوه بر پرداخت جریمه‌ی فساد آن‌ها، باید به تعداد کسانی که به هر ترتیبی تحت فرمان او بودند و ملزم به پرداخت جریمه شده‌اند هم شیشه بپردازد (شیشه واحد پولی مربّاهاست که از قضا بسیار ارزشمند هم هست). هم‌چنین او یک شیشه‌ هم برای تنبیه خودش باید بپردازد. به مجموع هزینه‌ای که انسان $x$ ملزم به پرداخت آن می‌شود، جریمه‌ی انسان $x$ می‌گوییم. در یکی از روزهای گرم و آفتابی تابستان، تمام کسانی که کسی تحت فرمان آن‌ها نبود، فساد کردند و ملزم به پرداخت جریمه‌ی $1$شیشه‌ای شدند. امروز جریمه‌ای که رییس باید بپردازد به دستش رسیده. او از مقدار هزینه‌ای که باید بپردازد ناراضی است، به همین دلیل، از شما خواسته هزینه‌ای که او باید بپردازد را تایید کنید.

ورودی سوال رییس و کارخانه شکلات‌سازی

در خط اول ورودی n تعداد افراد کارخانه می‌آید. در خط دوم ورودی n – 1 عدد می‌آید که عدد $i$ ام، p_i​ است که نشان می‌دهد که انسان i+1 تحت فرمان مستقیم انسان p_i​ است.

$$1\le n\le 100$$

1 ≤ pi​ ≤ n

تضمین می‌شود که همه‌ی انسان‌ها تحت فرمان رییس کارخانه هستند.

خروجی سوال رییس و کارخانه شکلات‌سازی

در تنها خط خروجی تعداد هزینه‌ای که رییس باید بابت جریمه بپردازد را خروجی دهید.

حل سوال رییس و کارخانه شکلات‌سازی

class tree:
    def __init__(self, father, jarime, index):
        self.index = index
        self.children = []
        self.father = father
        self.jarime = jarime

nodes = []

def findjarime(index):
    global nodes
    jar = 0
    childs = nodes[index].children
    count = 0
    for child in childs:
        res = findjarime(child.index)
        jar += res[0]
        count += res[1]
    jar+= count    
    jar += 1
    count += 1
    return jar,count

n = int(input())

line = input()
farman = line.split(" ")


for i in range(n):
    nodes.append(tree(None, None, i))

for i in range(len(farman)):
    nodes[i+1].father = nodes[int(farman[i])-1]
    nodes[int(farman[i])-1].children.append(nodes[i+1])

boss = None
for i in range(n):
    if(nodes[i].father == None):
        boss = i
        break

print(findjarime(boss)[0])

منبع سوال‌: وبسایت کوئرا

اگر روش حل بهتری برای “تمرین رییس و کارخانه شکلات‌سازی” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم. اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.