+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مرحله انتخابی پردیس کد به رومینا و علی سپرده شده است. آن‌ها قرار است یک مسابقه طناب کشی برگزار کنند و هر کدام از بین شرکت‌کنندگان یک تیم انتخاب کنند. تمام اعضای تیم برنده به مرحله نهایی راه پیدا می‌کنند. تیم‌کشی به این صورت است: ابتدا رومینا از بین شرکت‌کنندگان یک نفر را انتخاب می‌کند. سپس علی دو نفر از افراد باقی‌مانده را برمی‌گزیند. از این مرحله به بعد، نوبت انتخاب‌ها به‌صورت یکی در میان (شروع از رومینا) ادامه می‌یابد و هر بار هر نفر دو شرکت‌کننده را انتخاب می‌کند تا زمانی که دیگر فردی برای انتخاب باقی نماند. (در صورتی که در پایان، تعداد شرکت‌کنندگانِ باقی‌مانده کمتر از تعداد لازم برای انتخاب باشد، رومینا یا علی در نوبت آخر خود تنها یک نفر را انتخاب می‌کنند.) هدف رومینا و علی این است که قوی‌ترین تیم ممکن را تشکیل دهند؛ بنابراین هر دو با بهینه‌ترین و هوشمندانه‌ترین روش ممکن انتخاب‌های خود را انجام می‌دهند. بعد از تیم‌کشی. رومینا تصمیم می‌گیرد که به تعدادی از اعضای تیم مقابل رشوه ‌دهد که به نفع او کنار بکشند و در طناب‌کشی منفعل باشند. کمترین تعداد اعضایی که رومینا باید به آن‌ها رشوه بدهد تا مجموع وزن تیم او بیشتر از تیم علی شود، چند نفر است؟ و اگر برعکس، علی بخواهد این کار را انجام دهد، پاسخ چگونه خواهد بود؟ روش رشوه دهی برای پیروزی رومینا یا علی را اعلام کنید. **وزن تمام شرکت‌کننده‌ها با یکدیگر متفاوت است** # ورودی در خط اول عدد طبیعی $n$ داده می‌شود که نشان‌دهنده‌ی تعداد شرکت‌کنندگان است. در خط دوم، $n$ عدد طبیعی داده می‌شود که وزن شرکت‌کنندگان را نشان می‌دهد. در خط سوم، یکی از رشته‌های `"romina"` یا `"ali"` آمده است که مشخص می‌کند در این تضمین داده می‌شود وزن هیچ دو فردی یکسان نیست. $$2 \leq n , a_i \leq 10^5$$ # خروجی در خط اول، کمینه‌ی تعداد افرادی را که فرد مورد نظر باید به آن‌ها رشوه دهد چاپ کنید. در خط دوم، وزن این افراد را به ترتیب از **سنگین به سبک** بنویسید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 1 4 6 9 2 romina ```` ## خروجی نمونه ۱ ``` 0 ```` ## ورودی نمونه ۲ ``` 4 1 4 6 9 romina ```` ## خروجی نمونه ۲ ``` 1 6 ```` ## ورودی نمونه ۳ ``` 4 5 7 3 1 ali ```` ## خروجی نمونه ۳ ``` 1 1 ````

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به یک جدول با $n$ سطر و $m$ ستون متشکل از اعداد صحیح بین $0$ تا $9$ می‌گوییم استثنایی اگر و تنها اگر به ازای هر خانه از جدول که عدد $x$ در آن نوشته شده است،‌ دقیقا $x$ تا از خانه‌های مجاور ضلعی‌اش(به جز خودش) حاوی عدد $x$ باشند. اعداد $n$ و $m$ به شما داده شده است. اگر جدول استثنایی‌ای با $n$ سطر و $m$ ستون وجود دارد آن را گزارش کنید. # ورودی در خط اول ورودی عدد $t$، تعداد تست‌کیس‌ها آمده‌است. در هر یک از $t$ خط بعدی، دو عدد طبیعی $n$ و $m$ آمده‌اند. $$ 1 \leq t \leq 10^5 $$ $$ \sum n \cdot m \leq 10^6 $$ # خروجی برای هر تست‌کیس، در صورتی که حداقل یک جدول استثنایی وجود دارد عبارت `Yes` را چاپ کنید. سپس در $n$ خط بعدی، در هر خط یک رشته به طول $m$ متشکل از ارقام $0$ تا $9$ چاپ کنید. اگر جدول استثنایی وجود ندارد عبارت `No` را چاپ کنید. برای چاپ عبارت `Yes` و یا `No`، خروجی به حروف کوچک و بزرگ حساس نیست. # مثال ## ورودی نمونه ``` 3 1 1 2 2 4 4 ``` ## خروجی نمونه ``` Yes 0 Yes 22 22 Yes 0222 2212 2012 2222 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در کشور اسکاتلند تفاوت‌های چشمگیری در قیمت بنزین دیده می‌شود؛ مثلاً قیمت بنزین در شهر $\text{Dunfermline}$ حدود ۱۳۵.۷ پنس برای هر لیتر است، در حالی که در $\text{Glasgow}$ و $\text{Kilmarnock}$ حدود ۱۳۰.۹ پنس است. مردم اسکاتلند می‌خواهند بدانند برای سفر از هر شهر به شهری دیگر چند پنس باید هزینه کنند. کشور اسکاتلند $n$ شهر و $m$ جاده دارد و بین هر دو شهری حداکثر یک جاده وجود دارد. هر جاده را با سه عدد $v$ و $u$ و $w$ نشان می‌دهیم که نشان دهنده‌ی جاده‌ای بین دو شهر $v$ و $u$ است و عبور از این جاده از هر دو جهت $w$ لیتر بنزین نیاز دارد. همچنین می‌دانیم هر لیتر بنزین در شهر $i$ام $a_i$ پنس قیمت دارد. شما باید به ازای هر دو شهر $s$ و $t$ محاسبه کنید کمترین مقدار پولی که باید خرج کنیم تا از شهر $s$ به شهر $t$ برسیم چند پنس است. دقت کنید که در ابتدا که در شهر $s$ هستیم هیچ بنزینی نداریم و همچنین هر مقدار که بخواهیم می‌توانیم در هر شهر بنزین بزنیم و ظرفیتی روی بنزینی که حمل می‌کنیم نداریم. تنها محدودیت این است که هنگام استفاده از یک جاده باید بنزین مورد نیاز را داشته باشیم. # ورودی در خط اول ورودی دو عدد $n$ و $m$ تعداد شهر ها و تعداد جاده‌های اسکاتلند می‌آید. در خط دوم ورودی دنباله‌ی $a_1, a_2, \ldots, a_n \ $ می‌آید که $a_i$ نشان‌دهنده‎‌ی قیمت هر لیتر بنزین در شهر $i$ می‌باشد. در هر کدام از $m$ خط بعدی سه عدد $v$ و $u$ و $w$ می‌آیند که نشان دهنده‌ی جاده‌ای دوطرفه بین دو شهر $v$ و $u$ است و استفاده از این جاده نیاز به $w$ لیتر بنزین دارد. $$1 \le n \le 500$$ $$n-1 \le m \le \frac{n(n-1)}{2}$$ $$1 \le v \neq u \le n$$ $$1 \le w, a_i \le 10^6$$ تضمین می‌شود گراف ورودی همبند است و همچنین بین هر دو راس حداکثر یک جاده وجود دارد(جاده تکراری نداریم). # خروجی خروجی به صورت یک ماتریس $n \times n$ است که خانه‌ی $(i, j)$ آن نشان‌دهنده‌ی کمترین مقدار پول مورد نیاز برای رفتن از شهر $i$ به شهر $j$ می‌باشد. # مثال ## ورودی نمونه ۱ ``` 3 3 1 10 3 1 2 4 2 3 5 3 1 6 ``` ## خروجی نمونه ۱ ``` 0 4 6 40 0 46 18 15 0 ``` ## ورودی نمونه ۲ ``` 5 7 600783 171847 191295 353053 995582 1 2 479221 1 3 159037 1 4 917731 4 5 63986 5 1 809126 4 2 64758 4 3 880750 ``` ## خروجی نمونه ۲ ``` 0 217642290081 95546725971 228770758107 239766560249 82352691187 0 109682722526 11128468026 22124270168 30422982915 122095564110 0 133224032136 144219834278 105215697361 22863006174 132545728700 0 22590449258 168919007213 86566316026 196249038552 63703309852 0 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امین بعد از یک روز طولانی، تصمیم گرفته که از سرزمین پردیس کد فرار کند و به استراحت بپردازد. ولی رومینا متوجه شده و می‌خواهد مانع فرار او شود. اما امین پیشنهاد می‌دهد که یک مسأله حل کند و بگذارند که برود. در ابتدا یک جایشگت روی تخته نوشته شده است. رومینا در هر مرحله یک دنباله جدید روی تخته می‌نویسد و دنباله قبلی را پاک می‌کند. دنباله جدید را به این صورت مینویسد که زیر هر دو عدد متوالی: + اگر تعداد اعضا دنباله‌ی فعلی روی تخته فرد باشد، عدد بزرگتر را انتخاب می‌کند و پایین آنها در دنباله جدید می‌نویسد. + اگر تعداد اعضا دنباله‌ی فعلی روی تخته زوج باشد، عدد کوچکتر را انتخاب می‌کند و پایین آنها در دنباله جدید می‌نویسد. به همین ترتیب بعد از عملیات‌های رومینا در هر مرحله یک دنباله جدید با یک عضو کمتر روی تخته نوشته شده و سپس دنباله قبلی پاک می‌شود. این مراحل انقدر تکرار می‌شوند تا یک عدد روی تخته باقی بماند. حالا برای رومینا سوال شده است که اگر به ازای همه ی دنباله‌های مختلفی که از پاک کردن قسمتی از سمت راست و قسمتی از سمت چپ دنباله اولیه بدست می‌آیند، بازی را شروع کند و عدد باقی مانده را در دفترش بنویسد. مجموع تمام اعداد نوشته شده در دفترش چند می‌شود؟ به امین کمک کنید مسأله را حل کند تا بتواند استراحت کند. البته چون مجموع ممکن است زیاد باشد، باقی مانده آن را به $ 10^9 + 7$ چاپ کنید. # ورودی خط اوّل شامل یک عدد صحیح $n$ است که نشان‌دهنده تعداد اعضای جایگشت اولییه است. $$ 1 \leq n \leq 2 \times 10^5 $$ سپس در خط بعدی $n$ عدد که به ترتیب از چپ به راست ترتیب اعضای جایگشت هستند ورودی داده می‌شود. $$ 1 \le a_i \le n $$ تضمین می‌شود که دنباله ابتدایی جایگشت است و عدد تکراری ندارد. # خروجی باقی مانده مجموع تمام جواب‌ها به ازای تمام زیر رشته‌های جایگشت اولیه را به $10^9+7$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 1 2 3 4 5 ```` ## خروجی نمونه ۱ ``` 42 ```` ## ورودی نمونه ۲ ``` 4 1 3 2 4 ```` ## خروجی نمونه ۲ ``` 23 ````

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ثنا پس از ماجراجویی‌های ویتنام در جنگل‌های ویتنام گم شده است و GPS او از کار افتاده است. نقشه‌ی ویتنام به صورت یک درخت وزن‌دار با $n$ رأس مدل می‌شود؛ هر یال وزن مثبتی دارد و فاصله‌ی بین دو رأس برابر است با مجموع وزن یال‌های مسیر یکتا بین آن دو رأس. ثنا می‌داند که در یکی از رئوس این درخت قرار دارد. او با استفاده از دانش خود در زمینه‌ی سیگنال‌ها دستگاهی ساخته که می‌تواند به برج‌های مخابراتی راس‌های مختلف وصل شود. هر بار که سیگنالی دریافت می‌کند، با توجه به زمان رفت‌وبرگشت سیگنال نتیجه می‌گیرد که فاصله‌ی راسی که در آن قرار دارد تا یک رأس مشخص، از مقداری معین بیشتر نیست. حالا ثنا می‌خواهد برنامه‌ای بنویسد تا با تحلیل این داده‌ها مکان خود را شناسایی کند. باید $q$ کوئری را پردازش کنید. در هر کوئری یا سیگنال جدیدی دریافت می‌شود. یا صدرا (برادر کوچک ثنا که طاقتش طاق شده)‌ از او می‌پرسد که آیا با توجه به اطلاعاتی که تا به حال دریافت کرده ممکن است در راس $v$ باشیم یا خیر. دو نوع کوئری داریم: + 1 v x : از این لحظه به بعد می‌دانیم فاصله تا راس $v$ حداکثر $x$ است. + 2 v : باید به این پرسش پاسخ دهید که آیا ممکن است در راس $v$ باشیم یا نه. ممکن است هیچ یک از رئوس در اطلاعات دریافت شده صدق نکند. به نمونه‌ی اول توجه کنید. # ورودی در خط اول ورودی تعداد تست‌کیس‌ها $T$ می‌آید. در خط اول هر تست‌کیس عدد $n$، تعداد رئوس درخت می‌آید. در $n - 1$ خب بعدی توصیف یال‌های درخت می‌آید. در هر خط به ترتیب سه عدد $v_i u_i w_i$ که به معنی وجود یک یال به وزن $w_i$ بین رئوس $v_i$ و $u_i$ است. در خط بعدی عدد $q$، تعداد کوئری‌ها می‌آید. در هر یک از $q$ خط بعدی یک کوئری به یکی از دو فرمت زیر می‌آید: + 1 v x + 2 v # خروجی به ازای هر کوئری از نوع دوم، در یک خط چاپ کنید `Yes` اگر ممکن است ثنا در آن راس باشد، و `No` اگر ممکن نیست. # محدودیت‌ها $$ 1 \leq T \leq 10^5 $$$$ 1 \leq n \leq 2 \cdot 10^5 $$$$ 1 \leq w_i \leq 1000 $$ $$ 1 \leq q \leq 4 \cdot 10^5 $$$$ 1 \leq v \leq n $$$$ 1 \leq x \leq 10^9 $$ + تضمین می‌شود دنباله‌ی ورودی یک درخت را توصیف می‌کند. $$ \sum n \leq 2 \cdot 10^5 $$ $$ \sum q \leq 4 \cdot 10^5 $$ # مثال ``` 2 3 1 2 2 1 3 2 6 1 1 2 2 2 1 1 1 2 2 1 2 0 2 1 6 1 2 262 1 3 396 2 6 724 3 4 693 4 5 845 9 1 5 2501 2 6 2 5 1 3 1273 2 5 1 1 372 1 6 871 2 3 2 2 ``` ``` Yes No No No Yes No No Yes ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- تعدادی روانی در یک ردیف داریم. هر روانی یک قدرت دارد و یک هزینه که هر دو را با یک عدد طبیعی نشان می‌دهیم. قدرت هر دو روانی‌ متفاوت است. در یک عملیات می‌توانیم به یک روانی دستور بدهیم یکی از مجاوران‌ش را به دلخواه خودمان به قتل برساند، به این شرط که قدرت قاتل بیشتر از مقتول باشد. برای انجام این دستور باید به اندازه هزینه‌ی روانی قاتل، پول پرداخت کنیم. در این سوال قدرت و هزینه‌ی $n$ روانی داده شده است و شما باید به ازای هر بازه از آنها، کمترین مقدار پول ممکن را محاسبه کنید تا تنها یک روانی باقی بماند، و در انتها جمع‌ این مقادیر به ازای تمام بازه‌‌ها را به پیمانه‌ی $998244353$ خروجی دهید. **تضمین داده میشود که قدرت روانی‌ها یک جایگشت تصادفی از 1 تا $n$ است.** # ورودی در خط اول، عدد $n$ می‌آید که نشان‌دهنده‌ی تعداد روانی‌ها می‌باشد. در خط دوم، آرایه‌ی $a_1, a_2, \ldots, a_n \ $ می‌آید که نشان‌دهنده‌ی قدرت روانی‌ها می‌باشد. در خط سوم، آرایه‌ی $b_1, b_2, \ldots, b_n \ $ می‌آید که نشان‌دهنده‌ی هزینه‌ی روانی‌ها می‌باشد. # محدودیت‌ها $$ 1 \le n \le 10^6 $$ $$ 0 \le b_i \le 10^6 $$ $$ 1 \le a_i \le n $$ تضمین داده می‌شود که آرایه‌ی $a_1, a_2, \ldots, a_n \ $ یک جایگشت تصادفی از اعداد $1$ تا $n$ است. سوال شامل 36 تست است. یک تست سمپل است. در 2 تست $n=100$ برقرار است. در 2 تست $n=10^5$ برقرار است و در $32$ تست $n=10^6$ برقرار است. # خروجی به ازای هر بازه کمترین پولی که می‌توان پرداخت کرد تا تنها یک روانی باقی بماند را محاسبه کنید و جمع این مقادیر را به پیمانه‌ی $998244353$ خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 10 5 9 3 4 1 7 6 8 10 2 54 92 52 56 26 75 64 12 23 94 ``` ## خروجی نمونه ۱ ``` 5905 ```

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- $n$ تا از بچه‌های پارک پردیس هر کدام تعدادی کارت خریدند که هر کارت عکس یکی از بازیکنان فوتبال را دارد. آنها در مجموع $m$ کارت خریدند. آنها با توجه به قدرت و کمیاب بودن کارت ها آنها را ارزش دهی کردند به صورتی که هر کارت ارزشی بین 1 تا $m$ دارد و هیچ دو کارتی ارزش یکسان ندارند. عدد بیشتر نشان دهنده ارزش بیشتر کارت است. بچه‌ها میتوانند یک دیگر را به چالش بکشند. به چالش کشیدن به این صورت است که ابتدا عدد $k$ به صورتی مشخص می‌شود که طرفین حداقل $k$ کارت داشته باشند. فرض کنید $a$م شخص $b$م را به چالش بکشد. سپس هر کس $k$ کارت پرارزش خود را به ترتیب ارزش روی میز میگذارد. سپس یک فرد بی طرف کارت ها به صورت زیر روی هم میگذارد. ابتدا پر ارزش‌کارت نفر $a$م قرار میگیرد و سپس پرارزش ترین کارت نفر $b$م روی کارت قبلی قرار میگیرد. و روی آن دومین کارت پر ارزش نفر $a$ و سپس دومین کارت پر ارزش نفر $b$ تا وقتی تمام $2k$ کارت روی میز قرار بگیرند و دسته کارت ما را تشکیل دهند. سپس به صورت نوبتی با شروع از نفر $a$ هر کس به ترتیب ضربه‌ای به دسته کارت‌ها میزند. هر ضربه باعث میشود تعدادی از کارت های روی دسته کارت برعکش شوند و روی میز بیافتند. آنگاه آن فرد تمام کارتهای برعکس شده را برای خودش برمی‌دارد. این کار تا وقتی که حداقل یک کارت روی میز باشد ادامه پیدا میکند. حال به شما لیست کارتهای اولیه بچه‌ها داده میشود. سپس چالش ها و نتایج آنها داده می‌شود و شما باید در نهایت لیست کارت‌هایی که هر کس در اختیار دارد را خروجی دهید. # ورودی در اولین خط دو عدد $n$ و $m$ داده می‌شود که به ترتیب تعداد بچه‌ها و تعداد کارت ها است. سپس در $n$ خط بعدی در خط $i$م ابتدا عدد $s_i$ یا همان تعداد کارت های نفر $i$م و سپس $s_i$ عدد $a_{i, 1}, a_{i,2}, \dots, a_{i, k}$ داده می‌شود که ارزش کارت‌های نفر $i$م است. تضمین میشود که کارت با ارزش $i$ دقیقا دست یک نفر است. سپس عدد $q$ داده می‌شود که تعداد چالش ها است. در $2q$ خط بعدی به ازای هر چالش دو خط ورودی داده می‌شود که خط اول شامل $a$ و $b$ و $k$ و $r$ است که بیانگر این است که فرد $a$م فرد $b$م را به چالش کشیده و آن دو $k$ کارت خود را روی میز گذاشته‌اند و $r$ نوبت به کارت ها ضربه زدند. تضمین میشود که هر دو نفر حداقل $k$ کارت دارند. سپس در خط بعدی $r$ عدد $c_i$ داده میشود که نشان دهنده تعداد کارت‌های برعکس شده بعد از ضربه $i$م است. تضمین می‌شود که جمع این اعداد دقیقا برابر $2k$ است. # خروجی شما باید $n$ خط خروجی دهید که در خط $i$م ابتدا تعداد کارت های نفر $i$م و سپس ارزش کارت های او به صورت **صعودی** باشد. # محدودیت‌ها $$1 \leq q, n, m \leq 3 \times 10^5$$$$ \sum s_i = m$$$$1 \leq k_i, c_i$$$$1 \leq \sum r_i \leq 3 \times 10^5$$ $$1 \leq a, b \leq n$$ $$a \neq b$$ ## ورودی نمونه ``` 3 10 4 7 1 8 3 3 10 2 9 3 4 5 6 2 2 3 3 3 3 1 2 1 2 3 2 5 1 ``` ## خروجی نمونه ``` 6 1 3 5 6 7 10 3 2 4 8 1 9 ```