+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت *****  کاراکتر اصلی ۱ دوست دارد دانش آموزانش (که آن‌ها را با نام کاراکترهای کمکی می‌شناسیم) را به درس هندسه علاقه‌مند کند به همین خاطر از وسیله‌ای کمک آموزشی استفاده می‌کند که یک صفحه با $n$ لامپ است که لامپ‌ها با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند و هم‌چنین در زیر صفحه‌ هم $n$ کلید با شماره‌های ۱ تا $n$ برای روشن کردن لامپ‌ها وجود دارد. هریک از لامپ‌ها به یک کلید در زیر صفحه وصل هستند. به علت مشغله‌ی زیاد، کاراکتر اصلی ۱ فرصت نکرده است هر لامپ را به کلید هم‌شماره‌اش وصل بکند و بصورت تصادفی هر لامپ را به یک کلید وصل کرده است، بطوری که هیچ کلیدی از $n$ کلید زیر صفحه نیست که لامپی به آن متصل نباشد. پس از زنگ تفریح وقتی کاراکتر اصلی ۱ به کلاس بر می‌گردد می‌بیند بعضی لامپ‌ها روشن و بعضی دیگر خاموش‌اند، اما به دلیل این که هر کلید به لامپی که ممکن است هم‌شماره‌اش نباشد متصل است، کار برای کاراکتر اصلی ۱ سخت است، چون او می‌خواهد قبل از جمع کردن وسیله آموزشی لامپ‌هایش را خاموش کند تا باتری آن بیهوده هدر نرود. باتوجه به وضعیت فعلی لامپ‌ها و این‌که هر کلید کدام لامپ را روشن می‌کند، در خروجی شماره‌ی کلیدهایی که باید بزنیم تا همه‌ی لامپ‌ها خاموش شوند را چاپ کنید. # ورودی در خط اول ورودی عدد طبیعی $n$ داده می‌شود. در خط دوم ورودی $n$ عدد طبیعی می‌آیند که $i$امین آن‌ها شماره‌ی کلیدی است که به لامپ $i$ام متصل است. و در خط آخر ورودی $n$ عدد از مجموعه‌ی $\{ 0, 1\}$ می‌آیند که $i$امین عدد نشان‌دهنده‌ی خاموش یا روشن بودن لامپ $i$ام است. اگر عدد $i$ام ۰ باشد یعنی لامپ $i$ام خاموش و در صورتی که عدد $i$ام ۱ باشد، لامپ $i$ام روشن است. $$1 \leq n \leq 100 \ 000$$ # خروجی در یک خط شماره کلیدهایی را چاپ کنید که اگر آن‌ها را **یک‌بار** بفشاریم وضعیت همه‌ی لامپ‌ها در انتها خاموش باشد. دقت کنید ترتیب خروجی دادن شماره کلید‌ها باید صعودی باشد. (یعنی اگر کلیدهایی که فشردن آن‌ها حالت مطلوب را می‌سازد پیدا کنید اما بصورت صعودی چاپشان نکنید نمره‌ی سوال را نمی‌گیرید) # مثال ## ورودی نمونه ``` 10 3 6 1 2 10 4 5 9 8 7 0 0 0 1 1 1 1 1 1 1 ``` ## خروجی نمونه ``` 2 4 5 7 8 9 10 ``` # توضیح در مثال داده‌شده لامپ‌های ۴ تا ۱۰ روشن‌اند و باید آن‌ها را خاموش کنیم، پس نیاز است کلیدهای `2 10 4 5 9 8 7` را فشار دهیم. اما در صورت سوال گفته شده که بایستی کلید‌ها باترتیب صعودی چاپ شوند، پس بجای `2 10 4 5 9 8 7` در خروجی ‍‍`2 4 5 7 8 9 10` را چاپ می‌کنیم.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت *****  امتحانات میان‌ترم نزدیک است و وضعیت هندسه‌ی کاراکترهای کمکی خراب! این موضوع به شدت روی اعتماد به نفس کاراکتر‌های کمکی اثر گذاشته و کاراکتر اصلی ۱ را به فکر انداخته تا برای آن‌ها کلاس تقویتی تشکیل دهد. از بین کاراکترهای کمکی $n$ نفر در این کلاس تقویتی ثبت‌نام کرده‌اند. کلاس تقویتی در کلاسی که $n$ نیمکت آن پشت سر هم و در یک ردیف چیده شده‌اند، برگزار می‌شود. نیمکت‌ها از جلوی کلاس تا انتها با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند. کاراکتر اصلی ۱ در اولین روز تدریسش برای کاراکترهای کمکی متوجه الگوی عجیبی در نشستن کاراکترهای کمکی روی نیمکت‌ها شد. کاراکتر کمکی ۱ که می‌آید روی نیمکت شماره‌ی ۱ می‌نشیند و از کاراکتر کمکی ۲ تا کاراکتر کمکی $n$ نیمکت استرس‌زدا را شناسایی می‌کنند و روی آن می‌نشینند. نیمکتی را استرس‌زدا می‌نامیم که: + خالی باشد. + بیشینه فاصله را تا نزدیک‌ترین نیمکت پر داشته باشد. (واحد فاصله در اینجا تعداد نیمکت‌های بین است) + اگر چند نیمکت با بیشینه فاصله موجود بود، نیمکتی که شماره‌ی آن از بقیه‌ کم‌تر باشد. از آنجایی که کاراکتر اصلی ۱ حوصله ندارد تا نشستن کاراکتر کمکی $n$ صبر کند، پس برنامه‌ای بنویسید که شماره‌ی نیمکتی که کاراکتر کمکی $n$ طبق الگو در آن می‌نشیند را چاپ کند. # ورودی در تنها خط ورودی عدد طبیعی $n$ داده می‌شود. $$1 \leq n \leq 10^{100 \ 000} $$ # خروجی در تنها خط خروجی شماره‌ی نیمکتی که کاراکتر کمکی $n$ در آن می‌نشیند را چاپ کنید. # مثال ## ورودی نمونه ``` 10 ``` ## خروجی نمونه ``` 9 ``` # توضیح در مثال داده شده، کاراکتر کمکی ۱ طبق صورت سوال در نیمکت ۱ می‌نشیند. ``` # # # # # # # # # 1 10 9 8 7 6 5 4 3 2 1 ``` نیمکت استرس‌زدا برای کاراکتر کمکی ۲ نیمکت ۱۰ است، چون با تنها نیمکت پر یعنی نیمکت ۱ بیشترین فاصله را دارد. ``` 2 # # # # # # # # 1 10 9 8 7 6 5 4 3 2 1 ``` برای کاراکتر کمکی ۳، نیمکت‌های ۵ و ۶ هر دو فاصله‌شان تا نزدیک‌ترین نیمکت پر ۳ است و نیمکتی با فاصله‌ی کمتر تا نزدیک‌ترین نیمکت پُرَش وجود ندارد. از بین این دو نیمکت ۵ استرس‌زداست چون شماره‌اش نسبت‌ به نیمکت ۶ کوچکتر است. ``` 2 # # # # 3 # # # 1 10 9 8 7 6 5 4 3 2 1 ``` برای کاراکتر کمکی ۴، ۳ نیمکت وجود دارد که فاصله‌شان تا نزدیک‌ترین نیمکت پر ۱ باشد و بقیه‌ی نیمکت‌های خالی با نزدیک‌ترین نیمکت پر همسایه هستند (فاصله‌شان ۰ است). پس از بین آن ۳ نیمکت که شماره‌هایشان ۳، ۷ و ۸ است، نیمکت ۳ استرس‌زداست. ``` 2 # # # # 3 # 4 # 1 10 9 8 7 6 5 4 3 2 1 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت *****  چند روز پیش و مصادف با روز بعد از اعلام نتایج امتحان هندسه‌ی میان‌ترم، کاراکتر کمکی ۱ در انباری خانه‌شان یک صفحه بازی پیدا کرده که متعلق به پدربزرگ مرحومش (خدا رفتگان شما را هم بیامرزد) است. کاراکتر کمکی ۱ با پیداکردن این صفحه‌ی بازی بسیار خوشحال می‌شود و تصمیم می‌گیرد با دوستش کاراکتر کمکی ۲ برای این‌ صفحه‌ی بازی، بازی‌ای ابداع کنند که با انجام آن اندکی از ناراحتی و غم جان‌سوز اعلام نتایج امتحان هندسه فاصله بگیرند. از آنجایی که قبل از این‌که قرار باشد بازی ابداع شود آن‌ها حتما باید نسبت به صفحه‌ی بازی شناخت پیدا کنند. پس به همین منظور راهنمای صفحه‌ی بازی را مطالعه می‌کنند که اطلاعات مندرج در آن به شرح زیر است: + صفحه‌ی بازی شامل $n$ دایره و $n - 1$ پاره خط است که هر سر هر پاره‌خط به یکی از دایره‌ها متصل است. + دایره‌های صفحه با اعداد متمایز ۱ تا $n$ شماره‌گذاری شده‌اند. + دو دایره‌ را در صفحه‌ی بازی همسایه می‌نامیم اگر و فقط اگر یکی از پاره‌خط‌های صفحه‌ باشد که یک سر آن به یکی از این دو دایره و سر دیگرش به دایره‌ی دیگر متصل باشد. + منظور از **حرکت مهره** در این صفحه‌ی بازی، حرکت دادن مهره از دایره‌ای که روی آن قرار دارد به یکی از همسایه‌های خالی از مهره‌ی آن است. + اگر فقط یک مهره بر روی یکی از دایره‌های صفحه داشته باشیم (برخلاف شرایط بازی) تضمین می‌شود می‌توان با چندبار حرکت‌ دادن مهره، آن را به هر یک از دایره‌های دیگر صفحه رساند. بعد از مطالعه‌ی کامل جزئیات دفترچه‌ی راهنما که در بالا آمده بود، کاراکتر کمکی ۱ و کاراکتر کمکی ۲ توانستند یک بازی بسیار مهیج برای این صفحه‌ی بازی ابداع کنند که مشخصات آن به شرح زیر است: + بازی دو نفره است. + هر بازیکن یک مهره‌ی مخصوص به خود دارد. (بازیکن‌ها در حین بازی می‌توانند وضعیت مهره‌ی حریف را ببینند) + هر یک از دو مهره در ابتدا و حین بازی روی یکی از دایره‌های صفحه قرار می‌گیرند. + هیچ‌گاه دو مهره در یک دایره قرار نمی‌گیرند. + با شروع از کاراکتر اصلی ۱، به نوبت هر بازیکن یک‌بار مهره‌ی خود را حرکت می‌دهد. + بازنده‌ی بازی کسی است که نتواند حرکتی انجام بدهد. یعنی دایره‌ی همسا‌یه‌ی خالی‌ای برای او وجود نداشته باشد که بتواند مهره‌اش را به آن حرکت دهد. دارنده‌ی استراتژی برد، کسی است که با هر نوع بازی طرف مقابل، بتواند طوری بازی کند که در انتها، بازی حتما به نفع خودش تمام شود. برنامه‌ای بنویسید که دارنده‌ی استراتژی برد در بازی را مشخص کند. # ورودی در خط اول ورودی عدد طبیعی $n$ داده می‌شود که نشان دهنده تعداد دایره‌های صفحه‌ی بازی است. در $n -1 $ خط بعدی در هر خط شماره‌ی دو دایره آمده‌اند که نشان‌دهنده‌ی وصل‌بودن این دو دایره توسط یکی از پاره‌خط‌های صفحه است. در خط آخر دو عدد طبیعی $x$ و $y$ داده می‌شود که به ترتیب نشان‌دهنده‌ی شماره دایره‌ی محل ابتدایی مهره‌ی کاراکتر کمکی ۱ و کاراکتر کمکی ۲ است. $$2 \leq n \leq 100 \ 000$$ # خروجی در تنها خط خروجی اگر کاراکتر کمکی ۱ دارنده‌ی استراتژی برد است، `karakter e komaki_1` را چاپ کنید و اگر کاراکتر کمکی ۲ دارنده‌ی استراتژی برد است، `karakter e komaki_2` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 1 3 1 2 ``` ## خروجی نمونه ۱ ``` karakter e komaki_2 ``` ## ورودی نمونه ۲ ``` 4 1 2 1 3 1 4 3 1 ``` ## خروجی نمونه ۲ ``` karakter e komaki_2 ``` ## ورودی نمونه ۳ ``` 7 1 2 1 6 2 3 2 4 2 5 6 7 3 7 ``` ## خروجی نمونه ۳ ``` karakter e komaki_1 ``` # توضیح در مثال اول مهره‌های کاراکتر کمکی ۱ و کاراکتر کمکی ۲ به ترتیب در دایره‌های ۱ و ۲ قرار دارند. در حرکت اول کاراکتر کمکی ۱ تنها می‌تواند به دایره‌‌ی ۳ برود. در حرکت بعدی کاراکتر کمکی ۲ نیز تنها یک حرکت دارد و می‌تواند به دایره‌ی شماره‌ی ۱ برود. حرکت بعدی نوبت کاراکتر کمکی ۱ است که هیچ دایره‌ی همسایه‌ی خالی ندارد، پس برنده‌ی بازی کاراکتر کمکی ۲ است. در مثال دوم مهره‌های کاراکتر کمکی ۱ و کاراکتر کمکی ۲ به ترتیب در دایره‌های ۳ و ۱ قرار دارند. در حرکت اول کاراکتر کمکی ۱ هیچ حرکتی نمی‌تواند انجام بدهد و در همین حرکت اول و بدون هیچ حرکت مهره‌ای کاراکتر کمکی ۲ برنده‌ی بازی است.  در مثال سوم مهره‌های کاراکتر کمکی ۱ و کاراکتر کمکی ۲ به ترتیب در دایره‌های ۳ و ۷ قرار دارند. در حرکت اول کاراکتر کمکی ۱ مجبور است مهره‌اش را به دایره‌ی ۲ ببرد. در حرکت بعدی کاراکتر کمکی ۲ هم مجبور است مهره‌اش را به دایره‌ی ۶ ببرد. از این‌جا به بعد که برای هر یک از دو بازیکن چند حرکت ممکن وجود دارد، برای کاراکتر کمکی ۱ روش برد ارائه می‌دهیم. کاراکتر کمکی ۱ می‌تواند مهره‌اش را به دایره‌ی ۱ ببرد تا کاراکتر کمکی ۲ را مجبور کند در مرحله‌ی بعد مهره‌اش را به دایره‌ی ۷ ببرد و در حرکت آخر کاراکتر کمکی ۱ مهره‌اش را به دایره‌ی ۶ می‌برد تا کاراکتر کمکی ۲ حرکت ممکنی در نوبتش نداشته باشد و برنده‌ی بازی کاراکتر کمکی ۱ شود. 

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت *****  پس از امتحان میان‌ترم هندسه، این‌بار کاراکتر اصلی که به تازگی خوی مبارزه با دانش‌آموز گرفته است سعی دارد از طریق امتحان پایان‌ترم هندسه دانش‌آموزان بی‌گناهش را مورد آزار قرار دهد. کاراکتر کمکی ۱ و کاراکتر کمکی ۲ که هر دو به شدت امتحانشان را خراب کردند به فکر راهی برای انتقام افتادند. انتقام از معلم هندسه‌ی نابکارشان ناشدنی به‌نظر می‌رسد پس به این نتیجه رسیدند که لااقل از برگه‌های امتحانی انتقام بگیرند تا گوشه‌ای از عقده‌ی گوشه‌ی دلشان باز شود. همان‌طور که می‌دانید آن‌ها تنها نیستند و با $n - 2$ دانش‌آموز فلک زده‌ی دیگر دست به یکی کردند تا در روزی مشخص پس از مدرسه جمع شوند و $n$ برگه‌ی امتحانی‌شان را در یک جمع دانش‌آموزی مورد محاکمه قرار بدهند. آن‌ها در دادگاه دانش‌آموزی بین خودشان حکمی برای این برگه‌ها صادر کردند که کاراکتر کمکی ۱ و کاراکتر کمکی ۲ مامور اجرای این حکم هستند. برای هیجان انگیزتر شدن اجرای حکم قضایی، کاراکتر کمکی ۱ و کاراکتر کمکی ۲ تصمیم گرفتند حکم را به یک بازی بین خودشان تبدیل کنند. هدف بازی مجازات همه‌ی $n$ برگه‌ی امتحانی است و قرار است به ترتیبی این مجازات توسط دو بازیکن بازی یعنی کاراکتر کمکی ۱ و کاراکتر کمکی ۲ انجام شود. قوانین انجام بازی به شرح زیر است: + در ابتدا $n$ برگه‌ی امتحانی باید در یک ردیف قرار بگیرند. + هر برگه‌ی امتحانی با توجه به مقدار سختگیری کاراکتر اصلی در تصحیح آن باید مجازات شود، مجازات به این ترتیب است که یک نفر از بین کاراکتر کمکی ۱ و کاراکتر کمکی ۲ به سمت برگه‌ی $i$ام با **_میزان نفرت_** $a_i$ شلیک می‌کند. (دقت کنید ممکن است میزان نفرت مجازات منفی باشد) + بازی نوبتی است و چون کاراکتر کمکی ۱ از لحاظ سنی (و نه از لحاظ عقلی) بزرگتر است، بازی را شروع می‌کند. + در هر مرحله بازیکنی که نوبتش است مختار است یکی از برگه‌ها را به دلخواه به عنوان هدف انجام مجازات انتخاب کند، وقتی برگه‌ای انتخاب شود تمام برگه‌های با شماره‌ی کمتر از آن برگه خود بخود با دیدن مجازات برگه‌ی مجازات شده، مجازات می‌شوند، به عبارت دیگر اگر $i$امین برگه برای مجازات انتخاب شود تمام برگه‌های مجازات‌نشده‌ی با شما‌ره‌ی کم‌تر از $i$ هم مجازات می‌شوند. (هیچ برگه‌ای دوبار مجازات نمی‌شود) + مجموع میزان‌ نفرت‌های **مفید** شلیک‌های انجام شده توسط هر فرد امتیاز فرد در بازی را مشخص می‌کند. مجموع‌ میزان نفرت‌های **مفید** شلیک‌ها یعنی مجموع میزان نفرت لازم برای مجازات تمام برگه‌های انتخاب‌شده توسط هر فرد __و نه تمام برگه‌های مجازات شده توسط فرد__. همان‌طور که قبلا هم اشاره شد در هوش کاراکتر کمکی ۱ و کاراکتر کمکی ۲ شکی نیست، پس یقین داریم بهترین انتخاب‌ها را برای کسب بیشترین مجموع مجازات انجام خواهند داد. در خروجی دو چیز از شما می‌خواهیم: + مشخص کنید چه کسی می‌برد. + اگر مطلوب علاوه بر بردن بازی، با بیشینه اختلاف بردن باشد، شخصی که می‌برد (در صورتی که بازی به مساوی کشیده نشود) حداکثر با چه اختلاف تضمین‌شده‌ای برنده‌ی بازی می‌شود؟ # ورودی در خط اول ورودی عدد طبیعی $n$ داده می‌شود. در خط بعدی ورودی $n$ عدد طبیعی داده می‌شود که $i$امین عدد نشان‌دهنده میزان نفرت لازم برای مجازات برگه‌ی $i$ام است. $$1 \leq n \leq 1 \ 000 \ 000$$ $$|a_i| \leq 1 \ 000 \ 000 \ 000$$ # خروجی در صورتی که بازی با بازی هوشمندانه‌ی دوطرف به مساوی ختم شود، `mosavi` را چاپ کنید، در صورتی که کاراکتر کمکی ۱ بازی را ببرد، `< اختلاف > :karakter e komaki_1` را در خروجی چاپ کنید و در صورتی که کاراکتر کمکی ۲ بازی را ببرد، `< اختلاف > :karakter e komaki_2` را در خروجی چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 6 1 2 100 4 5 99 ``` ## خروجی نمونه ۱ ``` karakter e komaki_1: 99 ``` ## ورودی نمونه ۲ ``` 2 -10 -10 ``` ## خروجی نمونه ۲ ``` mosavi ``` ## ورودی نمونه ۳ ``` 1 -1 ``` ## خروجی نمونه ۳ ``` karakter e komaki_2: 1 ``` # توضیح در مثال اول همان اولین مجازات برای کاراکتر کمکی ۱ کافی است تا بازی را با بیش‌ترین اختلاف ببرد و با انتخاب برگه‌ی ۶ام بازی را با ۹۹ امتیاز اختلاف، به نفع خودش پایان دهد. در مثال دوم اگر در مجازات اول کاراکتر اصلی ۱ برگه‌ی شماره‌ی ۲ را انتخاب کند بازی را با ۱۰ امتیاز اختلاف می‌بازد، پس برگه‌ی شماره‌ی ۱ را انتخاب می‌کند و بازی مساوی می‌شود. در مثال سوم تنها انتخاب کاراکتر کمکی ۱ برای انتخاب کردن برگه‌ی شماره‌ی ۱ است، پس آن را انتخاب می‌کند و بازی به نفع کاراکتر کمکی ۲ با ۱ امتیاز اختلاف تمام می‌شود.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت *****  کاراکترهای کمکی در روز رسمی اعتراض به نمرات امتحان هندسه‌ی پایان‌ترم، هیئتی برای مذاکره با کاراکتر اصلی ۱ می‌فرستند. خوشبختانه کاراکتر اصلی ۱ اهل معامله است و حاضر است دو نوع معامله با هیئت مذاکره‌کننده انجام دهند: 1. نمره‌ی هندسه‌ی $k$ نفر از کاراکترهای کمکی را (به انتخاب هیئت مذاکره‌کننده) از کارنامه‌شان حذف کند و در ازای این‌کار $x \times k$ تومان پول دریافت کند، که $x$ یک عدد طبیعی مشخص و $k$ یک عدد طبیعی دلخواه هستند. 2. نمره‌ی هندسه‌ی $k$ نفر از کاراکترهای کمکی را (به انتخاب هیئت مذاکره‌کننده) یک نمره افزایش دهد و در ازای این‌کار $y \times k$ تومان پول دریافت کند، که $y$ یک عدد طبیعی مشخص و $k$ یک عدد طبیعی دلخواه هستند. توجه کنید هیئت مذاکره‌کننده می‌تواند تنها یک بار از هر نوع معامله استفاده کند. هدف هیئت مذاکره‌کننده فقط یک چیز است و آن هم این است که لیست نمرات هندسه‌ی کاراکترهای کمکی **شرم‌آور** نباشد. لیست نمرات هندسه‌ی کاراکترهای کمکی را **شرم‌آور** می‌دانیم در صورتی که تهی نباشد (یعنی حداقل نمره‌ی هندسه‌ی یکی از کاراکترهای کمکی در کارنامه‌اش آمده باشد) و ب.م.م (بزرگ‌ترین مقسوم‌علیه مشترک) نمرات ۱ باشد. در خروجی برنامه‌ی خود چاپ کنید، حداقل میزان پولی که باید کاراکترهای کمکی پرداخت کنند تا لیست نمرات هندسه از **شرم‌آور**بودن خارج شود، چند تومان است. # ورودی در خط اول ورودی سه عدد طبیعی $n$، $x$ و $y$ به ترتیب نشان‌دهنده‌ی تعداد نمرات لیست اولیه‌ی نمرات هندسه، ضریب قیمت معامله‌ی اول و ضریب قیمت معامله‌ی دوم داده شده‌اند. در خط دوم و آخر ورودی، $n$ عدد طبیعی که نشان‌دهنده‌ی لیست اولیه‌ی نمرات هندسه‌ی کاراکترهای کمکی هستند داده‌ شده‌اند. (بیشینه نمره‌ی قابل کسب در امتحان هندسه برای هر نفر $1 \ 000 \ 000 $ است.) $$1 \leq n \leq 100 \ 000$$ $$1 \leq x,y \leq 1 \ 000\ 000 \ 000$$ # خروجی در تنها خط خروجی کم‌ترین هزینه‌ی ممکن هیئت مذاکره کننده برای رسیدن به هدف را چاپ کنید. # مثال ## نمونه ورودی ۱ ``` 1 5 1 1 ``` ## نمونه خروجی ۱ ``` 1 ``` ## نمونه ورودی ۲ ``` 1 4 3 8 ``` ## نمونه خروجی ۲ ``` 0 ``` ## نمونه ورودی ۳ ``` 5 7 12 1 2 4 8 16 ``` ## نمونه خروجی ۳ ``` 7 ``` # توضیح در مثال اول ب.م.م (۱) = ۱ در نتیجه یا باید یکی به ۱ اضافه کنیم یا آن را از لیست نمرات حذف کنیم که افزایش نمره در این‌جا ارزان‌تر است. در مثال دوم لیست اولیه‌ی نمرات هندسه مطلوب است و هیئت‌مذاکره‌کننده بدون پرداخت هزینه‌ای هدف موردنظر را دارد و نیازی به معامله ندارد. در مثال سوم هرکاری روی هر یک از اعداد لیست نمرات بکنیم ولی روی ۱ تغییری ایجاد نکنیم همچنان ب.م.م اعداد ۱ خواهد بود. پس با افزایش یا حذف روی ۱ در یک معامله می‌توانیم ب.م.م نمرات را به ۲ تغییر بدهیم که در این‌جا حذف ارزان‌تر است از افزایش.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت *****  آخرین فرصت برای درس خواندن کاراکترهای کمکی شهریورماه است. ماهی که کاراکتر اصلی ۱ به مدیر مدرسه قول داده درپایان آن شمار دانش آموزان را به کمتر از نصف کاهش دهد. متاسفانه هندسه‌ی کاراکترهای کمکی بسیار ضعیف است درعوض سیستم‌های اطلاعاتی بسیار قدرتمندی دارند که از طریق آن‌ها به تصمیمات شوم کاراکتر اصلی ۱ پی برده‌اند. از این‌رو برنامه‌ریزی برای پایه‌ریزی انقلاب دانش‌آموزی در مدرسه را آغاز کرده‌اند. با زحمات شبانه‌روزی تمام کاراکترهای‌ کمکی، سرانجام کاراکتر‌های کمکی موفق به ترسیم نقشه‌ای از مدرسه شدند، کاراکتر کمکی ۱ با اولین نگاه به آن بدرستی متوجه شد که نقشه‌ی مدرسه‌شان یک درخت است که هر قسمت مدرسه در آن بصورت یک راس شماره‌دار نشان داده شده است و شماره‌ی هر راس متفاوت از بقیه‌ و عددی طبیعی از ۱ تا $n$ است (شامل خود ۱ و $n$). کاراکتر کمکی ۲ با توجه به حدس کاراکتر کمکی ۱ فکری کرد که به نظر می‌تواند آن‌ها را در رسیدن به هدفشان و این‌بار، گرفتن انتقام از خود کاراکتر اصلی ۱ یاری کند. ایده‌ی او این بود که تعدادی از کاراکترهای کمکی در تعدادی از برگ‌های نقشه قرار گیرند (ممکن است تعدادی از برگ‌ها باشند که هیچ‌یک از کاراکترهای کمکی در آن نباشند) سپس یکی از کاراکترهای کمکی با گفتن رمز "هندسه خر عست" عملیات قطعی برق را آغاز کند. پس از قطعی برق زمان فرار کاراکتر اصلی ۱ از مدرسه فرا می‌رسد. او که در مدرسه تنها و بدون کمک هیچ ‌کاراکتر اصلی دیگری گیر افتاده است در ابتدا در راس ۱ نقشه‌ی مدرسه است و بدلیل قطعی برق حتی نمی‌داند که در حین فرار در هر مرحله به کجا می‌رود. کاراکتر اصلی ۱ به آخر خط رسیده است و دانش آموزان امید دارند به محض رسیدن او به یکی از برگ‌هایی از نقشه‌ی مدرسه که یکی از کاراکترهای کمکی در آن حضور داشته باشد زندگی نامبارک او را به پایان رسانند. اگر بدانیم در صورت رسیدن کاراکتر اصلی ۱ به برگ‌هایی که کاراکتری کمکی در آن کمین کرده ‌است، حتما کاراکتر اصلی ۱ خواهد مرد و در صورت رسیدن به برگی که کسی در آن کمین نکرده است، می‌تواند از مدرسه فرار کند و حتما زنده خواهد ماند، بگویید احتمال زنده ماندن کاراکتر اصلی چقدر است؟ *قطعی برق کاراکتر اصلی ۱ را در هر مرحله ی جابجایی مجبور به انتخاب تصادفی یکی از رئوس مجاور راسِ هر مرحله می‌کند. *ترس شدید و عذاب وجدان، کاراکتر اصلی ۱ را مجبور کرده مدام در حال جابجایی در مدرسه باشد تا بمیرد یا به حالتی برسد که ترس از مرگ نداشته باشد. # ورودی در خط اول ورودی به ترتیب دو عدد طبیعی $n$ و $k$ داده می‌شوند. در خط دوم ورودی $k$ عدد طبیعی که نشان‌دهنده‌ی شماره‌ی رئوسی از درخت که کاراکترهای کمکی در آن کمین کرده‌اند، است، داده می‌شود. (تضمین می‌شود تمامی شماره راس‌های داده شده در این خط نشان‌دهنده‌ی برگ‌هایی از درخت هستند.) در $n - 1$ خط بعد در هر خط دو عدد طبیعی $u$ و $v$ داده می‌شوند که این دو راس $u$ و $v$ در درخت متصل هستند. $$2 \leq n \leq 100 \ 000$$ $$1 \leq k \leq n$$ $$1 \leq v,u \leq n$$ # خروجی در تنها خط خروجی احتمال زنده ماندن کاراکتر اصلی ۱ را با دقت دقیقا ۶ رقم اعشار چاپ کنید. (برای مثال بجای `0.5`، `0.500000`را و به‌جای `0.63710792`، `0.637108` را چاپ کنید.) # مثال ## نمونه ورودی ۱ ``` 3 1 2 1 2 1 3 ``` ## نمونه خروجی ۱ ``` 0.500000 ``` ## نمونه ورودی ۲ ``` 9 1 9 1 2 2 3 3 4 4 5 5 6 1 7 7 8 8 9 ``` ## نمونه خروجی ۲ ``` 0.375000 ``` # توضیح در متن صورت سوال آمده که کاراکتر اصلی ۱ ابتدائا در راس ۱ قرار دارد. از آن‌جایی که حتما باید حرکت بکند، پس یا به راس ۲ می‌رود یا به راس ۳. هر دوی این رئوس برگند. در راس ۲ زندگی کاراکتر اصلی ۱ پایان می‌پذیرد و در راس ۳ نجات پیدا می‌کند، پس به احتمال $\frac {1} {2} = 0.5 = 0.500000$ کاراکتر اصلی ۱ زنده می‌ماند.