+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در یک روز خوش و خرم زمستان ، سروش از جلوی نمازخانه ی مدرسه می گذشت که ناگهان درطی عطسه ی رضا در سواحل ملبورن (عافیت باشه)، طوفانی در حیاط مدرسه شکل گرفته و مقادیر زیادی از کفش های دم در نمازخانه را با خود برد. (به این فرایند اثر پروانه ای می گویند که با توجه به وقت کم آزمون به توضیح آن نمیپردازیم). سروش که متوجه عمق فاجعه شده بود ، به فکر فرو رفت که کفش های باقی مانده را به صورتی با هم جفت کند که در اولویت اول تعداد جفت ها بیشینه شود و سپس در اولویت دوم بیشینه اختلاف سایز دو کفش جفت شده، کمینه شود. طبیعتاً تنها میتوان کفش های پای راست را با کفش های پای چپ جفت کرد. از آنجایی که سروش کار و زندگی دارد، این امر را به شما واگذار کرده است. کمینه اختلاف سایز دو کفش جفت شده را با رعایت نکات گفته شده محاسبه کنید. # ورودی در خط اول ورودی دو عدد $n$ و سپس $m$ به شما داده میشود که به ترتیب تعداد کفش های پای راست و چپ هستند. در خط دوم $n$ عدد داده می‌شوند که سایز کفش های پای راست هستند. در خط سوم $m$ عدد داده میشوند که سایز کفش های پای چپ هستند. $$1\leq n,m \leq 10^5$$ سایز کفش ها اعدادی مثبت و طبیعی هستند که همه کمتر مساوی $10^9$ هستند. # خروجی در تنها خط خروجی کمینه اختلاف سایز دو کفش جفت شده را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 3 3 2 3 2 1 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 4 3 45 41 39 2 46 42 39 ``` ## خروجی نمونه ۲ ``` 1 ``` ## ورودی نمونه ۳ ``` 5 5 10 2 1 6 7 12 3 6 11 9 ``` ## خروجی نمونه ۳ ``` 4 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در رستوران پدر خوب $n$ نفر از بچه های دوره تابستون دور میز گردی نشسته اند و منتظر شام طلا اند. در این حین طلاها به علت سخاوت زیاد ، $n$ ظرف سیب زمینی سفارش داده اند و آنها را به ترتیب بر روی میز گرد چیده اند. به طوری که نفر $i$ام مجاور ظرفهای سیب زمینی $i$ و $i+1$ است. (چون افراد دور میز گرد هستند نفر $n$ ام با ظرفهای سیب زمینی $n$ و $1$ مجاور است) برای این که سیب زمینی کم نیاید ، هر نفر یکی از دو ظرف سیب زمینی مجاورش را انتخاب می کند و تنها از آن سیب زمینی می خورد. توجه کنید که ممکن است یک ظرف سیب زمینی توسط دو نفر انتخاب شود و یا اصلا انتخاب نشود. ظرف سیب زمینی $i$ام نیز $a_i$ عدد سیب زمینی دارد. دقت کنید که اگر دو نفر از یک سیب زمینی بخورند، هر کدام دقیقا نیمی از آن را می خورند. ممکن است این مقدار اعشاری شود. بعد از انتخاب ها یک نفر ناراحت خواهد بود اگر با تغییر انتخابش مقدار سیب زمینی بیشتری نسیبش شود با ثابت در نظر گرفتن انتخاب بقیه! به بچه های دوره کمک کنید جوری سیب زمینی خود را انتخاب کنند که پس از آن کسی ناراحت نشود. اگر چنین حالت ایده آلی وجود ندارد ، در تنها خط خروجی "Ey Baba" چاپ کنید. # ورودی در خط اول ورودی به شما یک عدد $n$ داده میشود. در خط بعدی $n$ عدد به شما داده میشود که عدد $i$ام نشان دهنده ی $a_i$ است. $$1\leq n \leq 10^6$$ $$1\leq a_i \leq 10^9$$ # خروجی اگر جوابی وجود نداشت "Ey Baba" چاپ کنید. در غیر این صورت $n$ عدد چاپ کنید که عدد $i$ام برابر با شماره ظرف سیب زمینی‌ای باشد که نفر $i$ام باید انتخاب کند. اگر چند جواب وجود دارد یکی از آنها را به دلخواه چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 5 3 7 2 9 ``` ## خروجی نمونه ۱ ``` 2 3 3 5 1 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اعداد $k$ و $n$ به شما داده شده اند. تعداد جایگشت های $p$ به طول $n$ را بشمارید که شرط زیر به ازای هر $1 \leq i \leq n$ برقرار باشد. $$|p_i-i| \neq k$$ باقی مانده تعداد این جایگشت ها را بر $924844033$ چاپ کنید. # ورودی در تنها خط ورودی دو عدد $n$ و $k$ به شما داده میشود. $$2 \leq k +1 \leq n \leq 2000 $$ # خروجی در تنها خط خروجی باقی مانده تعداد جایگشت های ممکن را به $924844033$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 4 1 ``` ## خروجی نمونه ۲ ``` 5 ``` ## ورودی نمونه ۳ ``` 425 48 ``` ## خروجی نمونه ۳ ``` 756765083 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به شما یک درخت $n$ راسی داده میشود (گراف همبند $n-1$ یالی). شما باید این درخت را به گونه ای جهت دار کنید که تعداد جفت های $(u,v)$ که از $u$ به $v$ مسیری جهت دار وجود دارد بیشینه یا کمینه شود. دقت کنید که باید یکبار تعداد این جفت ها را کمینه و یکبار آنها را بیشینه کنید. # ورودی در خط اول ورودی به شما یک عدد $n$ داده میشود. درهر یک از $n-1$ خط بعدی دو عدد $v$ و $u$ به شما داده میشوند که به معنای وجود یال بین دو راس $u$ و $v$ است. $$1\leq n \leq 250000$$ $$1\leq u,v \leq n$$ # خروجی در تنها خط خروجی دو عدد به ترتیب چاپ کنید که اولین عدد نشان‌دهنده ی کمینه تعداد جفت های گفته شده و دومین عدد بیشینه مقدار این جفت ها باشد. # مثال ## ورودی نمونه ۱ ``` 4 2 1 3 1 4 1 ``` ## خروجی نمونه ۱ ``` 3 5 ``` ## توضیحات نمونه ۱ نمونه ای از جهت دهی کمینه: ``` 1 2 1 3 1 4 ``` نمونه ای از جهت دهی بیشینه: ``` 2 1 1 3 1 4 ``` ## ورودی نمونه ۲ ``` 8 2 1 3 2 4 3 5 4 6 5 7 6 8 7 ``` ## خروجی نمونه ۲ ``` 7 28 ```