+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت -------------------- در جهان‌های موازی، جام جهانی هر سال برگزار می‌شود. تیم ملی کانادا در تلاش است تا در جام جهانی قهرمان شود اما باید تیم ملی فرانسه را شکست دهد. قدرت فعلی تیم کانادا برابر $a$ و قدرت تیم فرانسه برابر $b$ است. می‌دانیم کانادا در صورتی شانس قهرمانی دارد که قدرت آن حداقل نصف قدرت فرانسه باشد، یعنی: $$2 \times canada \ge france$$ امیرحسین علاقه زیادی به خواننده‌های ساکن کانادا دارد و همیشه از این تیم حمایت می‌کند. به لطف او قدرت تیم کانادا هر سال دقیقاً ۱ واحد افزایش پیدا می‌کند. بنابراین پس از گذشت دقیقاً $n$ سال، قدرت کانادا برابر $a+n$ خواهد بود. قدرت تیم فرانسه در طول زمان ثابت است. حال مشخص کنید آیا پس از دقیقاً $n$ سال، کانادا می‌تواند شانس قهرمانی داشته باشد یا خیر.  # ورودی در یک خط سه عدد صحیح $a$ و $b$ و $n$ داده می‌شود که به ترتیب نشان‌دهنده قدرت اولیه کانادا، قدرت فرانسه و تعداد سال‌ها هستند. $$1 \le a, b, n \le 100$$ # خروجی اگر پس از دقیقاً $n$ سال کانادا شانس قهرمانی داشته باشد، `Yes` و در غیر این صورت `No` چاپ کنید. پاسخ مسئله را می‌توانید هر شکلی از آن را چاپ کنید؛ برای مثال خروجی‌های زیر همگی قابل قبول هستند: `Yes`, `YES`, `yes`, `yEs`, `YeS`, `nO`, `NO`, `No` به طور کلی مقایسه به بزرگی و کوچکی حروف حساس نیست. # مثال ## ورودی نمونه ۱ ``` 2 9 2 ``` ## خروجی نمونه ۱ ``` No ``` در این حالت بعد از ۲ سال قدرت کانادا به ۴ می‌رسد که کمتر از نصف قدرت فرانسه است، بنابراین پاسخ `No` است. ## ورودی نمونه ۲ ``` 13 40 7 ``` ## خروجی نمونه ۲ ``` Yes ``` در این حالت پس از ۷ سال قدرت کانادا به ۲۰ می‌رسد که شرط قهرمانی برقرار می‌شود، بنابراین پاسخ `Yes` است.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کارلوس کِی‌روش در جام جهانی ۲۰۱۴ در تلاش برای پیدا کردن تاکتیکی برای بازی تیم ایران در مقابل آرژانتین بود. او یک تاکتیک را به صورت یک آرایه $n$ عضوی نشان می‌دهد که هر عضو آن عددی مثبت است و عضو $i$ ام این تاکتیک را به شکل $a_i$ نشان می‌دهیم. در یک تاکتیک، عضو $i$ ام آن را کلیدی می‌نامیم اگر به ازای هر $j$ کوچکتر از $i$ بدانیم عضو $i$ ام این تاکتیک از عضو $j$ ام آن بزرگتر است. به عبارتی عضو $i$ ام کلیدی است اگر و تنها اگر به ازای هر $j < i$ داشته باشیم $a_j < a_i$. حال میزان کارآمدی یک تاکتیک را تعداد اعضای کلیدی آن می‌نامیم. برای مثال کارآمدی تاکتیک $[2,5,1,10,10]$ برابر با $3$ است و عضو‌های اول، دوم و چهارم کلیدی اند. در آن زمان، یکی از دستیاران کارلوس کِی‌روش به او تاکتیک اولیه‌ای را پیشنهاد داد. اما کارلوس برای قوی‌تر کردن این تاکتیک، عملیات زیر را به تعداد دلخواه بر روی تاکتیک اولیه انجام داد: + او در هر عملیات می‌تواند دو عضو **مجاور** از آرایه تاکتیکش را انتخاب کند به طوری که **زوجیت این دو عضو برابر باشد** (یا هر دو زوج باشند، یا هر دو فرد باشند)، و سپس این دو عضو را با یکدیگر جابجا کند. به عنوان مثال در تاکتیک $[2,4,4,3]$ می‌توان اعضای اول و دوم آرایه که به ترتیب مقادیر 2 و 4 را دارند را جابجا کرد و به تاکتیک $[4,2,4,3]$ رسید. اما در تاکتیک $[2,3,5]$ نمی‌توان اعضای اول و دوم آرایه را جابجا کرد زیرا اعداد آنها 2 و 3 است که زوجیت برابر ندارند. یا به طور مثال در تاکتیک $[2,4,4,3]$ نمی‌توان اعضای اول و سوم را جابجا کرد زیرا با وجود برقرار بودن شرط برابری زوجیت، این دو عضو مجاور نیستند. او در نهایت بین تمام تاکتیک‌هایی که با عملیات بالا قابل رسیدن بودند، تاکتیکی با بیشترین میزان کارآمدی را به عنوان تاکتیک نهایی برای بازی انتخاب کرد. حال سال‌ها از آن ماجرا می‌گذرد و او میزان کارآمدی تاکتیک نهایی‌اش را فراموش کرده است و به دنبال این است که با داشتن تاکتیک اولیه، میزان کارآمدی تاکتیک نهایی‌اش را پیدا کند. به او کمک کنید تا این عدد را بیابید.  # ورودی ورودی شامل دو خط است که در خط اول عدد $n$، طول تاکتیک اولیه، و در خط بعدی $n$ عدد با فاصله می‌آیند که نشان‌دهنده یک آرایه $n$ عضوی (تاکتیک اولیه کارلوس کِی‌روش) است. $$ 1 \leq n \leq 3 \times 10^5 $$ $$ 0 \leq a_i \leq 10^9 $$ # خروجی خروجی برنامه یک خط است و در آن باید بیشترین میزان کارآمدی یک تاکتیک که کِی‌روش در آن زمان می‌توانست به آن برسد را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 2 1 4 4 ``` ## خروجی نمونه ۱ ``` 2 ``` نیازی به تغییر وجود ندارد و کارآمدی این تاکتیک $2$ است. ## ورودی نمونه ۲ ``` 5 6 2 9 7 10 ``` ## خروجی نمونه ۲ ``` 5 ``` می‌توان با جا‌به‌جا کردن $6$ و $2$ و سپس جابه‌جا کردن $7$ و $9$، به تاکتیک $[2,6,7,9,10]$ رسید که کارآمدی آن $5$ است. ## ورودی نمونه ۳ ``` 5 8 18 6 7 2 ``` ## خروجی نمونه ۳ ``` 3 ```

* محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت --- *همان‌طور که می‌دانید، یکی از حسرت‌های ایتالیایی‌ها در فوتبال، از دست دادن جام جهانی 1994 با پنالتی چیپ روبرتو باجو در فینال است. از طرفی محمدسام ادعا می‌کند که به ماشین زمان دست یافته است. به همین دلیل ایتالیایی‌ها به پیش او آمده‌اند تا با استفاده از ماشین زمان، به فینال جام جهانی 1994 برگردند و به روبرتو بگویند این پنالتی را چیپ نزند! اما محمدسام در ابتدا به آن‌ها یک معما داده تا آن‌ها را محک بزند!* معما به این صورت است: به شما جدولی با ابعاد $n \times m$ داده شده است. شما باید تعدادی دومینو در آن قرار دهید (دومینو شکلی است که از دو خانه‌ی مجاور کنار هم تشکیل شده است). یک چینش از دومینوها داخل جدول را **اتوبوسی** می‌نامیم اگر دو شرط زیر را داشته باشد: * در هر خانه‌ی جدول حداکثر یک دومینو قرار گرفته باشد. * هیچ دو دومینویی ضلع مشترک نداشته باشند. حال این معما از شما می‌خواهد یک چینش اتوبوسی از دومینوها در جدول $n \times m$ ارائه دهید به طوری که تعداد دومینوها حداقل $$ \frac{n \times m - \min(n,m)}{4} $$ باشد. ($\min(a,b)$ یعنی مقدار عدد کوچکتر بین $a$ و $b$؛ به طور مثال $\min(3,5)$ برابر 3 است) حال به ایتالیایی‌ها کمک کنید تا این معما را حل کنند!  # ورودی شما باید مسئله را برای $T$ تست‌کیس مختلف حل کنید. ابتدا در یک خط عدد $T$ داده می‌شود و در $T$ خط بعدی، در هر خط دو عدد $n$ و $m$ به ترتیب آمده‌اند. تضمین می‌شود جمع مقادیر $n \times m$ در همه تست‌ها حداکثر $10^6$ است. $$ 1 \leq T \leq 400 $$ $$ 1 \leq n, m \leq 1000 $$ # خروجی شما باید برای هر تست‌کیس یک جدول $n \times m$ از کاراکترهای `*` و `.` خروجی دهید، به طوری که خانه‌هایی که در یک دومینو قرار گرفته‌اند با `*` و خانه‌های خالی با `.` نمایش داده شوند. همچنین چینش شما باید یک چینش اتوبوسی و مطابق شرایط گفته‌شده باشد. اگر چندین پاسخ وجود دارد، یکی را به دلخواه چاپ کنید. همچنین دقت کنید که خروجی جدول باید دقیقاً مانند نمونه‌ها باشد و هیچ فاصله‌ی اضافی بین خانه‌های جدول وجود نداشته باشد. ‍ # مثال ## ورودی نمونه ۱ ``` 2 1 2 3 3 ``` ## خروجی نمونه ۱ ``` ** **. ..* ..* ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --- محمدسام بعد از تساوی غیرمنتظره اسپانیا در برابر کیپ‌ورد با عملکرد خیلی خوب وُزینیا (دروازه‌بان کیپ‌ورد) دیگر اشتیاقی برای نوشتن داستان جذاب برای سوال نداشت. به همین دلیل سعی کرد برای جلوگیری از اتلاف وقت، متن این سوال را به خلاصه‌ترین حالت ممکن بنویسد: به شما یک جایگشت به طول $n$ به نام $p$ ورودی داده شده و شما قرار است فرآیند گفته شده را بر روی این جایگشت انجام دهید: + ابتدا تعدادی از اعضای آن را حذف کنید (این تعداد می‌تواند 0 هم باشد) به طوری که حداقل یک عضو از این جایگشت باقی بماند. + سپس آرایه باقیمانده را $a$ بنامید. شما می‌توانید بر روی آرایه باقیمانده عملیات زیر را به تعداد دلخواه (این تعداد می‌تواند 0 هم باشد) انجام دهید: + + فرض کنید طول آرایه $k$ باشد. شما یک اندیس $i$ انتخاب می‌کنید به طوری که $1 < i$ و $i < k$ باشد و همچنین عضو $i$‌ام آرایه از هر دو عضو مجاورش اکیداً بزرگ‌تر باشد، سپس مقدار این عضو را برابر با $0$ قرار می‌دهید. حال در این سوال شما باید تعداد آرایه‌های مختلفی که با استفاده از فرآیند بالا بر روی جایگشت $p$ قابل به دست آمدن هستند را محاسبه کنید. از آنجا که این مقدار عدد بزرگی است، کافیست باقیمانده آن را بر $10^9+7$ خروجی دهید.  # ورودی ورودی به صورت $T$ تست‌کیس مختلف می‌آید که برای هرکدام باید مسئله را جداگانه حل کنید. در خط اول ابتدا عدد $T$ و سپس در $2 \cdot T$ خط بعد به ترتیب برای هر تست‌کیس عدد $n$ و سپس در خط بعد $n$ عدد متمایز می‌آید که نشان‌دهنده جایگشت $p$ است. $$ 1 \leq T \leq 100 $$ $$1 \leq n \leq 5000 $$ $$ 1 \leq p_i \leq n $$ تضمین می‌شود جمع مقادیر $n$ بر روی همه تست‌کیس‌ها حداکثر $5000$ است. تضمین می‌شود در هر تست‌کیس تمامی $p_i$ ها متمایز هستند. # خروجی در یک خط، باید تعداد $a$ های مختلفی که قابل به دست آمدن هستند را باقیمانده بر $10^9 + 7$ خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 2 2 1 3 1 3 2 5 1 4 3 2 5 ``` ## خروجی نمونه ۱ ``` 3 8 39 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در فینال جام جهانی 2022 هیجان به اوج خود رسیده است. تنها $n$ ثانیه از بازی باقی مانده، فرانسه از آرژانتین یک گل عقب است و امباپه تصمیم گرفته که دروازه تیم حریف را با شوت های پی در پی باز کند تا اختلاف گل دو تیم جبران شود. امباپه که دقیقا یک ثانیه قبل از شروع $n$ ثانیه پایانی شوتی بسیار بد و خارج از چارچوب دروازه زده، نزد امیرحسین، آنالیزور ارشد تیم فرانسه آمده تا در ادامه بازی به بهینه ترین شکل ممکن شوت هایش را بزند. در $i$مین ثانیه پس از شوت خجالت‌آور امباپه، انرژی او (که در ابتدا برابر 0 است) $a_i$ واحد افزایش می‌یابد، اما دقت کنید که ظرفیت ذخیره انرژی امباپه نامحدود نیست و اگر انرژی او به $m$ برسد ناگهان انرژی او تخلیه میشود و به صفر میرسد. به عبارتی اگر انرژی او در حال حاضر $e$ باشد و در ثانیه فعلی $a$ واحد به انرژی او اضافه شود، انرژی وی در نهایت برابر با $m$ $mod$ $(e + a)$ خواهد بود. این بازیکن محدودیت دیگری نیز دارد، از آنجا که دقایق زیادی از شروع بازی گذشته پاهای او دیگر توان زیادی ندارند و او نمی‌تواند دو شوت با فاصله زمانی کمتر از $k$ ثانیه بزند. امباپه می‌تواند در پایان هر ثانیه دلخواه یک شوت به سمت دروازه حریف بزند (در صورتی که شرط بالا نقض نشود). اگر زمان زدن شوت او $e$ واحد انرژی داشته باشد، این شوت $e$ واحد قدرت خواهد داشت و بعد از زدن شوت انرژی امباپه تخلیه و برابر با 0 میشود. **دقت کنید که دقیقا یک ثانیه قبل از شروع $n$ ثانیه پایانی امپابه یک شوت زده (و نمی‌تواند در $k-1$ ثانیه اول شوت دیگری بزند) و امیرحسین او را وادار میکند تا در ثانیه پایانی بازی هم یک شوت به سمت دروازه آرژانتین بزند. (بنابراین در ثانیه $n$ حتما یک شوت می‌زند)** از آنجا که امیرحسین شب گذشته را به خوبی نخوابیده از شما میخواهد تا به او و تیم فرانسه کمک کنید که بفهمند حداکثر جمع قدرت شوت های امباپه چقدر میتواند باشد.  # ورودی سطر اول ورودی، شامل سه عدد طبیعی $n$ , ثانیه های باقی مانده از بازی، $m$، ظرفیت انرژی امباپه، $k$، حداقل فاصله بین هر دو شوت است. $$1 \leq k \leq n \leq 3 * 10^5$$ $$1 \leq m \leq 10^9$$ در سطر بعدی، $n$ عدد می‌آید که عدد $i$م نشان دهنده ی $a_i$ است. $$1 \leq a_i \leq 10^9$$ # خروجی خروجی برنامه یک خط است و در آن باید بیشترین مقدار ممکن برای جمع قدرت شوت های امباپه را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 2 2 4 5 3 6 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 12 6 3 6 6 1 5 6 6 1 5 6 6 1 5 ``` ## خروجی نمونه ۲ ``` 6 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک ماه مانده به جام جهانی 2026، دقیقا وقتی همه تیم ها در حال آماده‌سازی خود برای تورنومنت بودند، امیرحسین که آدم پول دوست و خبیثی است به فکر راه انداختن تورنومنت خود افتاد تا هم تیم های ملی بازی های نسبتا دوستانه‌‎ای قبل از جام جهانی انجام دهند هم خودش پولی به جیب بزند. پس از ثبت نام اولیه، مشخص شد $n$ تیم با شماره های 0 تا $n-1$ در این تورنومنت شرکت خواهند کرد و امیرحسین با توجه به تیم ها برای $m$ روز متوالی برنامه‌ریزی کرد به طوری که در روز $i$م (با شروع از روز 0) یک مسابقه بین دو تیم $a_i$ و $b_i$ برگزار شود. از آنجا که امیرحسین حاضر است برای بیشتر پول درآوردن هرکاری انجام دهد، پس از کمی محاسبات به این نتیجه رسید که اگر تیم $a_i$ مسابقه روز $i$م را برنده شود میتواند پول بیشتری به جیب بزند. او که مسئول تورنومنت است تمام زد و بند های لازم را انجام میدهد تا برنده مسابقه روز $i$م تیم $a_i$ باشد. اما داستان به همینجا ختم نمیشود، امیرحسین $m$ مدال برای هر بازی تورنومنت تدارک دیده تا بازی ها جذاب تر شوند. در روز $i$م و پس از برگزاری مسابقه آن روز، ابتدا تمام مدال های تیم بازنده از آنها گرفته میشود و به تیم برنده داده میشود، سپس امیرحسین مدال $i$م که تا الان برای کسی نبوده و مخصوص این بازی در نظر گرفته شده را نیز به برنده مسابقه این روز می‌دهد. پس از اتمام $m$ بازی تورنومنت و در صبح روز $m$ام، امیرحسین تمامی $m$ مدال را جمع آوری میکند و سپس هر مدال $i$ را به تیمی می‌دهد که تعداد شب های بیشتری از بقیه تیم‌ها این مدال را در دست داشته (لزومی ندارد این شب ها متوالی باشند)، اگر چند تیم تعداد شب های مساوی مدال $i$ را در دست داشته باشند در نهایت مدال $i$ به تیم با شماره کوچکتر تعلق میگیرد.  # ورودی سطر اول ورودی، شامل دو عدد طبیعی $n$ , تعداد تیم های حاضر در تورنومنت و $m$، تعداد مسابقه های تورنومنت است. $$2 \leq n \leq 2 * 10^5$$ $$1 \leq m \leq 2 * 10^5$$ در سطر $i$م از $m$ سطر بعدی، دو عدد $a_i$ و $b_i$ می‌آید که تیم های حاضر در مسابقه این روز هستند. $$0 \leq a_i, b_i \leq n-1, a_i \ne b_i$$ # خروجی خروجی برنامه شامل $n$ عدد طبیعی است و عدد $i$م باید تعداد مدال هایی باشد که صاحب نهایی آنها تیم $i$م است. # مثال ## ورودی نمونه ۱ ``` 3 4 0 1 2 1 1 0 2 1 ``` ## خروجی نمونه ۱ ``` 1 1 2 ``` ## ورودی نمونه ۲ ``` 6 10 2 5 3 0 4 2 0 1 4 3 2 4 0 3 0 2 5 2 5 0 ``` ## خروجی نمونه ۲ ``` 5 0 1 1 1 2 ```