+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پوپک از خواب بیدار می‌شود... به یاد می‌آورد که خوابی دیده است اما جزییات این خواب در خاطرش نیست... پوپک می‌داند که او در خوابش دو کیسه تیله داشته است که در هر کیسه حداقل یک تیله بوده است. پوپک می‌داند که تعداد تیله‌های کیسه اول مقسوم‌علیهی از عدد $a$ بوده و تعداد تیله‌های کیسه دوم مقسوم علیهی از عدد $b$ بوده است. همچنین پوپک به یاد دارد که دو کیسه‌اش خیلی سنگین نبودند و در مجموع حداکثر $x$ تیله در دو کیسه قرار داشته است. در همین هنگام پوپک، توک را می‌بیند و ماجرا را برای او تعریف می‌کند. توک نیز خیلی سریع تعداد خواب‌های متفاوتی که ممکن است پوپک دیده باشد را می‌شمارد و این تعداد را به او می‌گوید... در همین هنگام توک یه دل نه صد دل عاشق پوپک می‌شود ... # ورودی در تنها خط ورودی به ترتیب سه عدد $a$ و $b$ و $x$ آمده است. $$1 \le a, b\le 1\ 000$$ $$2 \le x \le 1\ 000$$ # خروجی در تنها خط خروجی تعداد خواب‌های متفاوتی که ممکن است پوپک دیده باشد را چاپ کنید. ## ورودی نمونه ۱ ``` 2 2 2 ``` ## خروجی نمونه ۱ ``` 1 ``` تنها حالت ممکن این است که در هر دو کیسه دقیقا $1$ تیله قرار گرفته باشد. ## ورودی نمونه ۲ ``` 7 7 14 ``` ## خروجی نمونه ۲ ``` 4 ``` چهار حالت مختلف برای تعداد تیله‌های در کیسه $(1, 1)$ و $(1, 7)$ و $(7, 1)$ و $(7 , 7)$ هستند.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- برنامه‌ای بنویسید که ۲ عدد ۳ رقمی را به صورت برعکس مقایسه کند. به این صورت که ارزش یکان هر عدد بیش دهگان و ارزش دهگان بیش از صدگان است. بطور مثال: $$321 < 123$$ $$201 > 800$$ # ورودی در خط اول عدد اول و در خط بعدی عدد دوم وارد می‌شود. اعداد ورودی مثبت و سه‌رقمی هستند. # خروجی عددی که به صورت برعکس کوچک‌تر بوده باید در سمت چپ قرار بگیرد و بعد علامت کوچک‌تری و بعد عدد دیگر باید قرار بگیرد، مگر اینکه دو عدد در حالت برعکس برابر باشند که در آن صورت بین اینها یک علامت مساوی قرار می‌دهیم(باید همه اجزا با $space$ ازهم جدا شوند.) # مثال ## ورودی نمونه ۱ ``` 123 421 ``` ## خروجی نمونه ۱ ``` 421 < 123 ``` ## ورودی نمونه ۲ ``` 123 123 ``` ## خروجی نمونه ۲ ``` 123 = 123 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که *همه استفا عاشق مصطفی هستند*. تیمور که یکی از استف‌های زحمت‌کش مسابقات است عقیده دارد که از بین همه استف‌های عاشق مصطفی، مصطفی خودش عاشق استفی است که بتواند معماهای سخت را حل کند. مصطفی معمایی طرح کرده و آن را برای همه استف‌ها فرستاده است تا آن را حل کنند. او جدولی $m \times n$ برای استف‌ها فرستاده که هر خانه از آن `x` یا `y` است. استف‌ها می‌توانند در هر مرحله یک خانه از جدول را انتخاب کنند و محتوای‌ درون آن خانه را به `x` ، ‍`y` یا ‍‍`z` تبدیل کنند. استفی که بتواند در کمترین مراحل کاری کند که شرایط زیر برقرار باشد، این معما را حل کرده است. ۱- مسیری از یکی از خانه‌های سطر اول به یکی از خانه‌های سطر آخر وجود داشته باشد که خانه‌های آن فقط `y` و ‍`z` باشد. ۲- مسیری از یکی از خانه‌های ستون اول به یکی از خانه‌های ستون آخر موجود باشد که خانه‌های آن فقط `x` و ‍`z` باشد. یک مسیر، دنباله‌ای از خانه‌های جدول است که در آن هر خانه به جز خانه آخر، با خانه بعدی‌اش مجاور ضلعی است. از آنجایی که تیمور حوصله‌ی این سوسول بازی‌ها را ندارد از شما خواسته تا به او کمک کنید تا نظر مصطفی را جلب کند. # ورودی در خط اول ابتدا عدد $n$ که تعداد سطر‌های جدول است و سپس عدد $m$ که تعداد ستون‌های جدول است به شما داده می‌شود. در هر یک از $n$ خط بعدی، یک رشته‌ به طول $m$ از حروف `x` و `y` داده شده است. $$ 1 \le n , m \le 1 \ 000$$ # خروجی در یک خط کمترین مراحل تغییر لازم برای برآورده کردن شرط‌های مصطفی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 2 xy yx ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 3 5 xyxyy yyyxy yyyyx ``` ## خروجی نمونه ۲ ``` 3 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مجید که به تازگی برنامه‌نویسی یاد گرفته است، شبه کدی برای مرتب سازی صعودی یک آرایه به اسم $a$ به طول $n$ نوشته است که به وضوح غلط است. این تکه کد به صورت زیر است: ```c for i = 1 to n - 2 for j = 1 to n - 1 if a[j] > a[j + 1] swap(a[j], a[j + 1]) ``` میلاد جایگشتی از اعداد ۱ تا $n$ دارد که بعضی از اعداد آن مشخص نیست و به جای آن صفر گذاشته شده است. حال ما می‌خواهیم بدانیم آیا می‌توانیم جای صفرهای جایگشت، اعدادی قرار بدهیم به طوری که در انتها: 1. کد مجید نتواند جایگشت را به درستی به صورت صعودی مرتب کند. 2. هر یک از اعداد ۱ تا $n$ دقیقاً یک‌بار در آرایه آمده باشند. (برای فهمیدن بهتر، بخش ورودی و توضیح نمونه‌ها را بخوانید.) # ورودی در خط اول عدد $n$ که تعداد اعداد جایگشت است به شما داده می‌شود. در خط بعدی $n$ عدد،بین $0$ تا $n$، که با فاصله جدا شده‌اند به شما داده می‌شود که اعداد جایگشت میلاد است. $$1 \le n \le 100\ 000$$ # خروجی اگر می‌توانستیم صفر‌ها را به گونه‌ای عوض کنیم که شرایط صورت سوال را داشت در خط اول خروجی عبارت ‍‍‍‍```Yes``` و در خط بعدی جایگشت کامل را به همراه اعدادی که به جای صفرها جایگزین شده‌اند چاپ کنید. (چنانچه چندین جایگشت وجود داشت، شما به دلخواه یکی از آن‌ها را چاپ کنید.) در غیر اینصورت در یک خط عبارت ```No``` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 1 3 0 2 ``` ## خروجی نمونه ۱ ``` No ``` توضیح: تنها عددی که می‌تواند جای ۰ بگذارد عدد ۴ است که برنامه مجید می‌تواند این جایگشت را مرتب کند. ## ورودی نمونه ۲ ``` 4 0 0 0 0 ``` ## خروجی نمونه ۲ ``` Yes 4 3 2 1 ``` توضیح: اگر جایگشت فوق را به برنامه مجید بدهیم آن را به درستی مرتب نمی‌کند. توجه کنید که جایگشت فوق یکی از جواب های مسئله است؛ جایگشت‌های دیگری نیز وجود دارد که برنامه‌ی مجید روی آن‌ها درست کار نمی‌کند.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که _همه استفا عاشق مصطفی هستند_. امیر روی میز سرور (که مصطفی پشت آن می‌نشیند) تکه کاغذی پیدا کرده است که روی آن یک رشته پرانتزگذاری معتبر به صورت رنگی نوشته شده است و هر حرف آن به رنگ خاصی است. او پی برد که یکی از استف‌ها با سلیقه‌ی خاصی پرانتزگذاری را به صورت رنگی برای بدست آوردن دل مصطفی نوشته است. او متوجه می‌شود که استف عاشق از سبک رنگ آمیزی کوبیسم استفاده کرده است. رشته پرانتزگذاری $s$ با طول $n$ را در نظر بگیرید. برای هر حرف $i$ ،$m_i$ را برابر با اندیس پرانتز باز یا بسته متناظر با حرف $i$ رشته در نظر بگیرید. از آنجا که این پرانتزگذاری معتبر است، مقدار $m_i$ به ازای هر $i$ وجود دارد. برای مثال اگر دنباله پرانتزگذاری ما `(())()` باشد، دنباله‌ی $m$ برابر با $\{4, 3, 2, 1, 6, 5\}$ خواهد بود. این رشته یک رنگ آمیزی کوبی است اگر ویژگی‌های زیر را داشته باشد: 1. هر حرف به یکی از رنگ‌های ۱ تا $k$ رنگ شده باشد. 2. رنگ حرف $i$ و رنگ حرف $m_i$ باید برابر باشد. 3. اگر $m_i \ne i-1$ رنگ حرف $i$ با $i-1$ متفاوت باشد. 4. اگر $m_i \ne i+1$ رنگ حرف $i$ با $i+1$ متفاوت باشد. امیر می‌خواهد تعداد رنگ‌آمیزی‌های کوبی متفاوت $s$ با $k$ رنگ را زیر آن تکه کاغذ بنویسد تا مصطفی را بیشتر حیرت‌زده کند! از آنجا که این عدد خیلی بزرگ‌ است، باقی‌مانده آن را بر $10^9 + 7$ برایش بدست بیاورید. # ورودی در سطر اول ورودی دو عدد $n$ و $k$ آمده است. سپس در سطر بعد رشته پرانتزگذاری $s$ آمده‌است. تضمین می‌شود $s$ یک پرانتزگذاری معتبر است. $$1 \le k \le n \le 200\ 000$$ $$|s| = n$$ # خروجی در تنها سطر خروجی باقی‌مانده تعداد روش‌های رنگ‌آمیزی کوبی $s$ با $k$ رنگ را بر $10^9+7$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 2 (()) ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 6 3 (())() ``` ## خروجی نمونه ۲ ``` 12 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو که فردی بسیار پول پرست است، جهت صرفه‌جویی در تعداد حروف پیامک‌هایش به فشرده‌سازی رشته‌ها روی آورده. روش عمو برای فشرده‌سازی به این صورت است: او در ابتدا جایگشتی از اعداد ۱, ۲, ..., $k$ انتخاب میکند. سپس رشته‌ی خود را به دسته های پشت سر هم $k$ حرفی تقسیم میکند (طول رشته باید به $k$ بخش‌پذیر باشد) و روی هر دسته از حروف، جایگشت خود را اعمال میکند. سپس رشته‌ی بدست آمده را بوسیله‌ی روش RLE که در ادامه توضیح داده خواهد شد، فشرده میکند. اعمال جایگشت $p$ روی یک دسته از $k$ حرف یعنی حرف $p_1$م را در جایگاه اول قرار داده، حرف $p_2$م را در جایگاه دوم و... برای مثال اعمال جایگشت {۲ ,۴ ,۱ ,۳} روی رشته‌ی $abcd$ آن را تبدیل به $cadb$ میکند. اعمال این جایگشت با دسته دسته کردن روی رشته‌ی $abcdefgh$، رشته‌ی $cadbgehf$ را نتیجه میدهد. رشته‌ی جایگشت داده شده توسط RLE (یا run-length encoding) فشرده میشود. جهت جلوگیری از محاسبات پیچیده، طول رشته‌ی فشرده‌شده را برابر تعداد گروه حرف‌های برابر پشت سر هم درنظر میگیریم. برای مثال طول رشته‌ی $aabcaa$ پس از فشرده‌شدن توسط RLE را ۴ در نظر میگیریم. (یک گروه ۲ حرفی a، یک گروه تک حرفی b، یک گروه تک حرفی c و یک گروه ۲ حرفی a) عمو میخواهد پیامکی را با روش گفته شده فشرده کرده و بفرستد. واضح است که طول رشته‌ی نهایی به جایگشت انتخاب‌شده مربوط است. شما با داشتن متن پیامک عمو، جایگشتی انتخاب کنید که پس از فشرده‌سازی بوسیله‌ی آن طول پیامک کمینه شود و این طول کمینه را خروجی دهید. # ورودی سطر اول تنها شامل عدد $k$ است. در سطر بعدی پیامک عمو بصورت یک رشته از حروف کوچک انگلیسی به طول حداکثر ۵۰۰۰۰ آمده است. $$2 \le k \le 16$$ # خروجی در تنها سطر خروجی یک عدد چاپ کنید که برابر کمترین طول ممکن برای پیامک عمو است. # ورودی نمونه ``` 4 abcabcabcabc ``` # خروجی نمونه ``` 7 ``` در این مثال با انتخاب جایگشت {۲ ,۳ ,۴ ,۱} نتیجه‌ی بهینه بدست می‌آید.

+ محدودیت زمان:۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند! رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت! تبریک! شما کیک پخش‌کن جلسه‌ی کنکور شده‌اید! باید کاری برای حلی سه‌ای هایِ دوست داشتنی انجام دهید! حلی سه‌ای ها از روش‌های پیشرفته‌ی تقلب استفاده می‌کنند! یکی از این روش‌ها درخت تقلب است! به این صورت که هر نفر به یک راس متناظر می‌شود! از طرف حلی سه‌ای‌ ها(!) از شما خواسته شده که برای تقلب آسان تر کار‌های زیر را بی‌چون و چرا انجام دهید! در ابتدا یک راس به منزله‌ی مقر فرماندهی(با شماره ۱) داریم که از دیشب سر صندلی خود حاضر بوده است. هر بار یکی از این دو کار را انجام می‌دهیم: + `1 p` : طبق برنامه یک حلی سه‌ای وارد می‌شود! اگر قبل از ورود این فرد $k$ فرد سر جلسه حضور داشتند ما شماره‌‌ی $k+1$ را به آن فرد اختصاص می‌دهیم و آن را به راس شماره $p$ وصل می‌کنیم. + `d v 2` : دورترین راس از مقر فرماندهی را که با $v$ حداکثر $d$ یال فاصله دارد را پیدا می‌کنیم و آن را گزارش می‌دهیم! همانطور که معلوم است. گراف همیشه درخت باقی می‌ماند. # ورودی در خط اول ورودی $q$ تعداد کوئری‌ها می‌آید. سپس $q$ خط هر کدام همان طور که شرح داده شد آمده‌اند. $$1 \leq q \leq 200\ 000 $$ $$0 \leq d \leq 1\ 000\ 000\ 000$$ در کوئری‌ها تضمین میشود راس $p$ و $v$ در گراف وجود دارند. # خروجی به ازای هر کوئری نوع دو، جواب آن را چاپ کنید. اگر چند جواب درست وجود داشت یکی از آن‌ها را به دلخواه چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 1 1 1 1 2 2 10 1 3 2 2 10 ``` ## خروجی نمونه ۱ ``` 2 4 ``` ## ورودی نمونه ۲ ``` 9 1 1 1 1 1 2 2 3 3 1 4 2 3 4 1 4 1 6 2 4 2 ``` ## خروجی نمونه ۲ ``` 4 5 7 ```