+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی که از کدزدن خسته شده‌است، به تازگی به رشته‌ی صنایع علاقه پیدا کرده است. به همین دلیل تصمیم گرفته است تا در مورد این رشته تحقیق کند. او به افراد مختلفی مراجعه می‌کند و هرکدام یک مقداری اطلاعات به او می‌دهند. او به اندازه‌ی مقدار اطلاعاتی که از اشخاص می‌گیرد متعجب می‌شود. مثلا اگر یک عدد اطلاعات بگیرد می‌گوید `Wow!`، اگر دوتا اطلاعات بگیرد می‌گوید`Woow!` و به همین شکل مقدار کشیدن کلمه(تعداد `o` ها) زیاد می‌شود. حالا شما باید بگویید که اگر یک نفر به اندازه‌ی $n$ به مهدی اطلاعات بدهد، ما باید انتظار چه کلمه‌ای را از او داشته باشیم.  # ورودی در تنها سطر ورودی یک عدد طبیعی $n$ به شما داده شده است که نمایانگر مقدار اطلاعات داده‌شده به مهدی است. $$ 1 \le n \le 10 $$ # خروجی خروجی شامل یک کلمه است،‌ که نشان‌دهنده‌ی کلمه‌ ایست که مهدی بعد از شنیدن اطلاعات راجع به رشته‌ی صنایع می‌گوید. # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` Wow! ``` ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` Woow! ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی که از کدزدن خسته شده‌است، دوست ندارد که در سوال‌هایی که در آن‌ها نیاز به کد زدن هست، از نام او استفاده شود. چندی پیش مهدی متوجه شد که پویان (که یک نوجوان تپل است) و دو نفر از دوستانش به دور از چشم او تعدادی صورت سوال برای مسابقه‌ای در Quera نوشته‌اند و از او بعنوان شخصیت اصلی داستان‌های آن استفاده کرده‌اند. این با معیارهای مهدی جور در نمی‌آید؛ پس او تمام تلاشش را می‌کند که صورت آن سوال‌ها را تغییر دهد. این سه نفر، پویان و دو نفر از دوستانش، هر یک در تعدادی از روزهای هفته به Quera می‌روند. مهدی در آغاز هفته روزهایی از هفته که هریک از این سه تن در Quera هستند را از آن‌ها پرسیده است. او می‌خواهد بداند چند روز در هفته می‌تواند به Quera برود که هیچ‌یک از این افراد در آنجا نباشند تا بتواند صورت سوال‌ها را به دلخواه خودش تغییر دهد. حال مهدی برنامه‌ی روزهایی که این سه نفر به Quera می‌روند را به شما می‌دهد و شما بگویید که مهدی چند روز در این هفته می‌تواند به اصلاح این صورت سوال‌ها بپردازد. # ورودی در ورودی روز‌هایی از هفته که هریک از این افراد به Quera می‌روند در این قالب آمده‌است: توصیف روز‌های هر یک از این سه فرد در دو سطر آمده است. (پس در مجموع ورودی شامل ۶ سطر می‌شود.) در سطر اول هر توصیف تعداد روز‌هایی که این فرد در هفته به Quera می‌رود آمده‌است و سپس در سطر بعدی آن، نام روز‌هایی که آن فرد به Quera می‌رود آمده‌است. تضمین می‌شود که تعداد این روز‌ها در سطر اول هر توصیف، با تعداد نام روزها در سطر دوم آن برابر است و نام یک روز از هفته در یک توصیف حداکثر یک‌ بار آمده‌است. همچنین تضمین می‌شود هریک از این افراد در این هفته حداقل یک روز به Quera می‌روند. نام روز‌های هفته: + shanbe + 1shanbe + 2shanbe + 3shanbe + 4shanbe + 5shanbe + jome # خروجی خروجی شامل یک عدد است که برابر است با تعداد روز‌هایی که هیچیک از این سه نفر، پویان و دو نفر از دوستانش، به Quera نمی‌روند و مهدی می‌تواند در آن روزها به تغییر صورت سوال‌ها بپردازد. # مثال ## ورودی نمونه ۱ ``` 4 shanbe 1shanbe 2shanbe 3shanbe 1 5shanbe 3 1shanbe 3shanbe 5shanbe ``` ## خروجی نمونه ۱ ``` 2 ``` در این مثال، مهدی می‌تواند در روزهای ۴شنبه و یا جمعه سراغ صورت سوال‌ها برود. ## ورودی نمونه ۲ ``` 2 shanbe 2shanbe 2 1shanbe 3shanbe 3 jome 5shanbe 4shanbe ``` ## خروجی نمونه ۲ ``` 0 ``` در این مثال، مهدی هر روزی از هفته که به Quera برود یکی از این افراد در آنجا حضور دارد و مهدی نمی‌تواند صورت سوال‌ها را تغییر دهد.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی که از کدزدن خسته شده‌است، دیگر حوصله اعدادی که بیشتر از یک رقم دارند را ندارد. به همین خاطر به هر عدد چند رقمی که بر بخورد آن را به شیوه خاص خودش تبدیل به یک عدد تک رقمی می‌کند. به این شکل که عدد مورد نظر را با عدد حاصل از مجموع ارقام آن جایگزین می‌کند و به یک عدد جدید می‌رسد. سپس همین کار را با عدد جدید انجام می‌دهد و تا جایی که به یک عدد تک‌رقمی برسد به این کار ادامه می‌دهد. بعد از مدتی مهدی متوجه شد که با این کار نه تنها راحت تر نشده است، بلکه بیشتر درگیر اعداد شده است. در نتیجه از شما خواسته است در یک رقمی کردن عددها به او کمک کنید.  # ورودی در تنها سطر ورودی یک عدد $n$ می‌آید که نشان دهنده عددیست که باید آن‌ را تک رقمی کنید. $$ 1 \le n \le 10 ^{18} $$ # خروجی در تنها خط خروجی باید عدد تک‌رقمی حاصل از تبدیل $n$ به یک عدد تک‌رقمی طبق روش مهدی چاپ شود. # مثال ## ورودی نمونه ۱ ``` 14 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 123456 ``` ## خروجی نمونه ۲ ``` 3 ``` در مرحله اول عدد 123456 تبدیل به عدد 6 + 5 + 4 + 3 + 2 + 1 = 21 می‌شود. در مرحله دوم عدد 21 تبدیل به عدد 1 + 2 = 3 می‌شود.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی که از کدزدن خسته شده است، به سراغ بازی های دوران کودکی‌اش رفته است. اما چون کسی را نمی‌شناسد که با او این نوع بازی‌ها را انجام دهد، مجبور است قوانین بازی را تغییر داده و یک نفره بازی کند. برای شروع اون می‌خواهد بازی "گردو، شکستم" یک نفره بازی کند. بازی به این صورت است که مهدی در فاصله‌ی $n$ سانتی‌متری از دیوار ایستاده است و میخواهد به دیوار برسد. برای این کار او میتواند پایش را به صورت طولی جلوی پای قبلی بگذارد و به جلو برود و یا پایش را به صورت عرضی جلوی پای قبلی خود بگذارد. هدف این است که او جوری پاهایش را بگذارد و جلو برود که در انتها پایش با دیوار مماس شود. اما مهدی دیگر کد نمی‌زند، برای همین شما باید به اون کمک کنید تا بفهمد چگونه این بازی را ببرد. یعنی به او بگویید که چند بار پایش را طولی و چند بار عرضی بگذارد تا در نهایت مسافت دقیقا $n$ سانتی‌متر را طی کرده و پایش با دیوار مماس شود. و یا به او بگویید که این کار غیرممکن است.  # ورودی در تنها سطر ورودی سه عدد $n$ و $x$ و $y$ به شما داده شده است که به ترتیب نمایانگر فاصله‌ی مهدی تا دیوار و طول و عرض پاهای مهدی است. $$ 1 \le n, x, y \le 100\ 000 $$ # خروجی خروجی شامل دو عدد است که با فاصله از یکدیگر جدا شده‌اند. این اعداد باید به ترتیب نشان‌دهنده‌ی تعداد دفعاتی باشند که مهدی باید پایش را طولی و عرضی بگذارد. ممکن است چند جواب برای یک ورودی وجود داشته باشد. شما می‌توانید هرکدام را به دلخواه چاپ کنید. اگر حالتی وجود نداشت که مهدی پایش را با دیوار مماس کند تنها یک عدد 1- در خروجی چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 10 2 3 ``` ## خروجی نمونه ۱ ``` 2 2 ``` دقت کنید که 0 5 نیز یک جواب صحیح برای مثال شماره ۱ می‌باشد؛ زیرا با ۵ قدم طولی مهدی ۱۰ سانتی‌متر طی می‌کند. ## ورودی نمونه ۲ ``` 10 4 7 ``` ## خروجی نمونه ۲ ``` -1 ``` در این مثال مهدی نمی‌تواند هیچ‌گاه با برداشتن گام‌های بطول ۴ یا ۷ سانتی‌متر، ۱۰ سانتی‌متر جلو برود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی که از کدزدن خسته شده‌است، از تمام شکل های مستطیلی هم بدش می‌آید(به خاطر مستطیلی بودن LCD کامپیوتر). بنابر این میخواهد همه چیز را به شکل مثلث تبدیل کند. برای تمرین او چوبی به طول $n$ در انباری پیدا کرده است و تصمیم گرفته به وسیله آن قاب عکسی مثلثی شکل برای خودش بسازد! به این شکل که با دو برش این چوب را به سه تکه تقسیم می‌کند و آن ها را طوری به هم می‌چسباند که تشکیل یک مثلث دهند. البته مهدی با مترش تنها طول های طبیعی را می‌تواند اندازه گیری کند و تکه چوب هایی که می‌برد طولشان برابر با عددی طبیعی خواهد بود. حال این سوال برای مهدی پیش آمده که با این فرایند چند نوع قاب عکس مختلف می‌تواند بسازد؟ دو قاب عکس مثلثی متفاوت در نظر گرفته می‌شوند اگر مجموعه‌ی طول اضلاع آن‌ها با یکدیگر متفاوت باشند. (به مثال‌ها و شکل‌هایشان توجه کنید!) # ورودی در تنها سطر ورودی عدد طبیعی $n$ آمده است که طول چوب اولیه را نشان می‌دهد. $$ 3 \le n \le 1\ 000\ 000 $$ # خروجی در تنها سطر خروجی باید تعداد قاب عکس های مختلفی که مهدی می‌تواند بسازد چاپ شود. # مثال ## ورودی نمونه ۱ ``` 5 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 12 ``` ## خروجی نمونه ۲ ``` 3 ``` توضیح مثال ۲: مهدی با چوبی به طول ۱۲، قاب عکس‌هایی به شکل‌های زیر می‌تواند بسازد. 

+ محدودیت زمان: ۳ ثانیه + **محدودیت حافظه: ۴۰ مگابایت** ---------- مهدی که از کدزدن خسته شده‌است، امتحان درس مبانی برنامه‌نویسی را خراب کرده‌است. او می‌داند که استاد درس مبانی دقیقا $k$ نفر را می‌اندازد. مهدی می‌خواهد بداند که آیا مبانی را می‌افتد یا نه. برای همین میخواهد نمره‌ی اولین کسی که درس را می‌افتد (یا $k$امین کمترین نمره) را پیدا کند. نمره‌ی نفر $i$م به ترتیب الفبا، $a_i$ است. چون تعداد دانشجویان زیاد است، استاد نمره‌ها را به این صورت رد می‌کند: $$ a_1 = m $$ $$ a_i =(x \times a_{i-1} + y) \ mod \ p \ (2 \le i \le n) $$ که $p$ برابر است با $10^9 + 7$. **به محدودیت حافظه‌ی غیر معمول در این سوال دقت کنید!** # ورودی در تنها سطر ورودی به ترتیب اعداد $n$، $k$، $m$، $x$، $y$ به شما داده شده است. $$ 1 \le k \le n \le 10\ 000\ 000 $$ $$ 0 \le m, x, y < p $$ # خروجی در تنها خط خروجی نمره‌ی $k$امین کمترین نمره را بنویسید. # مثال ## ورودی نمونه ۱ ``` 5 3 1 1 2 ``` ## خروجی نمونه ۱ ``` 5 ``` در این نمونه، دنباله‌ی نمره‌ها برابر `9 7 5 3 1` است و سومین کوچکترین آن‌ها برابر ۵ می‌شود. ## ورودی نمونه ۲ ``` 5 3 1 1000000006 0 ``` ## خروجی نمونه ۲ ``` 1 ``` در این نمونه، دنباله‌ی نمره‌ها برابر `1 1000000006 1 1000000006 1` است.

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی از کد زدن خسته شده است، از شغل بساز و بفروش که خسته نشده است! زمین بزرگی به ابعاد $n \times m$ به صورت جدولی به $n \times m$ تکه زمین کوچک با مساحت برابر ۱ تقسیم شده است و تکه زمینی که در سطر $i$ و ستون $j$ قرار دارد، در ارتفاع $h_{i,j}$ می‌باشد. مهدی می‌خواهد بیشترین تعداد تکه زمین را انتخاب کرده و در آن خانه بسازد اما این تکه زمین‌ها باید دو ویژگی داشته باشند: ۱. اجتماع آنها یک زیر جدول بشود. (زیر جدول یک زیرمجموعه از خانه‌های جدول است که اجتماعشان به شکل یک مستطیل می‌شود) ۲.ارتفاع‌های تکه زمین‌های هر ردیف از این زیر جدول باید به ترتیب از چپ به راست یک دنباله‌ی حسابی تشکیل دهند. همینطور است دربا‌ره‌ی هر ستون از زیرجدول که باید از بالا به پایین یک دنباله‌ی حسابی تشکیل دهند. حالا مهدی از شما می‌خواهد که به او بگویید که مساحت بزرگترین (پر مساحت ترین!) زیر جدولی که دو شرط بالا را دارد چقدر است. # ورودی در سطر اول ورودی دو عدد $n$ و $m$ آمده است که به ترتیب نمایانگر تعداد سطرها و تعداد ستون‌های جدول تکه زمین‌ها می‌باشد. سپس ارتفاع‌های تکه زمین‌ها به صورت زیر می‌آید: در $n$ سطر در هر سطر $m$ عدد می‌آید که عدد $j$‌امی که در سطر $i$ می‌آید نمایانگر $h_{i,j}$ می‌باشد. $$ 1 \le n,m \le 3000 $$ $$ 0 \le a_{i,j} \le 10^9 $$ # خروجی در تنها سطر خروجی مساحت بیشترین زیرجدول از تکه‌زمین‌ها را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 4 5 3 5 7 2 4 4 4 3 5 3 1 6 3 2 4 ``` ## خروجی نمونه ۱ ``` 9 ``` زیرمستطیل با بیشترین مساحت در این مثال با رنگ آبی مشخص شده‌است:  ## ورودی نمونه ۲ ``` 2 3 0 1 2 1 2 3 ``` ## خروجی نمونه ۲ ``` 6 ```