• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

مهدی به تازگی با نظریه گراف آشنا شده و درخت‌ها را مورد بررسی قرار داده است. او به درخت‌هایی علاقه‌مند است که تعداد برگ‌هایشان از تعداد رئوس غیر برگشان بیش‌تر است. به همین دلیل او این درخت‌ها را درخت‌های خوب می‌نامد. با توجه به علاقه شدید او به این خاصیت در درخت‌ها او به دنبال درخت‌هایی می‌گردد که همیشه خوب باشند. او برای این‌که ببیند یک درخت همیشه خوب است، ابتدا بررسی می‌کند که خود درخت خوب باشد و سپس می‌خواهد ببیند آیا می‌توان راسی را از درخت حذف کرد که جنگل باقی‌مانده باز هم خوب باقی بماند. او می‌خواهد آن‌قدر این کار را بکند تا هیچ راسی در درخت باقی نماند، اگر درختی چنین ویژگی‌ها را داشت، احتمالا مهدی خیلی خوشحال می‌شود، زیرا یک درخت همیشه خوب یافته است. لازم به ذکر است هنگام حذف کردن یک راس از یک درخت آن راس و همه‌ یال‌های مجاورش به همراه رئوسی که درجه‌شان صفر شده از درخت حذف می‌شوند.

در این مسئله قرار است شما به مهدی کمک کنید و بگویید آیا یک جنگل همیشه خوب است یا نه و در صورت همیشه خوب بودن ترتیبی از حذف رئوس را ارائه دهید که در همه مراحل جنگل باقی‌مانده همیشه خوب باقی بماند.

ورودی🔗

در سطر اول ورودی $n$ تعداد رئوس درخت می‌آید.

در $n$ سطر بعدی در خط $i$ام ابتدا $k$ تعداد رئوس مجاور راس $i$ام می‌آید و سپس $k$ عدد می‌آید که شماره رئوس مجاور راس $i$ام می‌باشند. رئوس از ۱ تا $n$ شماره‌گذاری شده‌اند.

$1 \le n \le 1\ 000\ 000$

خروجی🔗

در سطر اول خروجی اگر درخت ورودی درختی همیشه خوب است، عبارت Always Good Tree را چاپ نمایید. اگر درخت ورودی، درختی همیشه خوب نیست درتنها خط خروجی عبارت Discouraging Tree را چاپ نمایید.

در سطر دوم ابتدا تعداد رئوسی که مستقیما حذف می‌کنید را بنویسید و سپس شماره رئوسی که از درخت حذف کرده‌اید را به ترتیب حذف شدن بنویسید.

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

5
1 2
2 1 3
2 2 4
2 3 5
1 4

خروجی نمونه ۱🔗

Discouraging Tree

ورودی نمونه ۲🔗

5
4 2 3 4 5
1 1
1 1
1 1
1 1

خروجی نمونه ۲🔗

Always Good Tree
1 1

ورودی نمونه ۳🔗

5
2 2 3
1 1
3 1 4 5
1 3
1 3

خروجی نمونه ۳🔗

Always Good Tree
2 1 3

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

ژنرال باخ خود را برای جنگی تازه آماده می‌کند. او تصمیم دارد که در این جنگ، نیروهای خود را در قلعه نگاه دارد و از آن‌جا دفاع کند. نقشه قلعه به صورت یک جدول $n \times n$ است که برخی از خانه‌های آن خالی و برخی از خانه‌های آن دیوار است. یک پایگاه به یک مجموعه از خانه‌های خالی گفته می‌شود که از هر کدام از آن‌ها بتوان با طی کردن تنها خانه‌های خالی (با مجاورت ضلعی) به دیگری رسید. چون که پایگاه‌ها به وسیله دیوارها از یک‌دیگر جدا شده‌اند، در هنگام جنگ با یک‌دیگر ارتباط ندارند و بنابراین هر کدام از آن‌ها نیاز به یک فرمانده دارند. اما چون ژنرال تنها $k$ فرمانده دارد، بنابراین نیاز دارد که تنها $k$ پایگاه داشته باشد. بنابراین باید با متصل کردن پایگاه‌ها به یک‌دیگر، تعداد آن‌ها را کاهش دهد. به دلیل فرسوده بودن قلعه، ژنرال تصمیم گرفته است که به جای خراب کردن دیوار‌های بین پایگاه‌ها، آن‌ها را با استفاده از پل به یک‌دیگر متصل کند. یک پل به طول $L$ پلی است که بر روی $L$ دیوار متوالی ساخته می‌شود. توجه کنید که زیر هر پل باید کاملا دیوار قرار داشته باشد و همچنین یک پل یا به صورت شرقی-غربی قرار دارد یا به صورت شمالی-جنوبی. همچنین هیچ دو پلی در یک ارتفاع ساخته نمی‌شوند. به این معنی که اگر یک پل شرقی-غربی با یک پل شمالی-جنوبی تقاطع داشته باشند، یکی از آن‌ها بر روی دیگری رد می‌شوند و کسی نمی‌تواند از روی یک پل به دیگری برود. کشیدن یک پل به طول $L$، $L$ سکه طلا خرج دارد. حال ژنرال می‌خواهد با کم‌ترین هزینه کاری کند که تعداد پایگاه‌ها کم‌تر مساوی تعداد فرماندهان شود اما از آن‌جا که از مسائل بهینه‌سازی خیلی سر در نمی‌آورد، از شما خواسته است که این کار را برای او انجام دهید.

ورودی🔗

در سطر اول ورودی، $n$ ابعاد نقشه و سپس $k$ تعداد فرماندهان ژنرال آمده است. $1 \le n \le 1\ 000$

در n سطر بعد، در هر سطر یک رشته به طول $n$ از $W$ و $E$ آمده است که $W$ نشان‌دهنده دیوار است و $E$ نشان‌دهنده‌ی خانه خالی است. البته در نقشه، همواره سطر اول و آخر و ستون اول و آخر دیوار هستند که در واقع همان دیوارهای دور قلعه هستند.

خروجی🔗

در تنها سطر خروجی شما باید کم‌ترین تعداد سکه‌ای که ژنرال باید مصرف کند تا تعداد پایگاه‌ها کم‌تر مساوی $k$ شود را چاپ کنید.

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

5 3
WWWWW
WEWEW
WWWWW
WEWEW
WWWWW

خروجی نمونه ۱🔗

1

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

یوری پسر جومونگ می‌خواهد لذت مردم گوگوریو از زندگی را به حد اعلا برساند. در گوگوریو $n$ نفر زندگی می‌کنند و در انبارهای گوگوریو $m$ کیلو ترب وجود دارد. یوری برای بیشینه کردن لذت مردم، می‌خواهد تمام ترب‌ها را بین مردم تقسیم کند. هر فرد در گوگوریو با توجه به میزان تربی که به او می‌رسد خوشحال می‌شود(به وضوح هر چی بیشتر ترب به یک نفر برسد، بیشتر خوشحال می‌شود.)

فرض کنید فرد $i$ ام در گوگوریو با $x$ کیلو ترب، به میزان $s_i(x)$ شودوکی (شودوکی واحد خوشحالی مردم در گوگوریو می‌باشد) خوشحال می‌شود (تابع $s_i(x)$ یک تابع اکیدا صعودی بر حسب $x$ می‌باشد). همچنین رابطه‌ زیر برای هر تابع $s_i$، به ازای هر $x$ و $y$ (که $x < y$)، برقرار است:

$s_i(x) + s_i(y) \le s_i(x + 1) + s_i(y - 1)$

هدف یوری بیشینه کردن مجموع لذتی است که مردم در گوگوریو می‌برند.

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

ورودی🔗

در این سوال، ورودی توسط کتابخانه از فایل ورودی خوانده می‌شود. دقت کنید هیچ چیزی توسط برنامه شما نباید از ورودی خوانده شود. فرمت فایل ورودی برای کتاب‌خانه ی مثالی که به شما داده‌ایم به شکل زیر است:

در سطر اول دو عدد $n$ و $m$ آمده‌است که $n$ جمعیت مردم گوگوریو و $m$ میزان (به کیلو) ترب موجود در انبار‌های گوگوریو است.

$1 \le m, n \le 1 \ 000\ 000$

خروجی🔗

در این سوال شما باید بیشترین مجموع لذتی که مردم گوگوریو می‌توانند ببرند را به کتابخانه گزارش دهید. دقت کنید که هیچ چیزی توسط برنامه شما نباید در خروجی نوشته شود.

زیرمسئله‌ها🔗

کتابخانه🔗

باید این سوال را به زبان ++C پیاده‌سازی کنید.

کدهای مورد نیازتان در این فایل فشرده موجود هستند. توضیحات:

شما در این سوال باید برای دریافت اطلاعات تابع لذت افراد از کتابخانه‌ای که در اختیار کد شما قرار داده می‌شود استفاده کنید. برای این منظور فایل‌های کتابخانه‌ی lezatlib.h و lezatlib.cpp در اختیار شما قرار داده شده‌است. برای اینکه بتوانید از کتابخانه مورد نظر استفاده کنید باید در بالای برنامه خود، کتابخانه lezatlib.h را include کنید:

#include "lezatlib.h"

برای compile کردن برنامه خود می‌توانید از دستور زیر استفاده کنید:

g++ yourProgram.cpp lezatlib.cpp

همچنین توابعی با فرمت زیر در کتابخانه قرار دارد:

Initialize();
int getN();
int getM();
int getLezat(int, int);
void reportSol(int);

شما باید در ابتدای برنامه خود، تابع initialize() را از کتابخانه فراخوانی کنید؛ در غیر این صورت رفتار کتابخانه غیرقابل استناد می‌باشد. بعد از آن با فراخوانی توابع getN() و getM() می‌توانید مقادیر $n$ و $m$ را از کتابخانه بگیرید.

شما می‌توانید با فراخوانی تابع getLezat(l,x)، مقدار لذتی که فرد $i$ از داشتن $x$ کیلو ترب می‌برد را از کتابخانه بپرسید (پارامتر اول، شماره فرد و پارامتر دوم میزان ترب را مشخص می‌کند). برای مثال:

int p = getLezat(3,5);

میزان لذتی که فرد ۳ از ۵ کیلو ترب می‌برد را می‌گوید.

در پایان باید مقدار جواب خود را با تابع reportSol(int) به کتابخانه گزارش دهید. بعد از فراخوانی این تابع برنامه شما هیچ فعالیتی نباید انجام دهد.

یک نمونه برنامه‌ای که شما می‌توانید بفرستید: (فایل lezat.cpp در کدهایی که به شما دادیم.)

#include "lezatlib.h"

using namespace std;

int main() {
    initialize();
    int n = getN();
    int m = getM();
    int x = getLezat(n-1,m-1);
    reportSol(x);
    return 0;
}

دقت کنید که کتابخانه‌ای که به شما به عنوان نمونه داده شده است، کتاب‌خانه‌ای نیست که برنامه‌ی شما با آن تست می‌شود و صرفاً جهت یک مثال به شما داده شده است.