• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۵۰ مگابایت

محمدرضا در ترم آخر دانشگاه تصمیم گرفت کار کند. چون کار خاصی بلد نبود به صفحه نیازمندی های روزنامه شریف مراجعه کرد و دید مسابقه «کدناک» به دنبال یک نفر می گردد که به شرکت کنندگان مسابقه خوشامد بگوید. چون هیچ کار دیگه ای پیدا نکرد برای این کار apply کرد. کدناک هم چون انتخاب دیگه ای نداشت او را انتخاب کرد. بعد از چند روز محمدرضا کار بهتری پیدا کرد و تصمیم گرفت از این کار استعفا دهد. ولی چون از معین(مامور حراست کدناک) می ترسید تصمیم گرفت برنامه ای بنویسد که کار خوشامد گویی را انجام دهد. ولی متاسفانه در دانشگاه برنامه نویسی اش پسرفت کرده بود. بعد از یک هفته تلاش ناموفق تصمیم گرفت از جوانانی که هنوز برنامه نویسی یادشان نرفته است کمک بگیرد.

ورودی🔗

در سطر اول ورودی یک اسم(شامل یک یا چند کلمه) آمده.

خروجی🔗

در تنها سطر خروجی عبارت Welcome to codenak و در ادامه اسمی که در ورودی آمده را وارد کنید.

مثال🔗

ورودی نمونه ۱🔗

Jack Sparrow

خروجی نمونه ۱🔗

Welcome to codenak Jack Sparrow

ورودی نمونه ۲🔗

Harry

خروجی نمونه ۲🔗

Welcome to codenak Harry

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۵۰ مگابایت

بعد از این که محمدرضا از برنامه که شما نوشتید برای شغل اولش اجرا کرد به سراغ شغل دومش رفت. در این شغل قرار بود تمام کارهای حسابداری یک شرکت را انجام دهد. بعد از یک هفته مدیر عامل شرکت متوجه شد در طی هفته اخیر ۵۰ میلیون تومان به محمد(لبو فروش محله) بدهکار شده است!!! در نتیجه محمدرضا را احضار کرد و دفاتر حساب را با هم بررسی کردند. خلاصه وقتی مدیرعامل شرکت متوجه شد محمدرضا از پس حسابداری شرکت برنمیاید یک حسابدار دیگر استخدام کرد. اما چون محمدرضا در حال تحصیل در دانشگاه شریف بود تصمیم گرفت محمدرضا را در شرکت مشغول کند تا شاید روزی استعدادهای نهفته اش(!!!) نمایان شود. بنابراین به منشی اش گفت هر روز ده هزار عدد تصادفی تولید کند و به محمدرضا بدهد و محمدرضا برای هر عدد سوال زیر را حل کند:

«عدد $x$ به شما داده شده است. مجموع اعداد طبیعی کوچکتر از چه عدد طبیعی ای $x$ برابر آن عدد طبیعی است؟»

محمدرضا هم به یاد قدیم خواست برای حل این سوال کدی بزند اما باز بعد از یک ماه تلاش به جایی نرسید. کمکش کنید تا از این کار اخراج نشود. زندگی خرج دارد.

ورودی🔗

در تنها سطر ورودی عدد $x$ به شما داده می شود. $-10^6 \le x \le 10^6$

خروجی🔗

در تنها سطر خروجی عدد خواسته شده را بنویسید. در صورتی که چنین عددی وجود ندارد عبارت no solution را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

5

خروجی نمونه ۱🔗

11

حاصل جمع اعداد ۱ تا ۱۱(شامل ۱ ولی فاقد ۱۱) برابر ۵۵ = ۵ × ۱۱ است

ورودی نمونه ۲🔗

2.3

خروجی نمونه ۲🔗

no solution

هیچ عددی وجود ندارد که حاصل جمع اعداد کوچکتر از آن ۲.۳ برابر آن عدد باشد.

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

بعد از این که اون شرکت دید محمدرضا داره به شرکت ضرر می زنه ازش شکایت کرد. امیر(مدیر کنترل کیفی کدناک) هم برای این که یه حالی از محمدرضا بگیره یه پاپوشی برای محمدرضا درست کرد. از قضا دست امیر به «بچه های بالا» می رسید و تونست محمدرضا رو به نفر اول لیست مجرمان تحت تعقیب تهران تبدیل کنه. شایان(رئیس پلیس تهران) هم یه عملیات ضربتی و سنگین تنظیم کرد تا محمدرضا رو دستگیر کنه. عملیات به این شکل بود که یک روز صبح که محمدرضا در حال رفتن به دانشگاهه تو یه پارک گیرش بیارن و به سمتش گوجه پرتاب کنن. عملیات این طوری تنظیم شده بود:

• زمین پارک به صورت یک جدول $h$ در $w$ در نظر گرفته می شود.

• مامورین پلیس فقط می توانند در راستای طول یا عرض جدول شلیک کنند. مثلا اگر یک مامور در سطر ۵ ام و ستون ۷ ام قرار داشته باشد فقط می تواند گوجه اش را در راستای ستون ۷ ام یا سطر ۵ ام پرتاب کند.

• اگر یکی از مامورین در مسیر حرکت گوجه باشد گوجه به مامور برخورد می کند و متوقف می شود.

• محمدرضا در سطر ۰ ام و ستون ۰ ام جدول قرار دارد. بنابراین شماره بعضی از سطرها و ستون ها منفی است

• مامورین پلیس با لباس مبدل هر کدام در یکی از خانه های جدول مستقر شده اند و از آن جا تکان نمی خورند.

  به نظر شما چند گوجه به محمدرضا برخورد می کند؟

ورودی🔗

در سطر اول ورودی عدد $N$ (تعداد پلیس هایی که با لباس مبدل در پارک مستقر شده اند) آمده است. سپس در $N$ سطر بعدی در هر سطر دو عدد $x_i$ و $y_i$ آمده که شماره سطر و ستونی است که مامور $i$ ام در آن حضور دارد.

$1 \le n \le 1000$ $-1000 \le x_i, y_i \le 1000$

خروجی🔗

در تنها سطر خروجی تعداد گوجه هایی که به محمدرضا برخورد می کند را بنویسید.

مثال🔗

ورودی نمونه ۱🔗

6
1 1
0 1
0 2
1 0
-1 0
0 -1

خروجی نمونه ۱🔗

4

مامور شماره ۱ اصلا توانایی شلیک گوجه به سمت محمدرضا رو نداره چون فقط می تونه در راستای سطر یا ستون جدول شلیک کنه. مامورهای شماره ۲ و ۶ کافی است در راستای ستون به سمت خانه $(0,0)$ شلیک کنن. مامورهای شماره ۴ و ۵ کافی است در راستای سطر به سمت خانه $(0,0)$ شلیک کنن. مامور شماره ۳ حتی اگر در راستای ستون به سمت خانه $(0,0)$ شلیک کند گوجه اش به مامور شماره ۲ برخورد می کنه و متوقف میشه.

ورودی نمونه ۲🔗

5
1 0
2 0
3 0
1 1
-1 -1

خروجی نمونه ۲🔗

1

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۵۰ مگابایت

بعد از این که محمدرضا از زندان آزاد شد مامورین نظام وظیفه جلوی درب زندان به استقبال او رفتند تا او را به خدمت سربازی ببرند. به خاطر سابقه دار بودن قرار بود محمدرضا خدمت سربازی را لب مرز بگذراند. جایی که همه سرباز ها به ۲ درجه ۱(بدبخت) و ۲(خیلی بدبخت) تقسیم می شدند. یک روز سر صف فرمانده پرسید «کی این جا ریاضی خونده؟» محمدرضا هم دستش را بالا برد. فرمانده گفت درجه سربازها رو طوری تغییر بده که از یک مکان به طرف راست تمام سربازها درجه ۲ و به طرف چپ همه درجه ۱ باشند. محمدرضا چون می دانست درجه هر کسی را که تغییر دهد یک کتک حسابی از او می خورد خواست که کمترین تعداد تغییر ها را انجام دهد. چون شب گذشته چند تا از سربازها شام محمدرضا را به زور از او گرفتند محمدرضا به شدت گرسنه است و توانایی فکر کردن ندارد. به همین خاطر از شما می خواهد که برایش این کار را انجام دهید.

ورودی🔗

در سطر اول ورودی عدد $n$ (تعداد سربازها در صف) آمده است.

در $n$ سطر بعدی عدد ۱ و ۲ آمده. عدد $i$ ام درجه سربازی است که در مکان $i$ ام صف ایستاده است. $0 \le n \le 10^7$

خروجی🔗

در تنها سطر خروجی حداقل تعداد تغییر درجه های لازم برای اجرای درخواست فرمانده را بنویسید.

مثال🔗

ورودی نمونه ۱🔗

7
2 1 1 1 2 2 1

خروجی نمونه ۱🔗

2

کافی است درجه اولین سرباز و آخرین سرباز را عوض کند تا سربازهای درجه ۱ و درجه ۲ در مکان ۵ ام از هم جدا شوند و سربازهای درجه ۱ قبل از مکان ۵ ام و سربازهای درجه ۲ بعد از مکان ۵ ام باشند.

ورودی نمونه ۲🔗

8
1 1 1 2 1 1 2 2

خروجی نمونه ۲🔗

1

با تغییر درجه سرباز ۴ ام تمام سربازهای درجه ۱ قبل از سرباز ۷ ام و تمام سربازهای درجه ۲ بعد از سرباز درجه ۷ ام قرار می گیرند.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

محمدرضا وقتی به زندان افتاد، از دانشگاه اخراجش کردند. حالا محمدرضا بعد از چند سال و بعد از گذراندن دوران مقدس سربازی می‌خواد دوباره کنکور بده و بره دانشگاه. اون خیلی هم اصرار داره که حتما دانشگاه شریف بره. فقط مشکل اینه که محمدرضا خیلی استعداد نداره. اون بعد از دادن کنکور می‌فهمه که دقیقا آخر شده. حالا می‌خواد انتخاب رشته کنه.

به غیر از محمدرضا $n$ نفر در کنکور شرکت کردن. هر نفر در برگه‌ی انتخاب رشتش دقیقا $k$رشته از رشته‌های داشنگاه شریفو انتخاب کرده که به ترتیب بررسی می‌شن. یعنی اگر یک نفر رشته‌ی اولی که انتخاب کرده رو قبول شه(هنوز ظرفیت داشته باشه) دیگه به سراغ رشته‌های بعدی نمیرن و همون رشته‌رو قبول میشه. به همین شکل انقدر از روی لیست انتخاب رشتش میرن جلو تا برسن به رشته‌ای که هنوز ظرفیت داره و اونجا قبول میشه. در کل هم ممکنه که یک نفر کلا در هیچ دانشگاهی قبول نشه که اینطوری باید بخونه برا سال بعد یا بره سربازی.

در کل توی دانشگاه شریف $m$ رشته وجود داره. رشته‌ی $i$م، $a_i$ نفر ظرفیت داره.

حالا محمدرضا می‌خواد ببینه چند حالت وجود داره که انتخاب رشته بکنه و رشته‌ای رو قبول شه. دوتا انتخاب رشته متفاوت هستند اگر توی لیست انتخاب رشته‌ها یک $i$ وجود داشته باشه که رشته‌ی $i$م در دو لیست متفاوت باشند. دقت کنید محمدرضا انقدر می‌فهمه که رشته‌ی تکراری تو لیستش نزاره. چون ممکنه تعداد حالات خیلی زیاد شه محمدرضا فقط باقی‌مانده‌ی این عدد بر $10^9 + 7$ میخواد.

ورودی🔗

در خط اول ورودی سه عدد $n$ و $m$ و $k$ آمده است که به ترتیب نمایانگر تعداد شرکت کننده‌ها در کنکور(بدون احتساب محمدرضا)، تعداد رشته‌های دانشگاه شریف و تعداد انتخاب‌های هرنفر است.

در خط بعدی $m$ عدد آمده‌است که عدد $i$م نمایانگر ظرفیت رشته‌ی $i$ است. ظرفیت هر رشته حداکثر یک میلیون است.

سپس در $n$ خط بعدی در هر خط $k$ عدد آمده است. خط $i$م نشان‌دهنده‌ی انتخاب رشته‌ی رتبه‌ی $i$م است. عدد اول در هر خط انتخاب اول، عدد دوم انتخاب دوم و به همین شکل عدد $k$م انتخاب $k$م هر نفر است. اعداد داده شده همگی طبیعی و کوچکتر مساوی $m$ هستند. ممکن است در انتخاب رشته‌ی یک نفر از یک رشته چند بار بیاید. $1 \le n,m \le 1000$ $1 \le k \le 100 \le m$

خروجی🔗

فقط یک عدد خروجی دهید که باقی‌مانده‌ی تعداد حالات انتخاب رشته‌ی محمدرضا بر $10^9 + 7$ را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

6 3 2
2 2 2
1 2
2 3
1 3
1 2
2 3
3 1

خروجی نمونه ۱🔗

0

ورودی نمونه ۲🔗

3 3 2
2 1 1
1 2
2 3
2 3

خروجی نمونه ۲🔗

4

روش‌های انتخاب محمدرضا که بتونه قبول شه ایناس: 1 2 - 1 3 - 2 1- 3 1

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

بعد از این که محمدرضا هرطور شده رفتش دانشگاه شریف حالا به دلایل عجیبی مدرسه‌های شهرش بهش پیشنهاد دادن که بیاد اونجا درس بده. محمدرضا که تحت هیچ شرایطی دیگه نمیخواد از دانشگاه اخراج بشه باید سر همه‌ی کلاسای دانشگاه شرکت کنه.

محمدرضا در طول هفته $n$ کلاس در دانشگاه داره. کلاس‌های دانشگاه میتونه هر ساعتی در روز و هر روزی در هفته باشه.

در کل $m$ مدرسه به محمدرضا پیشنهاد تدریس داده‌اند. کلاس‌های تدریس هم توی شهر محمدرضا روز و ساعت خاصی نداره و می‌تونه هر موقعی باشه. هر کلاس هم درامد خاص خودش را دارد.

محمدرضا چون خیلی پول‌پرسته و به روح معلمی هیچ اهمیتی نمیده میخواد بیشترین سود ممکن در هفته رو داشته باشه. ولی خب خودش نمیدونه چجوری باید کلاساشو انتخاب کنه و شما باید به اون کمک کنید. به این امید که شاید درصدی از درامدشو بهتون بده.

به دلیل متروهای فوق سریع از دانشگاه به شهر محمدرضا، اون میتونه در زمان بسیار کمی خودشو به شهرشون برسونه و بره سر کلاس. یعنی اگر دوشنبه‌ها تا ساعت ۱۷ داخل دانشگاه کلاس داره میتونه توی شهرشون از ساعت ۱۷ تا ۱۹ درس بده و به موقع برسه.

ورودی🔗

در خط اول ورودی دو عدد $n$ و $m$ آمده است که به ترتیب نمایانگر تعداد کلاس های دانشگاه و تعداد مدرسه‌های پیشنهاد شده به محمدرضا است.

در $n$ خط بعدی در هر خط سه عدد $d$، $s$ و $e$ می‌آید که به ترتیب نشان‌دهنده‌ی روز برگزاری کلاس(۰ به معنی شنبه، ۱ به معنی یکشنبه ...)، ساعت شروع و ساعت پایان کلاس است.

در $m$ خط بعدی در هر خط چهار عدد $d$، $s$ ،$e$ و $w$ می‌آید که به ترتیب نشان‌دهنده‌ی روز برگزاری کلاس(۱ به معنی شنبه، ۲ به معنی یکشنبه ...)، ساعت شروع، ساعت پایان و درآمد حاصل از کلاس است. $1 \le n,m \le 16$ $0 \le s < e \le 24$ $0 \le d < 7$ $1 \le w \le 10\ 000$

خروجی🔗

در تنها خط خروجی بیشترین درآمد ممکن برای محمدرضا را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

2 2
1 13 15
3 13 15
1 15 17 5000
3 12 14 2000

خروجی نمونه ۱🔗

5000

ورودی نمونه ۲🔗

2 3
1 8 10
1 10 12
2 19 22 10000
2 18 20 7000
2 21 24 5000

خروجی نمونه ۲🔗

12000

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت

بعد از ۳ بار افتادن درس «معادلات دیفرانسیل» و ۲ بار حذف «فیزیک ۲» محمدرضا تونست مدرک کارشناسی اش رو بگیره. یک روز که محمدرضا رفت مدرک کارشناسی اش رو بگیره و بعدش بره برای آزمون کارشناسی ارشد ثبت نام کنه تو دانشکده یکی از اساتید رو دید:

استاد: تو مگه درس طراحی الگوریتم رو پاس کردی؟

محمدرضا: بله استاد.

استاد: حتما اشتباهی شده. برو این سوال رو حل کن ببینم. اگر نتونی حل کنی مدرک بی مدرک.

محمدرضا: :|

یه کمکی به محمدرضا بکنین که بتونه مدرکش رو بگیره.

سوال استاد: «$n$ تا عملیات داریم که هر کدوم از یکی از عملیات های ضرب و جمع و تفریق و یک عدد تشکیل شدند. مثلا ۴+ یا ۲× یا ۳-. می خوایم با این عملیات ها با شروع از عدد ۱ عدد $k$ رو بسازیم. به چند روش می تونیم این کار رو بکنیم به شرطی که در طی عملیات هامون عدد بیشتر از 2*k و کمتر از 1 تولید نشود و امکان استفاده از هر عملیات به هر تعداد باری که می خوایم باشه؟ چون این عدد ممکنه خیلی بزرگ بشه باقی مونده این عدد به ۱۰۰۰۰۰۰۰۰۷ رو حساب کن.»

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $k$ به ترتیب آمده اند.

در $n$ سطر بعدی در هر سطر یک عملیات و یک عدد($a_i$) اومده. عملیات و عدد با یک فاصله از هم جدا شده اند

$0 \le n, k \le 5000$ $0 \le a_i \le 5000$

خروجی🔗

در تنها سطر خروجی تعداد راه های ساخت عدد $k$ با استفاده از این عملیات ها رو بنویسید.

مثال🔗

ورودی ۱🔗

3 7
+ 3
* 2
+ 5

خروجی ۱🔗

3

توضیح🔗

عدد ۶ را به روش های زیر می توان تولید کرد. دقت کنید که هر عملیات روی خروجی عملیات های گذشته انجام می شود(که این موضوع با پرانتز گذاری در روش های زیر مشخص شده است).

((1*2)+5)
((1+3)+3)
(((1*2)*2)+3)

ورودی ۲🔗

4 6
+ 3
* 2
- 7
+ 5

خروجی ۲🔗

infinite

توضیح🔗

عدد ۶ را با نامتناهی روش می توان ساخت: (برای وضوح بیشتر پرانتز ها را حذف می کنم اما روش اعمال عملیات ها مشابه قبل است. مثلا در خط اول ابتدا 2*1 محاسبه می شود و سپس 2(حاصل عملیات قبلی) در عملیات 2× مورد استفاده قرار می گیرد و سپس 4 در عملیات 2× مورد استفاده قرار می گیرد و ...)

1*2*2*2-7+5
1*2*2+2-7*2*2*2-7+5
1*2*2+2-7*2*2*2-7*2*2*2-7+5
...