المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۰:سوال سه

ضدعفونی درخت (۲۰ نمره)

زاریچ که زندگی خود را وقف شکست ویروس کرونا کرده است، عقیده دارد که برای شکست واقعی این ویروس لازم است درخت‌ها نیز ضدعفونی شوند (حتی اگر مفاهیمی ریاضی باشند). یک درخت n رأسی در نظر بگیرید که رأس‌های آن با اعداد ۱، ۲، … و n شماره‌‌گذاری شده‌ باشند. میزان آلودگی هر یال برابر تفاضل شماره‌‌های رأس‌های دو سرش است. مثلا یالی که دو رأس با شماره‌های ۳ و ۵ را به یکدیگر وصل می‌کند دارای آلودگی ۲ است. میزان آلودگی یک درخت برابر مجموع آلودگی یال‌هایش است. زاریچ باید خود را برای پاک‌سازی هر نوع درختی آماده کند. لذا می‌خواهد بداند بیشینه‌ی آلودگی برای یک درخت n رأسی (با رأس‌های شماره‌گذاری شده از ۱ تا n) چه‌قدر است. این مقدار بیشینه را بیابید. دقت کنید که ابتدا باید این مقدار را به ازای هر n به دست آورید و یک درخت n رأسی با بیشینه‌ی آلودگی را توصیف کنید، سپس اثبات کنید که درختی n رأسی با آلودگی بیشتر از آن وجود ندارد.

پاسخ


ابزار صفحه