+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امسال با توجه شرایط کرونایی، مدرسه ی بهرادینا تصمیم گرفته که کلاس ها رو به صورت آنلاین برگزار کنه. بهراد از زنگ های اول متنفره و می خواد بخوابه، اما متاسفانه معلم یک سوال بدیهی اواسط کلاس می پرسه و از تمام بچه ها می خواد که جواب آن سوال را در چت بنویسند، و هر کس هم که جوابش را نفرستد معلم برایش غیبت رد می کند. بهراد سوال معلم رو نمی دونه و از شما می خواد که برنامه ای بنویسید که به سوال معلم پاسخ دهد. و اما سوال معلم: اکنون $n$ نفر داخل کلاس هستند، به چند طریق می توان ۳ نفر از میان دانش آموزان انتخاب کرد؟؟ با توجه به این که می دانیم غیر از معلم و دانش آموزان کسی در کلاس نیست به سوال معلم پاسخ دهید. # ورودی به شما تنها یک عدد $n$ داده می شود که تعداد افراد حاضر در کلاس است. $$1 \le n \le 99$$ # خروجی شما باید جواب سوال معلم را خروجی دهید. ## ورودی نمونه ۱ ``` 4 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` 0 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- معلم بهراد تا مدت ها سرش با کد شما گرم موند و بهرادم به خوابش رسید. اما یک روز که بهراد به کمک کد شما حاضریش رو زده بود، معلم اونو برای حل سوال فیزیک صدا کرد و بله... برای همین معلم بهرادینا تصمیم گرفت که یک مسئله ی دیگه رو به عنوان حضور و غیاب قرار بده. اما بهراد خیلی پررو تر از این حرف هاست و از شما خواسته که یک کد دیگه هم برای این سوال بزنید. معلم یک عدد برای دانش آموزان در چت خصوصی ارسال می کنه و بلافاصله بعد از آن در خط پایینی به همان تعداد عدد ارسال می کنه و دانش آموز باید شکلی رو ارسال کنه. برای این که کار شما کمی سخت تر بشه، شرایط شکل رو بهتون نمی گم و شما باید از روی مثال ها متوجه اون بشید. # ورودی در خط اول به شما یک عدد $n$ داده می شود. در خط دوم هم $n$ عدد به شما داده می شود. (تمامی این عدد ها کمتر از ۱۰۰۰ هستند.) $$1 \le n \le 100$$ # خروجی شکل مورد نظر رو باید چاپ کنید. ## ورودی نمونه ۱ ``` 5 5 4 3 2 1 ``` ## خروجی نمونه ۱ ``` * ** * *** ** * **** *** ** * ***** **** *** ** * ``` ## ورودی نمونه ۲ ``` 5 3 4 2 3 2 ``` ## خروجی نمونه ۲ ``` * * ** * ** *** * ** * *** **** ** *** ** ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بهراد در طول دوران المپیادش واژه های زیادی رو وارد این حرفه کرد، یکی از این واژه ها، واژه ی بدیهیجات بود. از نظر بهراد بدهیجات جمع بدیهی است و به سوالات خاصی گفته می شود. روزی صالح که شخصی بسیار پیگیر است و باید در جریان تمامی اتفاقاتی که هر کجای عالم اتفاق می افتد قرار بگیرد از بهراد خواست که یک مثال از سوالات بدیهیجات بزنه. بهراد هم پاسخ داد: مثلا یک سری عدد به شما داده می شود که همگی آنها با هم جمع شده اند، حالا جمع این اعداد رو به دست بیاورید. صالح هم طبق معمول بدون هیچ دلیل خاصی این سوال رو در کانتست امروز شما گذاشته است. # ورودی به شما یک مجموعه از اعداد داده می شود که پشت سر هم جمع شده اند که مجموع این اعداد از ۱۰۰۰۰ بیشتر نمی شود. # خروجی باید جمع مورد نظر را چاپ کنید. ## ورودی نمونه ۱ ``` 1+2+3 ``` ## خروجی نمونه ۱ ``` 6 ``` ## ورودی نمونه ۲ ``` 10+3+100 ``` ## خروجی نمونه ۲ ``` 113 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مجمع تشخیص مصلحت کلاس، هر ساله از میان زبده ترین دانش آموز کلاس آریان اینا انتخاب میشه. وظیفه ی این افراد گرفتن وقت دبیر ها و جلوگیری از برگزاری کوئیز های کلاسی تعریف شده است. طاها رئیس این مجمعه و روش جدیدی برای رد و بدل کردن اخبار بین اعضا ترتیب داده. این روش به این شکل پایه گذاری شده که طاها خودش عضو شماره ی صفره و بقیه ی اعضا هم هر کدوم شماره ی مخصوص خودشون رو دارن، هر کدوم از اعضا وظیفه داره که هر خبری رو که به دستش میرسه رو به یکی دیگه از اعضا انتقال بده. (البته به جز خود طاها؛ طاها خبر می گیره ولی انتقال نمی ده) متاسفانه مشکلی در این سامانه پیش اومده: طاها متوجه شده طی چیدمانی که انجام داده بعضی از خبر ها اصلا بهش نمی رسه. طاها به تمام کسانی که خبری را دارند که طاها نداره جاسوس می گه و بقیه رو امین می نامه. حالا طاها می خواد بدونه که چند نفر امین در مجمع وجود دارند. # ورودی در خط اول به شما یک عدد $N$ داده می شود و در $N$ خط بعدی به شما یک عدد داده می شود(از صفر تا $N$) که نشان دهنده ی این است که این شخص خبرش را به چه کسی می دهد. $$1 \le N \le 1000$$ # خروجی شما باید یک عدد خروجی دهید که تعداد امین های مجمع است. ## ورودی نمونه ۱ ``` 5 0 4 1 5 4 ``` ## خروجی نمونه ۱ ``` 2 ``` افراد اول و سوم امین های طاها هستند و هر خبری که دریافت کنند به طاها می رسد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آریان پس از این که از شر کنکور خلاص شده، تصمیم گرفته که بزنه توی کار بانکداری و یک بانک رو هم تاسیس کرده. بانک آریان که با نام آریانک شناخته میشه یک بانک معمولی نیست. هر مشتری که وارد بانک میشه یک فیش می گیره و میره توی صف می ایسته (آریان کمی خسیسه و برای بانک صندلی تدارک ندیده). و اما نکته ی عجیب تر کاربرد اون فیش هاست. روی فیش هر کس یک عدد نوشته شده. حال فرض کنید که فرد شماره ی $i$ به سر صف رسیده است و روی فیش او هم عدد $Pi$ نوشته شده است، اگر باجه ای با شماره ی کمتر و یا مساوی $Pi$ خالی باشد، آریان وی را به آن باجه راهنمایی می کند(اگر چند باجه واجد شرایط خالی باشند، آریان او را به هر باجه ای که بخواهد راهنمایی می کند) اما اگر همه ی آن ها اشغال باشند وی باید صبر کند. مردم شهر توی ماه رمضان به علت فشار روزه کمی بی اعصاب شده اند و اصلا نمی خواهند معطل شوند بنابراین اگر کسی در سر صف منتظر بماند، عصبانی می شود و داخل بانک دعوا راه می اندازند. آریان از تمام فیش هایی که ممکن است امروز صادر شود خبر داره، حالا می خواهد بداند که او حداکثر چند نفر را می تونه پذیرش کنه تا داخل بانک دعوا نشه!! حواستان باشد که مشتری های این بانک خیلی پرچونه هستند و زمانی که در هر باجه بنشینند تا آخر وقت اداری بلند نمی شوند. # ورودی در خط اول به شما عدد $N$ داده می شود که تعداد باجه های آریانک است. در خط دوم به شما عدد $M$ داده می شود که حداکثر تعداد مشتری هایی هستند که ممکن است امروز به بانک بیایند. در $M$ خط بعدی به شما یک عدد داده می شود که همان عددی است که روی فیش هر نفر نوشته می شود، این عدد از 1 تا $N$ است. افراد به همین ترتیب ورودی وارد بانک می شوند.(در صورت پذیرش) $$1 \le N, M \le 100000$$ # خروجی شما باید یک عدد خروجی دهید که حداکثر تعداد مشتری است که آریان می تواند بپذیرد تا داخل بانک دعوا نشود. ## ورودی نمونه ۱ ``` 4 3 4 1 1 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 4 6 2 2 3 3 4 4 ``` ## خروجی نمونه ۲ ``` 3 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- توی ماه مبارک رمضان ملت برای افطاری به خونه ی همدیگه میرن و خب مرسومه که یک جعبه شیرینی هم برای صاحب مجلس می برن. مش رمضون از این فرصت استفاده کرده و می خواد یک استارتاپ بزنه (با اون سنش خجالتم نمیکشه!!). شهر مش رمضون اینا $N$ تا خونه داره (که با 1 تا $N$ شماره گذاری شده اند) که خونه های 1 تا $K$ از این خونه ها شیرینی فروشی هستند. شهر مش رمضون اینا $M$ تا جاده ی یک طرفه داره که بین خونه ها کشیده شدن ولی از اونجایی که در این شهر کرونای منحوس هنوز وجود داره، تردد در هر یک از این جاده ها یک جریمه ای داره. (دولت برای کنترل کرونا در این شهر این کار رو انجام داده) و اما ایده ی مش رمضون: مش رمضون می خواد اپلیکیشنی طراحی کنه که مبدا و مقصد کاربر رو دریافت کنه و در صورت امکان مسیری رو بده که از مبدا شروع بشه، از یک شیرینی فروشی بگذره و سپس به مقصد برسه و طبعا کمترین جریمه رو داشته باشه. راستی بگم که شیرینی فروش هم دل داره و ممکنه خودش هم بخواد به خونه ی کسی بره، در این صورت دیگه لازم نیست به شیرینی فروشی دیگه ای بره و از مغازه ی خودش شیرینی می بره. از اون جایی که مش رمضون برنامه نویسی بلد نیست از شما خواسته که این برنامه رو برایش بنویسید و نتایجی رو براش به دست بیارید. توجه کنید که اگر اپلیکیشن مسیر مناسبی را برای کاربر پیدا نکند از او می خواهد که به این مهمانی نرود. # ورودی در خط اول به شما $N, M, K, Q$ داده می شود که به ترتیب تعداد شهر ها، تعداد جاده ها، تعداد شیرینی فروشی ها و تعداد در خواست های امروز است. در $M$ خط بعدی به شما وضعیت جاده ها داده می شود که $Ui$ مبدا، $Vi$ مقصد و $Ci$ میزان جریمه هستند و به ترتیب به شما داده می شوند. در $Q$ خط بعدی به شما ورودی کاربر ها داده می شود یعنی در هرکدام از این خط ها به شما دو عدد $ai$ و $bi$ داده می شود که به ترتیب مبدا و مقصد هر کاربر است. $$1 \le N \le 200$$ $$1 \le K \le 100$$ $$1 \le Q, M \le 10000$$ $$1 \le Ci \le 1000000$$ # خروجی شما باید دو عدد را در انتهای کار برای مش رمضون چاپ کنید، اول از همه تعداد کاربرانی را که بهشان پیشنهاد نکردید که به مهمانی نروند و سپس مجموع کل هزینه ای که کاربران دیگر با استفاده از اپلیکیشن شما پرداخته اند (تا مش رمضون بتونه با این داده ها از دولت پورسانت بگیره:))‌ ) ## ورودی نمونه ۱ ``` 3 3 1 3 3 1 10 1 3 10 1 2 7 3 2 2 3 1 2 ``` ## خروجی نمونه ۱ ``` 2 24 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- این روزا آریان کمی بی حوصله شده و اصلا حوصله ی خوندن صورت سوالات طولانی $codeforces$ رو نداره. برای همین هم از دوستش آرین (که همه استاد صداش می کنن) خواسته که یک سوال با صورت کوتاه به آریان بده. استاد هم سوال زیر رو به آریان به داد: یک سری رشته داریم، حالا می خواهیم طول بلند ترین مجموعه از این رشته ها رو پیدا کنیم که اگر $Si$ و $Sj$ و i > j باشه آنگاه رشته ی $i$ هم با رشته ی $j$ آغاز شود و هم با این رشته تمام شود. آرین این سوال رو بسیار کلاسیک دونست و زود راه حلش رو به استاد گفت ولی خب استاد طبق معمول مثال نقضی برای راه حل آریان داد. استاد پس از دیدن راه حل غلط آریان تصمیم گرفت که این سوال رو توی کوئرا بذاره و ببینه که چند نفر این سوال رو می زنن؟؟ # ورودی در خط صفرم به شما یک عدد $N$ داده می شود و در $N$ خط بعدی به شما یک رشته داده می شود(در خط $i$ام به شما رشته ی $Si$ داده می شود) **توجه کنید که رشته ها از حروف بزرگ انگلیسی ساخته می شوند. $$1 \le ∑|Si| \le 2000000$$ پ.ن: طول هر رشته حداقل یک است بدیهتا!! # خروجی در خروجی شما باید یک عدد خروجی بدید که همون طول بلند ترین مجموعه است. ## ورودی نمونه ۱ ``` 5 A B AA BBB AAA ``` ## خروجی نمونه ۱ ``` 3 ``` مجموعه ی مورد نظر (A, AA, AAA) هستش. ## ورودی نمونه ۲ ``` 6 A B A B A B ``` ## خروجی نمونه ۲ ``` 3 ``` توی این مثال هم باز مجموعه سه عضو داره: {A, A, A}

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- آریان عاشق شکره!! اون که توی ماه رمضان، روزه هستش و نمی تونه در طول روز شکر بخوره، تصمیم گرفته برای افطار که به خونه‌ی مش‌رمضون میره بیشترین مقدار شکر رو بخوره. مش‌رمضون $N$ تا شله زرد درست کرده که $i$امین اونا $Ai$ گرم شکر داره، ننه قمر هم امشب مهمان مش‌رمضونه ولی ننه قمر عادت نداره جایی دست خالی بره، برای همین $M$ تا شله زرد درست کرده که $i$امین اونا $Bi$ گرم شکر داره!! زمانی که ننه قمر به خونه‌ی مش رمضون میرسه، مش رمضون از آریان می خواد که شله زرد های ننه قمر رو بذاره لا به لای شله زرد های مش رمضون که توی یک صف مرتب روی میز هستن‌ (آریان می تونه شله زرد ها رو اول یا آخر صف یا حتی بین دو شله زرد دیگه بذاره). حالا یک صف $N + M$ تایی از شله زرد ها درست شده. آریان از اول صف شروع می کنه و تعدادی شله زرد رو می خوره. مش رمضون به آریان گفته که هر چند تا شله زرد که بخواد می تونه بخوره ولی نباید هیچ دو شله زرد متوالی رو بخوره... حالا آریان می خواد بدونه که حداکثر چند گرم شکر می تونه بخوره!! # ورودی در خط اول شما یک عدد $N$ رو دریافت می کنید که تعداد شله زرد‌هاییه که مش رمضون درست کرده و در $N$ خط بعدی شما $Ai$ ها رو دریافت می کنید. در خط بعدی شما عدد $M$ رو دریافت می کنید که تعداد شله زرد هاییه که ننه قمر درست کرده و در $M$ خط بعدی هم شما $Bi$ ها رو دریافت می کنید. $$1 \le N \le 3000$$ $$0 \le M \le 100$$ $$1 \le Ai, Bi \le 100000 $$ # خروجی شما باید تنها یک عدد خروجی دهید، بیشینه‌ی گرم شکری که آریان می تونه بخوره!! ## ورودی نمونه ۱ ``` 5 10 12 6 14 7 3 1 8 2 ``` ## خروجی نمونه ۱ ``` 44 ``` برای این که بیشینه‌ی شکر رو بخوره آریان شله زردهای ننه قمر رو این شکلی بین شله زرد های مش‌رمضون قرار میده. ۱۰، ۱، ۱۲، ۲، ۸، ۶، ۱۴، ۷ حالا شله زرد هایی که ۱۰، ۱۲، ۸ و ۱۴ گرم شکر دارن رو می خوره: ۱۰ +‌ ۱۲ +‌ ۸ +‌ ۱۴ = ۴۴

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آریان با کمک شما تونست از دعوا توی بانکش جلوگیری کنه و پول خوبی رو به جیب بزنه، حالا آریان با سودی که از بانکش به دست آورده، یک رستوران تاسیس کرده به نام آریوران (Ariorun). آریان برای رستورانش یک پارکینگ در نظر گرفته بوده و تا امروز پارکبانی داشت که محل پارک کردن ماشین ها رو مدیریت می کرد. آریان طبق محاسباتی که انجام داد پول زیادی رو باید به پارکبانش می داد، پس پارکبان بیچاره رو اخراج کرد و تصمیم گرفت که برنامه ی پارکبان هوشمند رو بنویسه. رستوران آریان $N$ جای پارک متوالی داره. هر بار که گروهی وارد رستوران میشوند یک عدد را وارد پارکبان می کنند، آن هم تعداد ماشین هایی است که آن گروه می خواهند پارک کنند، پارکبان هوشمند اگر به تعداد مورد نظر جای پارک متوالی خالی داشته باشد، اجازه می دهد که وارد شوند و در اولین بازه ی متوالی که بتواند به آنها جای پارک می دهد. در غیر این صورت می گوید که رستوران پر است و آریوران این مشتری ها را از دست می دهد. بازه هایی از روز آریان غضب می کنه و در یک بازه ی مشخص هر چی مشتری نشسته باشه رو می ریزه بیرون!! آریان این بازه ها رو به پارکبان هم میده تا اگر ماشینی در اون بازه ها هست، بگه خالی شده. آریان تمام اطلاعاتی که پارکبان امروز دریافت کرده را دارد، حالا از شما خواسته که برنامه ای بنویسید تا تعداد گروه هایی که رستوران از دست داده را به دست بیاورد. # ورودی در خط اول به شما $N$ و $M$ داده می شود. که به ترتیب تعداد جای پارک ها و اطلاعاتی هستند که پارکبان دریافت کرده است. هر کدام از $M$ خط بعدی دو حالت دارند ۱- حرف $A$ به همراه یک عدد طبیعی کوچک تر یا مساوی $N$ وارد می شود که تعداد ماشین هایی هستند که یک مهمان خواسته که پارک کند. ۲- حرف $L$ به همراه یک بازه از جای پارک های پر داده می شود، که به معنی خالی شدن جای پارک های این بازه است. $$1 \le N \le 500000$$ $$1 \le M \le 300000$$ # خروجی کد شما باید تنها یک عدد خروجی دهد که همان تعداد گروه هایی است که پارکبان هوشمند به داخل رستوران راه نمیدهد. ## ورودی نمونه ۱ ``` 10 4 A 6 L 2 4 A 5 A 2 ``` ## خروجی نمونه ۱ ``` 1 ``` گروه شماره ی ۳ به داخل راه داده نمی شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همون طور که احتمالا تا الان متوجه شدین، صالح موجود عجیبیه!! آریان با پول هایی که از رستورانش در آورده می خواد که کف سالن رستورانش رو رنگ کنه. سالن رستوران آریان از $N$ کاشی تشکیل شده، این کاشی ها به صورت پشت سر هم و به طور مرتب قرار گرفتن. صالح یک شرکت رنگ آمیزی راه انداخته و آریان می خواد این کار رو به شرکت صالح اینا بسپره. صالح از اون جایی که کلا آدم عجیبیه قوانین عجیبی هم برای رنگ کردن این راهرو داره. شرکت صالح اینا $M$ نوع رنگ مختلف داره. آریان هر بار می تونه یک بازه ی $K$ تایی از این راهرو رو انتخاب کنه و همین طور هم یک نوع رنگ خاص رو و بچه های صالح اینا، این بخش از راهرو رو رنگ می کنن. آریان می خواد بدونه که به چند طریق می تونه این راهرو رو رنگ بکنه به طوری که هر کاشی حداقل یکبار رنگ شده باشد. توجه کنید که ترتیب رنگ شدن راهرو برای آریان اهمیتی نداره و فقط به رنگ نهایی راهرو کار داره. به طور دقیق تر آریان دو حالت رو مجزا می دونه اگر در انتهای کار دو کاشی باشند که رنگشون با هم فرق داشته باشه. # ورودی ورودی شامل یک خط است و اعداد $N$ و $M$ و $K$ به شما به ترتیب داده می شوند. $$1 \le N, M, K \le 1000000$$ # خروجی شما باید تعداد روش های رنگ آمیزی رو به پیمانه ی 1000000007 خروجی دهید. ## ورودی نمونه ۱ ``` 3 2 2 ``` ## خروجی نمونه ۱ ``` 6 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مش‌رمضون $N$ تا نوه داره، ننه قمر هم $N$ تا نوه داره (اصلا هم جای تعجب نیست که هر دوشون $N$ تا نوه دارن:))‌ ). نوه های مش رمضون و نوه های ننه قمر امسال برای اولین بار روزه گرفتن و می خوان بازی کنن تا از گذر زمان غافل بشن و سختی روزه رو احساس نکنن. آریان یک بازی سورپرایزی برای بچه ها داره. آریان یک زمینه مختصاتی خیلی بزرگ روی زمین انداخته (بی نهایت در بی نهایت) و به هر کدوم از نوه های مش رمضون یک سنگ قرمز و به هر یکی از نوه های ننه قمر یک سنگ آبی میده. آریان از همه ی بچه ها می خواد که سنگشون رو به داخل زمین مختصاتی پرتاب کنند (نوه های مش رمضون یک تیم و نوه های ننه قمر یک تیم هستن). خب حالا برنده چه طوری مشخص میشه؟؟ آریان به یک سنگ میگه تسخیری اگر توی مثلثی از سنگ ها با رنگی دیگر باشد (روی اضلاع هم داخل محسوب می شود). هر تیم به تعداد سنگ هایی که تسخیر می کنه امتیاز می گیره، حالا می خوایم بدونیم که نتیجه ی بازی چند، چند میشه؟! # ورودی در خط اول به شما $N$ داده می شود که تعداد نوه های مش رمضون و ننه قمر است. در $N$ خط بعدی مخصات نقاطی داده میشه که نوه های مش رمضون سنگشون رو انداختن. در $N$ خط بعدی هم مختصات نقاطی داده میشه که نوه های ننه قمر سنگشون رو انداختن. $$3 \le N \le 50000$$هر کدوم از مختصات ها عددی میان $-40000$ و $40000$ می باشد. # خروجی شما باید دو عدد خروجی دهید، عدد اول امتیازی است که نوه های مش رمضون به دست آوردن و عدد دوم امتیازی است که نوه های ننه قمر به دست آوردن. ## ورودی نمونه ۱ ``` 4 0 0 0 2 2 0 2 2 1 1 1 10 -10 3 10 3 ``` ## خروجی نمونه ۱ ``` 1 2 ``` نوه های مش رمضون سنگ با مختصات (۱، ۱) را تسخیر کرده اند و نوه های ننه قمر دو سنگ با مختصات های (۲، ۰) و (۲، ۲) را تسخیر کرده اند.