+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عرفان و دوستانش که مجموعاً $3n$ نفر می‌شوند به سینما رفتند و روی $3n$ صندلی متوالی در یک رديف نشستند. آن‌ها با خود $n + 1$ بسته پاپ كورن به سینما بردند. قرار شد $n + 1$ پاپ کورن بین افراد تقسم شود به نحوی که به هر نفر حداکثر یک بسته پاپ کورن برسد. در صورتی یک نفر از فیلم لذت می‌برد که یا خود یا یکی از ۲ نفر بغل دستی‌اش (۲ نفر کناری هر کدام ۱ بغل دستی دارند) پاپ کورن داشته باشد. حال برای عرفان سوال شده است که به چند طريق می‌توان پاپ کورن‌ها را بین افراد تقسیم کرد که همه از فیلم لذت ببرند. # ورودی در سطر اول عدد $T$ آمده است که تعداد تست کیس‌ها است. در هر یک $T$ خط بعد یک عدد آمده است که نشان دهنده‌ی $n$ است. $$1 \leq T \leq 100 \, 000$$ $$1 \leq n \leq 10^9$$ # خروجی بـه ازای هـر تسـت تعداد حالات افراز $n + 1$ پـاپ کورن بین $3n$ نفر به طوری که همه از فیلم لذت ببرند را به پیمانه‌ی $10^9 + 7$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 1 2 ``` ## خروجی نمونه ۱ ``` 3 10 ``` حالات مطلوب برای $n = 1$ (عدد $1$ پاپ کورن دارد $0$ ندارد) : $$101 \mid 110 \mid 011$$ حالات مطلوب برای $n = 2$ (عدد $1$ پاپ کورن دارد $0$ ندارد) : $$110010 \mid 101010 \mid 011010 \mid 100110 \mid 010110$$ $$101001 \mid 011001 \mid 100101 \mid 010101 \mid 010011$$

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مسابقه‌ی فوتبال بین دو تیم پائوزو و کوریه در حال شروع شدن است و بحث سر این که کدام تیم برنده خواهد شد به بالاترین حد خود رسیده است. طبق تجارب پیشین می‌دانیم همیشه تیمی برنده شده است که خفن‌ترین گروه هواداران را داشته باشد. این مسابقه تعدادی تماشاچی دارد که در یک ردیف کنار هم نشسته‌اند و هرکس یا طرفدار پائوزو است یا کوریه که اولی را با `0` و دومی را با `1` نمایش می‌دهیم. گروه هواداران به هر کلونی (حداقل ١ نفر) از تماشاچی‌ها گفته می‌شود که کنار هم نشسته اند و همه طرفدار یک تیم مشترک اند (همه `0` یا همه `1` هستند). خفن‌ترین گروه هواداران برای هر تیم، بزرگ‌ترین آن گروه‌ها در نظر گرفته می‌شود. حال ما که هوادار دوآتشه‌ی پائوزو هستیم می‌خواهیم تعداد اعضای خفن‌ترین گروه هواداران پائوزو را در سوپرگروه تلگرامی «کل کل دربی» اعلام کنیم تا در ادامه به رجزخوانی بپردازیم. # ورودی در تنها خط ورودی یک رشته متشکل از حروف `0` و `1` آمده است که آرایش نشستن تماشاچیان را نشان می‌دهد. طول رشته‌ی ورودی حداکثر $10^4$ است. # خروجی در تنها خط خروجی، تعداد اعضای خفن‌ترین گروه هواداران پائوزو را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 0010101011100 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 101010101 ``` ## خروجی نمونه ۲ ``` 1 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مانی به تازگی استخدام شده که خانه‌ای بسازد! اولین مشکل مانی برای شروع، صافی زمین زیر خانه بود. به طور دقیق‌تر زمین زیر خانه به شکل جدولی از راست نامتناهی بود که ارتفاع ستون $i$ام آن (از سمت چپ) $h_i$ است. مانند مثال زیر: (نقطه‌ها در جدول نشان‌گر ادامه‌دار و نامتناهی بودن جدول از سمت راست است،‌ برای مثال $h_3=5$ و $h_7=0$ است)  برای صاف‌کاری سطح، مانی می‌تواند از ترکیب این دو عملیات استفاده کند: + یک خانه خاک به یک ستون اضافه کند و $a$تا هزینه دهد. + با بولدوزر از **بالای چپ‌ترین ستون زمین** شروع کرده و به سمت راست برود. اگر ارتفاع ستون بعدی از ستونی که در آن است بیشتر بود، خاک‌های آن ستون را به ستون بعدی هل بدهد و اگر ارتفاع ستون بعدی کمتر از ستون کنونی بود، متوقف شود. همچنین هزینه‌ی کل این عملیات $b$ واحد است. (برای توضیحات بیشتر به مثال نمونه ۱ توجه کنید.) **توجه کنید هدف هم‌ارتفاع کردن ستون‌هایی است که حداقل یک واحد خاک دارند. به عبارت دیگر در آخر ارتفاع همه‌ی ستون‌هایی که حداقل یک واحد خاک دارند باید برابر باشد.** حال به مانی کمک کنید که با کمترین هزینه زمین را صاف کند. # ورودی در خط اول ورودی به ترتیب $n$، $a$ و $b$ داده می‌شود. $$1 \le n \le 2000$$ $$1 \le a, b \le 10^9$$ در خط دوم ورودی $n$ عدد آمده که $i$امین آن‌ها برابر با ارتفاع ستون $i$ام یا همان $h_i$ است. $$1 \le h_i \le 2000$$ **توجه کنید برای $i > n$ مقدار $h_i$ برابر با صفر است.** # خروجی در تنها خط خروجی، کمینه‌ی هزینه را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 7 9 2 4 3 1 ``` ## خروجی نمونه ۱ ``` 9 ``` می‌توان با یک‌بار انجام عملیات ۲ به جواب رسید. در این مثال $n=4$ است. توجه کنید خاک‌ها می‌توانند به خانه‌های بعد از $n$ ستون اول نیز برسند     ## ورودی نمونه ۲ ``` 4 1 3 1 2 3 2 ``` ## خروجی نمونه ۲ ``` 3 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مش‌رجب برای تولد ۶ سالگی خود یک نوار به طول $n$ هدیه گرفته است که در هر کدام از خانه‌های آن یک عدد مثبت نوشته شده است.  در ابتدا تمامی خانه‌های این نوار آبی هستند. از آنجایی که مش‌رجب رنگ آبی را دوست ندارد، می‌خواهیم خانه‌های این نوار را برای او قرمز کنیم. می‌دانیم از نظر مش‌رجب میزان زیبایی یک بازه از نوار برابر با مجموع اعداد خانه‌های قرمز منهای اعداد خانه‌های آبی آن بازه است. همینطور میزان علاقه مش‌رجب به نوار برابر با بیشینه میزان زیبایی در میان تمام بازه‌های آن است. می‌خواهیم یک به یک خانه‌های آبی را قرمز کنیم تا در نهایت تمام خانه‌ها قرمز شوند. از آنجا که مش‌رجب هنوز به مدرسه نرفته است و محاسبه حاصل جمع و تفریق کمی برایش سخت است، از شما می‌خواهیم که بگویید پس از قرمز شدن هر خانه، میزان علاقه مش‌رجب به نوار در آن لحظه چقدر است. # ورودی در خط اول ورودی عدد $n$ آمده است. در خط دوم $n$ عدد آمده است که عدد $i$-ام آن‌‌‌‌ $a_i$ یا همان عدد خانه $i$-ام ست. در خط سوم $n$ عدد آمده است که ترتیب قرمز شدن خانه‌ها را نمایش می‌دهد، اعداد این خط یک جایگشت از اعداد ۱ تا $n$ هستند. $$1 \le n \le 10^5$$ $$1 \le a_i \le 10^9$$ # خروجی در تنها خط خروجی باید $n$ عدد چاپ کنید که عدد $i$-ام نشان می‌دهد میزان علاقه مش‌رجب به نوار بعد از مرحله $i$-ام چقدر است. # مثال ## ورودی نمونه ۱ ``` 5 44 58 32 16 94 1 2 5 3 4 ``` ## خروجی نمونه ۱ ``` 44 102 148 212 244 ``` ## ورودی نمونه ۲ ``` 5 115 80 26 35 78 1 2 3 4 5 ``` ## خروجی نمونه ۲ ``` 115 195 221 256 334 ```

+ محدودیت زمان: ۲ ثانیه (برای تمامی زبان‌های برنامه‌نویسی) + محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی) ---------- _گراف دوبخشی کامل_ نوع خاصی گراف دوبخشی است. اگر دو بخش رأس‌های این گراف را با $A$ و $B$ نمایش دهیم، چنین گراف دوبخشی کاملی با $K_{|A|, |B|}$ نمایش داده می‌شود و شرایط زیر را برآورده می‌کند: + به ازای هر $a \in A$ و $b \in B$، یک یال بین رأس‌های $a$ و $b$ وجود دارد. + به ازای هر $u, v \in A$، هیچ یالی بین این رأس‌ها وجود ندارد. + به ازای هر $u, v \in B$، هیچ یالی بین این رأس‌ها نیز وجود ندارد. یک گراف ساده با $N$ رأس (شماره‌گذاری شده از $1$ تا $N$) و $M$ یال به شما داده می‌شود. (توجه کنید که این گراف لزوماً دوبخشی نیست.) تعیین کنید که آیا این گراف حاوی گراف دوبخشی کامل $K_{2, 3}$ به عنوان زیرگراف هست یا نه. به عبارت دیگر آیا امکان دارد که با حذف برخی (شاید صفر) رأس و برخی (شاید صفر) یال، $K_{2, 3}$ را به دست آوریم یا خیر.  $$K_{2, 3}$$ # ورودی + در اولین خط دو عدد جدا از هم $N$ و $M$ قرار دارد (در ابتدا $N$ می‌آید و سپس $M$). + در هر کدام از $M$ خط بعدی دو عدد جدا از هم $u$ و $v$ وجود دارد که نشان می‌دهد بین رأس‌های $u$ و $v$ یک یال ساده وجود دارد. # خروجی یک خط حاوی رشته‌ی `YES` چاپ کنید اگر گراف حاوی حداقل یک $K_{2, 3}$ باشد و یا `NO` در صورتی که نباشد (تمامی حروف انگلیسی بزرگ هستند). # محدودیت‌ها - $1 \leq N \leq 2000$ - $0 \leq M \leq \frac{N(N - 1)}{2}$ - $1 \leq u, v \leq N$ - گراف ورودی ساده است و هیچ طوقه و یال چندگانه‌ای ندارد. # مثال ## ورودی نمونه ۱ ``` 5 5 1 5 1 3 1 4 2 3 2 4 ``` ## خروجی نمونه ۱ ``` NO ``` ## ورودی نمونه 2 ``` 5 6 1 5 1 3 1 4 2 3 2 4 2 5 ``` ## خروجی نمونه 2 ``` YES ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- آی مجری که به فکر بچه‌ها است، تصمیم گرفته برای اولین بار آن‌ها را به سینما ببرد. آی مجری می‌داند که اگر یکی از بچه‌ها هنگام دیدن فیلم ناراحت باشد، فیلم را به کام همه تلخ خواهد‌کرد. به همین دلیل می‌خواهد همه راحت باشند. و اگر چنین چیزی امکان نداشت اصلا به سینما نروند. یکی از بچه‌‌ها ناراحت است اگر فردی جلوی او(نزدیک تر به پرده‌ی سینما و هم‌ستون با او) نشسته باشد و قدش از او بلندتر باشد. همچنین به دلیل این که آن‌ها خیلی خوش‌قلب هستند اگر بیننده‌ی دیگری غیر از آن‌ها هم نتواند فیلم را به خوبی ببیند(فرد بلندتری جلویش نشسته باشد)، ناراحت می‌شوند. همه‌ی انسان‌ها در سه دسته‌ی قدی دسته‌بندی می‌شوند: ۱) انسان‌های کوتاه(تا ۱۹۰ سانتی‌متر) ۲) انسان‌های معمولی(۱۹۱-۱۹۸سانتی‌متر) ۳) انسان‌های بلند(۱۹۹ به بالا) در واقع افرادی نمی‌توانند درست ببینند که یک نفر از دسته‌ی بلند‌تر جلوی آن‌ها نشسته باشد. صندلی‌های سینما $r$ ردیف و $c$ ستون دارند که در ردیف آخر نزدیک ترین آدم‌ها به پرده‌ی سینما نشسته‌اند. قبل از رسیدن بچه‌ها تعدادی بیننده به سالن سینما رفته اند و در جاهای دلخواه خود نشسته‌اند و نمی‌توان جای آن‌ها را تغییر داد. شما باید یک ترتیب دلخواه از نشستن همه‌ی بچه‌ها در سینما خروجی دهید که همگی راحت باشند و یا این که بگویید بهتر است اصلا به سینما نروند و به جای آن به پارک بروند. # ورودی در سطر اول ورودی دو عدد طبیعی $r$ و $c$ آمده‌است، که به ترتیب نمایانگر تعداد ردیف‌ها و ستون‌های سینماست. سپس در $r$ سطر بعدی در هر کدام $c$ کاراکتر آمده‌است که به این نحو معنی می‌شوند: ۱) جای خالی: # ۲) انسان کوتاه: s ۳)انسان معمولی: n ۴)انسان بلند: t در سطر بعدی سه عدد طبیعی و کوچکتر از یک میلیون می‌آید که به ترتیب نشان‌دهنده‌ی تعداد بچه‌های کوتاه، معمولی و بلند است که آی مجری می‌خواهد با خود به سینما بیاورد. $$1 \le r, c \le 1000$$ # خروجی اگر حالتی وجود نداشت، "Let's go to the park" را چاپ کنید. در غیر این صورت باید یک جدول مانند ورودی چاپ کنید که همه‌ی بچه‌ها نیز در جاهای خالی آن نشسته‌اند. اگر چند حالت وجود داشت،‌ به دلخواه یکی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 4 t##n #ts# nn#t #s## st#n 7 3 2 ``` ## خروجی نمونه ۱ ``` Let's go to the park ``` ## ورودی نمونه ۲ ``` 5 4 #### n#n# ###n #n## ssss 3 3 3 ``` ## خروجی نمونه ۲ ``` ttn# ntn# snnn sns# ssss ```

+ محدودیت زمان: ۳.۵ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- مارچلو که سال سختی را سپری کرده، بسیار خسته است. پس تصمیم گرفته که در این تابستان قوای از دست رفتهٔ خود را بازیابی کند و چه کاری بهتر از یک مسافرت خوب و مقداری جهانگردی! زمینی که مارچلو در آن زندگی می‌کند تخت است! به طور دقیق‌تر جدولی $n \times m$ می‌باشد که هر خانه‌ی آن یا منطقه‌ی آزاد است و یا توسط کشوری اداره می‌شود. (توجه کنید لزومی ندارد مناطق تحت کنترل یک کشور مجاور یکدیگر باشند) او در هر مرحله می‌تواند به یکی از خانه‌های مجاور ضلعی خانه‌ی فعلی سفر کند. همچنین سفر در مناطق آزاد برای همگان مجاز است اما برای سفر در مناطق یک کشور نیاز به پاسپورت آن کشور داریم. هر کشور نیز تعدادی سفارت در مناطق آزاد دارد که می‌توان پاسپورت آن کشور را از آن‌ها اخذ کرد. با دریافت پاسپورت جدید پاسپورت قدیمی از بین خواهد رفت. **گرفتن پاسپورت یک کشور هیچ هزینه‌ای ندارد اما برای وارد شدن از منطقه‌ی آزاد به منطقه‌ی آن کشور باید یک واحد هزینه‌ی عوارض ورود بپردازیم.** حال مارچلو می‌خواهد از خانه‌ی خود در جدول شروع کند و مسافرتش را در خانه‌ی مقصدی که از قبل معلوم کرده به پایان برساند. به او کمک کنید با کمترین هزینه سفرش را انجام دهد. (یا بگویید که نمی‌تواند به مقصد برسد) **تضمین می‌شود خانه‌ی مارچلو در منطقه‌ی آزاد است و در ابتدا پاسپورت هیچ کشوری را ندارد.** # ورودی در خط اول به ترتیب اعداد $n, m, k$ آمده است که نشان دهنده‌ی طول جدول، عرض جدول و تعداد سفارت‌ها است. در خط دوم اعداد $ s_x, s_y, e_x, e_y $ آمده که مختصات خانه‌ی شروع و پایان مارچلو است. $$1 \le n, m \le 500$$ $$1 \le k \le 10^6$$ $$1 \le s_x, e_x \le n$$ $$1 \le s_y, e_y \le m$$ **تصمین می‌شود خانه‌ی ابتدایی و انتهایی یکی نیستند و تمام سفارت‌ها در مناطق آزاد هستند.** در هر یک از $n$ خط بعدی $m$ عدد آمده که عدد $j$ام در سطر $i$ام برابر با $a_{i,j}$ و نشان دهنده‌ی کشوری است که خانه‌ی $(i, j)$ را اداره می‌کند. (اگر این عدد صفر باشد، به این معناست که آن خانه منطقه‌ی آزاد است) $$0 \le a_{i,j} \le 10^6$$ سپس در هر یک از $k$ خط بعدی سه عدد $x, y, p$ آمده که نشان دهنده‌ی وجود سفارت کشور $p$ در خانه‌ی $(x, y)$ است. $$1 \le x \le n$$ $$1 \le y \le m$$ $$1 \le p \le 10^6$$ # خروجی اگر رسیدن به مقصد ممکن نبود `-1` و در غیر این صورت کمینه هزینه‌ی ممکن برای رسیدن به مقصد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 4 3 1 1 4 4 0 0 1 2 0 2 2 2 1 1 0 0 1 1 1 1 1 2 2 3 3 1 1 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 4 4 2 1 1 4 4 0 0 1 2 0 2 2 2 1 1 0 0 1 1 1 1 1 2 2 3 3 1 ``` ## خروجی نمونه ۲ ``` 2 ```