+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
+ منبع: *CEOI 2018*
----------
مدتی است که زورو به فکر خرید سرور است. زورو پس از بررسی‌های بسیار $n$ سرور مناسب پیدا کرده است که سرور $i$ام $C_i$ هسته دارد که هر کدام فرکانس $F_i$ دارد. قیمت سرور $i$ام نیز $V_i$ است. لازم به ذکر است که هسته‌های یک سرور از یک‌دیگر مستقل‌اند و میتوانند کارهای متفاوتی را انجام دهند.
زورو که به فکر کسب و کار است ، با جست و جوی فراوان $m$ مشتری پیدا میکند. مشتری $i$ام حاظر است که $v_i$ واحد پول به زورو بدهد به شرطی که زورو $c_i$ هسته از سرور (های)ش را که هر کدام حداقل فرکانس $f_i$ داشته باشد را به او اجاره دهد. لازم به ذکر است که هر هسته را می‌توان به حداکثر یک نفر اجاره داد.
زورو که نمی‌خواهد این فرصت را از دست بدهد، از شما خواسته که به او کمک کنید و حداکثر سود ممکن را به او بگویید.
# ورودی
در خط اول ورودی $n$ ، تعداد سرورهای موجود برای خرید آمده است.
در هر یک از $n$ خط بعدی سه عدد $C_i$ ، $F_i$ و $V_i$ آمده است که نشان‌دهنده مشخصات سرور $i$ام است.
در خط بعدی ورودی $m$ ، تعداد مشتری های زورو آمده است.
در هر یک از $m$ خط بعدی سه عدد $c_i$ ، $f_i$ و $v_i$ آمده است که نشان دهنده ی مشخصات مشتری $i$ام است.
$$1 \le n, m \le 2\ 000$$$$1 \le C_i, c_i \le 50$$
$$1 \le F_i, f_i \le 10^9$$
$$1 \le V_i, v_i \le 10^9$$
# خروجی
تنها یک عدد چاپ کنید که برابر با بیشینه سود ممکن زورو است.
# زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:---------------------:|:----------------:|:-------------------:|
| ۱ | ۱۸ | $$n \le 15$$|
| ۲ | ۱۸ | $$m \le 15$$|
| ۳ | ۱۸ | $$n, m \le 250, C_i = c_i = 1$$|
| ۴ | ۱۸ | $$F_i = f_i = 1$$|
| ۵ | ۱۸ | $$V_i = v_i = 1$$|
| ۶ | ۱۰ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه ۱
```
4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550
```
## خروجی نمونه ۱
```
350
```
زورو سرور می‌خرد
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
برنامه‌ای بنویسید که عدد $n$ و سپس یک دنباله $n$-تایی $a_1, a_2, a_3, ..., a_n$ را از ورودی بخواند و سپس مقدار زیر را چاپ کند:
$$\sum_{1 \le l \le r \le n} f(l, r)$$
که $f(l, r)$ را این‌گونه تعریف می‌کنیم:
$$f(l, r) = \sum _{i = l} ^ r a_i$$
# ورودی
در سطر اول ورودی یک عدد $n$ آمده است و در سطر دوم $n$ عدد طبیعی آمده است که عدد $i$-ام نمایان‌گر $a_i$ است.
$$1 \le n \le 500\ 000$$
$$1 \le a_i \le 10$$
**دقت کنید که این سوال دارای زیرمسئله می‌باشد.**
# خروجی
برنامه‌ی شما باید تنها یک خروجی چاپ کند که برابر مقدار گفته شده است.
# زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت
|:------------------:|:----------:|:------------------:|
| ۱ | ۲۰ | $n \le 100$ |
| ۲ | ۳۰ | $n \le 4\ 000$ |
| ۳ | ۵۰ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه
```
3
1 2 3
```
## خروجی نمونه
```
20
```
$f(1, 1) = 1 , f(1, 2) = 3, f(1, 3) = 6, f(2, 2) = 2, f(2, 3) = 5, f(3, 3) = 3$
$\rightarrow ans = 1 + 3 + 6 + 2 + 5 + 3 = 20$
جمع همه‌ی زیربازه‌ها
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
افراد ۱ تا $n$ تیم‌بندی شده‌اند و در یک صف قرار گرفته‌اند. به یک شیوه تیم بندی یک دنباله $a_1,a_2,...,a_n$ نسبت میدهیم به این شکل که به ترتیب عناصر دنباله را میسازیم:
+ در مرحله $i$ ام اگر فرد با شماره $i$ با فرد شماره $j$ هم‌تیمی بود به شکلی که $i>j$ $a_i$ را برابر $a_j$ قرار میدهیم.
+ در غیر این صورت $a_i$ را برابر مینیمم عدد طبیعی مانند $x$ قرار میدهیم که $x$ برابر هیچ کدام از اعداد $a_1,a_2,...,a_{i-1}$ نباشد.
یک دنباله $a_1,a_2,...,a_n$ به شما داده شده است که تضمین میشود تیم‌بندی‌ای وجود داره که دنباله‌اش برابر آن شود.
تعداد تیم‌بندی‌‌هایی را بشمارید که دنباله‌هایشان از لحاظ لکسیکوگرافیکالی کمتر یا برابر دنباله $a$ باشد. چون ممکن است این عدد خیلی بزرگ باشد، باقی‌مانده آن را به $1\ 000\ 007$ حساب کنید.
# ورودی
در خط اول ورودی یک عدد $n$ داده شده است.
در خط دوم دنباله $a_1,a_2,...,a_n$ داده شده است.
$$1 \leq n \leq 10\ 000$$
# خروجی
باقی‌مانده تعداد تیم‌بندی‌های با شرایط گفته شده بر $1\ 000\ 007$ را در یک خط چاپ کنید.
# زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:---------------------:|:----------------:|:-------------------:|
| ۱ | ۳۰ | $$n \le 14$$|
| ۲ | ۲۰ | $$n \le 100$$|
| ۳ | ۲۰ | $$n \le 1\ 000$$|
| ۴ | ۳۰ | بدون محدودیت اضافی |
# مثال
## ورودی نمونه ۱
```
3
1 2 2
```
## خروجی نمونه ۱
```
4
```
دنباله‌های معتبر:
+ $1 1 1$
+ $1 1 2$
+ $1 2 1$
+ $1 2 2$
+ $1 2 3$
تیم‌بندی کج
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
شنگدباو *(shengdebao)* معلم یک مهد کودک شده است! هر کدام از بچه‌های این مهد قدرتی دارد، به طور دقیق‌تر قدرت کودک $i$ام برابر $a_i$ است.
معضلی که در بین بچه‌ها الان وجود دارد این است که می‌خواهند دو تیم تشکیل بدهند و با هم به بازی «کتک کاری» مشغول شوند! ممکن است تعدادی از بچه‌ها در این بازی شرکت نکنند اما یک نکته که خیلی مورد توجه است این است که اگر قرار باشد تعدادی از بچه ها در تیم اول و تعدادی در تیم دوم باشند جمع قدرت بچه های تیم اول و تیم دوم با هم به پیمانه ی $m$ برابر باشند.
شنگدباو به خاطر اینکه به بچه ها درس دوستی و مهربانی بدهد به آنها در حل معضلشان کمک نکرد! اکنون بچه ها پیش شما آمده‌اند و می‌خواهند تعدادی از آنها را در تیم اول و تعدادی در تیم دوم قرار دهید به طوری که جمع قدرت های دو تیم به پیمانه‌ی $m$ برابر شود. به آنها کمک کنید!
# ورودی
در اولین سطر ابتدا $n$ و سپس $m$ آمده است. که $n$ تعداد بچه ها است.
در سطر بعدی $n$ عدد داده شده است که با فاصله جدا شده است. $i$امین عدد $a_i$ است.
$$1 \le n \le 1\ 000\ 000$$
$$1 \le m \le 10 ^ 9$$
$$0 \le a_i < m$$
# خروجی
اگر روشی برای انجام این کار نبود خروجی دهید: `laelahaellallah`
در غیر اینصورت ابتدا خروجی دهید `alhamdolellah` و در سطر بعدی $n$ عدد خروجی دهید که هر کدام برابر $0$ یا $1$ یا $2$ است.
اگر $0$ بود یعنی کودک در هیج تیمی نیامده است و اگر $1$ بود یعنی در تیم اول و اگر $2$ بود یعنی در تیم دوم آمده است.
توجه کنید باید حداقل یکی از تیم‌ها خالی نباشد، یعنی تمامی اعداد خروجی نباید برابر صفر باشد. ولی ممکن است $1$ یا $2$ نداشته باشیم.
# زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:---------------------:|:----------------:|:-------------------:|
| ۱ | ۱۰ | $m \le 1\ 000$|
| ۲ | ۶ | $n \le 16$|
| ۳ | ۹ | $n \le 20$|
| ۴ | ۳۵ | $m \le 1\ 000\ 000$|
| ۵ | ۴۰ | بدون محدودیت اضافی|
# مثال
## ورودی نمونه ۱
```
4 1000
1 4 3 2
```
## خروجی نمونه ۱
```
alhamdolellah
1 0 2 1
```
## ورودی نمونه ۲
```
4 5
0 1 2 3
```
## خروجی نمونه ۲
```
alhamdolellah
2 0 1 1
```
## ورودی نمونه ۳
```
3 10000
1 10 100
```
## خروجی نمونه ۳
```
laelahaellallah
```
علی آقا؟!
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۵۱۲ مگابایت
----------
تیزی و کسری روی یک گراف همبند بازی میکنند. هر کدام از آنها روی یکی از راس های گراف قرار گرفته‌اند.
دو راس از این گراف راس های سرور نام دارند که این دو راس حتما با یک یال بهم وصلند.
تیزی و کسری یکی درمیان حرکت میکنند و ابتدا تیزی حرکت میکند. آنها در هر ثانیه میتوانند به یکی از راس های مجاور راس فعلی خود بروند اما مجبور به حرکت نیستند. قطع کردن سیم های یک سرور هم یک ثانیه طول میکشد.
هدف تیزی این است که به یک راس سرور برسد و سیم آن را قطع کند. کسری میخواهد جلوی او را بگیرد. کسری در صورتی برنده میشود که تا ابد جلوی کشیدن سیم سرور توسط تیزی را بگیرد. یا اینکه قبل از کشیده شدن سیم سرور با تیزی در یک راس باشد.
اما کسری خوابش می‌آید و میخواهد بیشتر بخوابد.
او میخواهد آنقدر بخوابد تا بعد از بیدار شدن همچنان مطمئن باشد میتواند از تیزی ببرد. بیشترین تعداد ثانیه‌ای که کسری میتواند به جای بازی کردن بخوابد را پیدا کنید.
دقت کنید که کسری در زمانی که خواب است حتی اگر با تیزی در یک راس قرار بگیرد برنده نمیشود.
# ورودی
در خط اول ورودی $n$ و $m$ به شما داده میشود که به ترتیب تعداد راس های گراف و تعداد یال های آن است.
در خط بعدی ۴ عدد $k$ و $t$ و $a$ و $b$ به شما داده میشود که $t$ شماره راس ابتدایی تیزی است و $k$ شماره راس ابتدایی کسری. $a$ و $b$ شماره راس های دو سرور هستند.
در هر یک از $m$ خط بعدی دو عدد $v$ و $u$ به شما داده میشود که نشان دهنده ی یک یال بین $v$ و $u$ است.
$$4 \leq n \leq 200\ 000$$
$$3 \leq m \leq 600\ 000$$
$$1\leq t,k,a,b,v,u \leq n$$
# خروجی
در تنها خط خروجی حداکثر زمانی که کسری میتواند بخوابد تا باز هم تیزی را ببرد بدهید. اگر کسری نمیتواند تیزی را ببرد $-1$ چاپ کنید.
# زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:---------------------:|:----------------:|:-------------------:|
| ۱ | ۳۰ | $$n \le 800, m\le 1 \ 600$$|
| ۲ | ۷۰ | بدون محدودیت اضافی|
# مثال
## ورودی نمونه ۱
```
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4
```
## خروجی نمونه ۱
```
1
```
## ورودی نمونه ۲
```
6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
```
## خروجی نمونه ۲
```
0
```
دو صفر هفت
+ محدودیت زمان: ۰.۵ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
شایان مقادیر زیادی به بهنود بدهکار است.(مقدار زیادی وجه نقد، زمین‌های شمال مکزیک و بخش قابل توجهی از نفت خاورمیانه) و به همین علت تمام تلاشش را میکند تا با او مواجه نشود.
آنها در شهری زندگی میکنند که به شکل یک گراف $n$ راسی و $m$ یالی است. شایان در ابتدا در راس $S$ است و میخواهد به راس $T$ که حمیدرضا در آنجا انتظارش را میکشد برود تا با او تنیس بازی کند(حمیدرضا خیلی اهل فوتبال نیست)
همزمان که شایان به سمت راس $T$ می‌رود، بهنود نیز که از اینکه نتوانسته طلبش را وصول کند، افسرده و پریشان شده با سرعتی برابر شایان گشتی مشخّص را با هدفی نامشخص طی میکند.(هر دو همزمان شروع به حرکت میکنند و برایشان طی کردن هر یال ۱ ثانیه زمان می‌برد) شایان کاملا مسیری که بهنود طی میکند را می‌داند، و سعی میکند گشتی را انتخاب کند که در هیچ کجای آن بهنود را نبیند٬ همچنین شایان میتواند در ۱ ثانیه در یک راس ثابت بماند و حرکت نکند یا در یک راس چند بار برود اما مسیر بهنود کاملا ساده است. (دقت کنید که شایان ممکن است بهنود را در یک راس یا در یک یال ببیند، در صورتی که هر دو همزمان در حال طی کردن آن یال باشند.)
او منطقا کوتاه‌ترین گشتی از $S$ به $T$ که شرط بالا را دارد طی میکند، اما قبل از حرکت از شما میخواهد که به او بگویید، طول این گشت چقدر است یا بگویید چنین گشتی وجود ندارد.
# ورودی
در سطر اول ورودی دو عدد $n$ و $m$ و در سطر بعد دو عدد $S$ و $T$ آمده‌است.
در $m$ سطر بعد هر خط، دو عدد $u$ و $v$ آمده است، که به معنی وجود یالی بی جهت از راس $u$ به راس $v$ می‌باشد.
در سطر بعدی عدد $k$ و در ادامه $k$ عدد آمده است که عدد $i$ام برابر با راس $i$ام مسیر بهنود است.
$$1 \le n, m \le 1\ 000\ 000$$
$$1 \le s, t, u, v, k \le n$$
$$1 \le u , v \le n$$
+ تضمین میشود گراف ساده است.
# خروجی
در تنها سطر خروجی، طول کوتاه ترین گشت با شرط گفته شده در صورت سوال را چاپ کنید. اگر چنین گشتی وجود ندارد، `-1` چاپ کنید.
# زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:---------------------:|:----------------:|:-------------------:|
| ۱ | ۳۱ | $n, m \le 2\ 000$|
| ۴ | ۶۹ | بدون محدودیت اضافی|
# ورودی نمونه
```
3 3
1 3
1 2
2 3
3 1
2
3 1
```
# خروجی نمونه
```
2
```
بدهکاری!
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
در اواسط حکومت خشایار شاه بر اسپادانا، یکی از قبایل همسایه- که از بردن نامش چشم‌پوشی می‌کنیم- تصمیم به حمله به اسپادانا گرفت. اما از آنجایی که خشایارشاه پادشاهی با کفایت بود، با کمک کیوان خیلی سریع اقدام به تشکیل سپاهی پر قدرت کرد.
در اسپادانا، $n$ سرباز با شماره‌های $1$ تا $n$ به ترتیب در یک صف قرار دارند که هوشمندی سرباز $1 \le i \le n$ برابر $a_i$ است. **هوشمندی** یک گروه از سربازها نیز برابر **میانگین هوشمندی** سربازهای آن گروه است. برای مثال هوشمندی یک گروه $3$ نفره از سربازها با هوشمندی ${1, 3, 4}$ برابر $\frac{8}{3}$ است.
از آنجایی که قبیله همسایه در $k$ گروه به اسپادانا حمله می‌کرد، خشایارشاه به کیوان دستور داده بود که سربازها را به حداقل $k$ گروه **افراز** کند. همچنین خشایارشاه دستور داده بود هر گروه از سربازها یک **زیردنباله متوالی** از سربازهای درون صف باشد.
به بیان دقیق‌تر کیوان باید سربازها را به حداقل $k$ زیردنباله متوالی افراز کند.
**اعتبار** یک گروه بندی توسط کیوان را *مینیمم هوشمندی* بین گروه‌ها تعریف می‌کنیم.
برای مثال فرض کنید دنباله $a = <1, 2, 3, 5>$ باشد، و کیوان دنباله را به $2$ زیردنباله متوالی مثل ${1, 2}$ و ${3, 5}$ افراز کند در اینصورت هوشمندی گروه‌ها برابر $\frac{3}{2}$ و $4$ میشود. درنتیجه اعتبار این گروه‌بندی $\frac{3}{2}$ است.
از آنجایی که اسپادانا در آن زمان بسیار مقتدر بود، خشایارشاه به کیوان دستور داده بود که اعتبار گروه‌بندی‌اش در بین تمام گروه‌بندی‌های ممکن بیشینه باشد.
شما می‌دانید که در آن زمان کیوان حال و روز درست و حسابی نداشته است، به او کمک کنید و بیشینه اعتبار ممکن در بین همه گروه‌بندی‌ها را بیابید.
# ورودی
در خط اول ورودی دو عدد $n, k$ آماده است.
سپس $n$ عدد $a_1, a_2, ..., a_{n}$ آمده است که میزان هوشمندی سربازها را معین میکند.
$$1 \le k \le n \le 100\ 000$$
$$0 \le a_i \le 10^{9}$$
# خروجی
در تنها خط خروجی, جواب مساله را چاپ کنید.
با توجه به اینکه جواب ممکن است اعشاری باشد، جواب شما در صورتی پذیرفته میشود که اختلاف آن با جواب بهینه کمتر از $10^{-6}$باشد.
# زیر مسئله‌ها
| زیرمسئله | نمره | محدودیت |
|:---------------------:|:----------------:|:-------------------:|
| ۱ | ۱۰ | $k \le 2$|
| ۱ | ۲۰ | $n \le 1\ 000$|
| ۲ | ۳۰ | $k \le 10$|
| ۳ | ۴۰ | بدون محدودیت اضافی|
# مثال
## ورودی نمونه ۱
```
4 2
2 1 4 3
```
## خروجی نمونه ۱
```
2.33333333333
```
## ورودی نمونه ۲
```
4 3
2 1 4 3
```
## خروجی نمونه ۲
```
2.0000000000
```
## ورودی نمونه ۳
```
10 4
13 4 7 3 1 17 5 8 7 6
```
## خروجی نمونه ۳
```
6.499999999
```
میانگین
+ محدودیت زمان: ۶ ثانیه
+ محدودیت حافظه: ۵۱۲ مگابایت
----------
شما بایستی از الگوریتم $A*$ برای حل مسئله راه‌بندان استفاده کنید.
در این مسئله، یک خودروی قرمز رنگ به همراه چند خودروی دیگر در یک پارکینگ مشابه شکل پارک شده‌اند. می‌خواهیم با جابجا کردن خودروها، برای خودروی قرمز رنگ که بین سایر خودروها گرفتار شده است، راهی باز کرده و آن را از پارکینگ خارج نماییم. همه‌ی خودروها در این پارکینگ به صورت افقی و عمودی پارک شده‌اند. از آنجایی که اکنون امکان دور زدن وجود ندارد، خودروهایی که به صورت افقی قرار دارند تنها میتوانند به چپ و راست حرکت کرده و خودروهای عمودی نیز فقط امکان بالا و پایین رفتن دارند.
هدف این است که با کمترین تعداد حرکت، خودروی قرمز رنگ را که همواره به صورت افقی و روبروی درب خروجی (که در ضلع شرقی پارکینگ قرار دارد) پارک شده است، از پارکینگ خارج نماییم.
در هر حرکت، یک خودرو میتواند در راستایی که قرار دارد به هر تعداد خانه دلخواه جابجا شود، مشروط بر اینکه با سایر خودروها و یا دیوار برخورد نکند. همچنین خارج کردن خودروهای دیگر به جز خودروی قرمز رنگ از پارکینگ مجاز نمی‌باشد.
# ورودی
ورودی شامل مشخصات پارکینگ و خودروهای پارک شده در آن به همراه موقعیت خودروی قرمز رنگ است. خط اول ورودی عدد $T$ است که تعداد پارکینگ‌ها را مشخص میکند. پس از آن مشخصات $T$ پارکینگ به صورت پشت سر هم در ورودی می‌آید. برای هر پارکینگ، در خط اول سه عدد $N$ ،$M$ و $V$ قرار دارد که به ترتیب تعداد سطرها و ستون‌های پارکینگ و تعداد خودروهای درون آن (شامل خودروی قرمز رنگ) را مشخص میکند. $V$ خط بعدی هر یک مشخصات یک خودرو را نشان می‌دهد. در هر خط، ابتدا دو عدد $R$ و $C$ قرار دارند که به ترتیب سطر و ستون قسمت بالا و سمت چپ خودرو را مشخص میکنند. در ادامه راستای خودرو با یک کاراکتر $h$ برای افقی و یا $v$ برای عمودی مشخص میشود. در انتهای خط نیز عدد $L$ طول خودرو را نشان می‌دهد.
لازم به ذکر است که خانه بالای سمت چپ در سطر ١ و ستون ١ قرار داشته و خانه پایین سمت راست در سطر $N$ و ستون $M$ قرار دارد. ضمناً اولین خط از لیست مشخصات خودروها متعلق به خودروی قرمز رنگ است. نمونه ورودی متناسب با شکل در زیر آمده است.
# خروجی
به ازای هر پارکینگ، برنامه باید کمترین تعداد حرکات که منجر به خروج خودروی قرمز رنگ از پارکینگ میشود را چاپ کند. نمونه خروجی برای شکل در زیر آمده است.
## ورودی نمونه
```
1
6 6 13
3 1 h 2
1 1 v 2
1 2 v 2
1 4 h 3
2 3 h 2
2 5 h 2
3 4 v 2
4 2 v 2
5 3 h 2
5 5 v 2
5 6 v 2
6 1 h 2
6 3 h 2
```
## خروجی نمونه
```
Test #1: 16
```
مسئله راه‌بندان
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۲۸ مگابایت
----------
برنامه‌ای بنویسید که عدد $n$ را از ورودی گرفته و دو لوزی به قطر $n$ را در کنار هم با استفاده از کاراکتر `*` (مطابق خروجی نمونه) چاپ کند.
# ورودی
در یک خط عدد فرد $n$ به شما داده میشود.
$$ 1 \le n \le 19 $$
# خروجی
لوزی‌های کنار هم را در خروجی چاپ کنید.
# مثال
## ورودی نمونه
```
5
```
## خروجی نمونه
```
* *
*** ***
**********
*** ***
* *
```
لوزی‌های ستاره‌ای
+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
فرض کنید $N$ وظیفه وجود دارد که از ۱ تا $N$ شماره‌گذاری شده‌اند. در این مسئله شما باید وظیفه‌ای که بیشترین تعداد وابستگی را دارد پیدا کنید.
یک وظیفه مانند $A$ به وظیفه دیگری مانند $B$ وابسته است در صورتی که $A$ به $B$ وابستگی مستقیم یا غیرمستقیم داشته باشد. به عنوان مثال اگر وظیفه $A$ به وظیفه $B$ وابسته است و وظیفه $B$ نیز به وظیفه‌ای مانند $C$ وابسته باشد، در این صورت وظیفه $A$ دو وابستگی خواهد داشت. یکی مستقیم و دیگری غیرمستقیم.
فرض کنید که در وابستگی‌ها دور وجود ندارد.
# ورودی
ورودی شامل مجموعه‌ای از سناریوها می‌باشد. هر سناریو با یک عدد صحیح $N$ ($1 \le N \le 1000$) شروع میشود. که تعداد وظیفه‌های آن سناریو را نشان می‌دهد و به دنبال آن $N$ خط می‌آید (هر خط برای یک وظیفه).
در خط $i$ ام از این $N$ خط، یک عدد صحیح $T$ ($0 \le T \le N-1$) می‌آید که تعداد وابستگی‌های مستقیم وظیفه شماره $i$ را نشان می‌دهد و به دنبال آن $T$ عددصحیح می‌آید که شماره وظیفه‌هایی است که وابستگی به آنها وجود دارد.
ورودی یک سناریو با $N=0$ خاتمه می‌یابد.
# خروجی
برای هر سناریو در یک خط شماره وظیفه با بیشترین وابستگی را چاپ کنید.
اگر چند وظیفه دارای بیشترین وابستگی هستند شماره وظیفه‌ای را که شماره کمتری دارد، چاپ کنید.
# مثال
## ورودی نمونه
```
3
1 2
1 3
0
4
2 2 4
0
2 2 4
0
0
```
## خروجی نمونه
```
1
1
```
بالاترین وابستگی
+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
سرانجام هری‌پاتر توانست طلسم شکست دادن دشمن بزرگ خود مالفوی را ابداع کند! هری یک جفت دستبند قدرت دایره‌ای ساخته که روی مچ دست‌های راست و چپش بسته میشود. او روی هر دستبند دنباله‌ای از حروف جادویی نوشته است که هر حرف فعال قدرت او را تقریبا به اندازه یک بید کتک‌زن افزایش می‌دهد!
با این حال یک مشکل وجود دارد. دستبندها فقط زمانی کار میکنند که زیردنباله حروف فعال شده روی هر دو دستبند یکسان باشد. برای مثال در شکل زیر یک جفت دستبند داده شده که حروف دو رشته $ababdcbcc$ و $aabdccccbd$ به عنوان حروف جادویی روی آنها قرار گرفته است که یک فعال‌سازی بهینه از این حروف به هری قدرتی به اندازه ۱۴ بید کتک‌زن می‌دهد.
روی دستبند اول حروف $babdccc$ در جهت ساعت‌گرد و روی دستبند دوم همین حروف در جهت پادساعت‌گرد فعال شده است. بطور کلی ترتیب حروف مهم است اما جهت زیر دنباله فعال روی هر دستبند (در جهت عقربه‌های ساعت یا خلاف جهت) ممکن است یکسان باشد یا نباشد. فراموش نکنید که دستبندها دایره‌ای هستند!
شما باید به هری کمک کنید که تصمیم بگیرد چه زیردنباله بهینه‌ای از حروف روی دستبندهایش را لازم است فعال کند تا بتواند مالفوی را شکست دهد.
# ورودی
فایل ورودی حداکثر شامل ۱۰۰ نمونه ورودی است. (حداکثر شامل ۵ نمونه بزرگ) هر نمونه یک خط شامل یک جفت رشته که با فاصله جدا شده اند و مربوط به همان دنباله حروف روی دستبندهای قدرت چپ و راست هری است (به ترتیب) می باشد و هر رشته تنها از حروف کوچک تشکیل خواهد شد. طول هر رشته ورودی بین $1$ تا $100$ کاراکتر است به جز در نمونه های بزرگ که طول هر رشته ورودی بین $1$ تا $1500$ کاراکتر می باشد.
# خروجی
حداکثر قدرتی که هری با فعال کردن حروف روی دستبندها می تواند برسد (بر حسب واحد بید کتک‌زن) را چاپ کنید.
# مثال
## ورودی نمونه
```
ababdcbcc aabdccccbd
harrypotter plorppothaa
potterharry plorppothaa
```
## خروجی نمونه
```
14
12
12
```
طلسم هری‌پاتر
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۱۲۸ مگابایت
----------
برنامه‌ای بنويسيد كه یک عدد صحيح را که تعداد ارقامش مشخص نيست از کاربر گرفته و هر رقم را به تعداد آن رقم چاپ کند.
# ورودی
در یک خط عدد به شما داده میشود.
طول عدد از ۱۰۰ کوچکتر است.
# خروجی
به ازای هر رقم ابتدا خود آن رقم به همراه `:` را چاپ کرده سپس به تعداد آن رقم از همان رقم چاپ کنید.
# مثال
## ورودی نمونه ۱:
```
50943
```
## خروجی نمونه ۱:
```
5: 55555
0:
9: 999999999
4: 4444
3: 333
```
عدد چاپ‌کن
+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
مادر سوکراتیس پاپاستوپولوس برای تقویت سوکرات هر روز برای او یک لیوان شیر پاستوریزه آماده میکند. سوکرات ۳ لیوان با ظرفیت‌های $A,B,C$ دارد که هر یک اعدادی در بازه ۱ تا ۲۰ هستند. مادر سوکرات هر روز لیوان با ظرفیت $C$ را پر از شیر میکند ولی از آنجا که سوکرات بازیگوش است ممکن است شیر را مدام از این لیوان به لیوان دیگر بریزد!
اما سوکرات از آنجایی که عاشق شیر است در این فرآیند انتقال شیر هیچ مقداری را بر روی زمین نمی‌ریزد و در واقع عمل ریختن شیر از لیوانی به لیوان دیگر را حتماً تا جایی که لیوان مقصد جا داشته باشد انجام می‌دهد. از طرفی از سر کنجکاوی! اگر لیوان مقصد، گنجایش بیش از لیوان مبدأ داشته باشد حتما تمام شیر را درون لیوان مقصد خالی میکند به گونه‌ای که در لیوان مبدأ شیری باقی نماند.
برنامه‌ای بنویسید که مادر سوکراتیس پاپاستوپولوس بداند با این بازیگوشی سوکرات (ریختن شیر از لیوانی به لیوان دیگر)، چه مقدار شیر میتواند در لیوان با ظرفیت $C$ پس از هر حرکت وجود داشته باشد در حالیکه لیوان با ظرفیت $A$ خالی باشد.
# ورودی
یک خط شامل سه عدد $C$ , $B$ , $A$
$$1 \le A , B , C \le 20$$
# خروجی
تمامی مقادیر ممکن شیر، در لیوان با ظرفیت $C$ در حالی که لیوان با ظرفیت $A$ خالی باشد. این مقادیر باید به صورت صعودی مرتب شده باشند.
# مثال
## ورودی نمونه ۱
```
8 9 10
```
## خروجی نمونه ۱
```
1 2 8 9 10
```
## ورودی نمونه ۲
```
2 5 10
```
## خروجی نمونه ۲
```
5 6 7 8 9 10
```
شیر
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
می‌خواهیم یک شبکه‌ی اجتماعی ایجاد کنیم که امکان افزودن و جست‌وجو کردن افراد در آن وجود داشته باشد. در این شبکه‌ی اجتماعی، اطلاعات هر شخص شامل نام، جنسیت، سن و شناسه‌ی آن شخص می‌باشد. شناسه‌ی هر شخص بین ۵ تا ۱۰ کاراکتر و شامل حروف کوچک و بزرگ الفبای انگلیسی و اعداد می‌باشد و شناسه‌ی افراد مختلف متفاوت است. دستورات این شبکه به شکل زیر هستند:
+ **Add** <username> <gender> <age> <id>
+ **Find** <id>
در دستور دوم ممکن است شناسه‌ی نوشته شده معرف یک شخص نباشد؛ در این صورت شما باید در صورت وجود، افرادی را که شناسه‌ی آنها با کاراکترهای نوشته شده شروع میشود به عنوان نتیجه‌ی جست‌وجو گزارش کنید. اگر تعداد این افراد بیشتر از ۱۰ نفر بود، فقط ۱۰ نفر اول (به ترتیب لغت‌نامه‌ای) را گزارش کنید.
# ورودی
در هر خط از ورودی برنامه، یکی دستورهای بالا وارد خواهد شد.
تعداد دستورات از ۱۰۰۰۰۰ کمتر است.
# خروجی
برای دستورهای **Add** عبارتی به شکل **User <id> added successfully** را در خروجی چاپ کنید.
برای دستورهای **Find**، نتایج به دست آمده را در خروجی چاپ کنید. برای اینکه نتایج دستورهای مختلف قابل تمایز باشند، در هر خط خروجی شماره‌ی دستور **Find** متناظر با آن را نیز چاپ کنید. همچنین اگر برای جست‌وجوی انجام شده نتیجه‌ای یافت نشد، عبارت **No user found** را در خروجی قرار دهید. برای روشن‌تر شدن خروجی‌ها به نمونه توجه کنید.
# مثال
## ورودی نمونه
Add Ali male 20 ali20ali
Add Mohammad male 21 mohammadm
Add Akbar male 30 akbar30
Find ali
Add Maryam female 20 maryam20
Find mohammad21
Add Mahtab female 13 mahtab13
Add Maziar male 40 maziarAk
Find ma
## خروجی نمونه
User ali20ali added successfully
User mohammadm added successfully
User akbar30 added successfully
1 Ali male 20 ali20ali
User maryam20 added successfully
2 No user found
User mahtab13 added successfully
User maziarAk added successfully
3 Mahtab female 13 mahtab13
3 Maryam female 20 maryam20
3 Maziar male 40 maziarAk
شبکه اجتماعی
+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
برنامه‌ای بنویسید که به ترتیب سه ورودی $a,b,c$ را دریافت کرده به طوری که $a$ عددی در مبنای $b$ بوده و $c$ مبنای عددی است که باید حساب شود: یعنی:
$$(a)_b = (x)_c$$
آنگاه اگر $x$ پالیندورم(آینه‌ای) است چاپ کند $YES$ و گرنه $NO$.
یک عدد را پالیندروم یا آینه‌ای می‌گوییم هرگاه با معکوسش برابر باشد مثلاً ۱۲۱ آینه‌ای است ولی ۱۳۲ نیست.
# ورودی
در خط اول عدد $a$ ، در خط دوم عدد $b$ و در خط سوم عدد $c$ به شما داده میشود.
$$ 1 \le a \le 10^6$$
$$2 \leq c,b \leq 10$$
# خروجی
در یک خط عبارت $YES$ یا $NO$ را چاپ کنید.
# مثال
## ورودی نمونه
```
505
6
7
```
## خروجی نمونه
```
YES
```
مبنای آینه‌ای
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۶۴ مگابایت
----------
یک مجموعه‌ی سه عضوی را فیثاغورثی می‌گویند در صورتی که سه عضو آن بتوانند اضلاع یک مثلث قائم الزاویه باشند. برنامه‌ای بنویسید که عدد $n$ را از ورودی دریافت کرده، یک سه تایی فیثاغورثی متشکل از اعداد صحیح که مجموع اعضای آن $n$ باشد در خروجی نمایش دهد. در صورتی که هیچ سه‌تایی فیثاغورثی پیدا نکرد، عبارت $Impossible$ را نمایش دهد.
# ورودی
در یک خط عدد $n$ به شما داده میشود.
$$ 1 \le n \le 90\ 000 $$
# خروجی
در تنها خط خروجی چنانچه چنین مجموعه ای یافت می‌شد، اعضایش را به ترتیب از کوچک به بزرگ چاپ کنید در غیر اینصورت عبارت $Impossible$ را چاپ کنید.
# مثال
## ورودی نمونه ۱
```
12
```
## خروجی نمونه ۱
```
3 4 5
```
## ورودی نمونه ۲
```
30
```
## خروجی نمونه ۲
```
5 12 13
```
## ورودی نمونه ۳
```
13
```
## خروجی نمونه ۳
```
Impossible
```
سه‌تایی فیثاغورثی
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
حالا که وقت فرزاد بیشتر است، او می تواند بیشتر برای پروژه وقت بگذارد. از این رو فرزاد به دانیال گفت که در روز شنبه به مکان همیشگی خود بروند و بر روی صورت پروژه کار کنند. آنها در زمان ذکر شده به محل قرار آمدند و شروع به کار بر روی صورت پروژه کردند. اما طبق معمول سر اینکه کدام یک زمین بازی را درست کنند بین آنها دعوایی پیش آمد. بلاخره پس از مشاجره های طولانی، بازی زیر را اختراع کردند:
در این بازی هر کدام از آنها یک ماتریس مربعی انتخاب میکنند. سپس دو ماتریس انتخابی را در هم ضرب کرده، در صورتی که دترمینان ماتریس حاصل فرد بود، دانیال و در غیر این صورت فرزاد باید زمین بازی را درست کند. برنامه‌ای بنویسید که سرعت آنها را در بازی بالا ببرد.
# ورودی
در اولین خط ورودی ابعاد ماتریس های ورودی و در ادامه دو ماتریس گرفته میشود.
طول ماتریس ها از ۱۰ کوچکتر است.
# خروجی
پس از انجام محاسبات، در خروجی یکی از دو کلمه ی $Farzad$ یا $Danial$ نمایش داده میشود.
# مثال
## ورودی نمونه
```
2
2 1
4 -3
-1 0
5 -2
```
## خروجی نمونه
```
Farzad
```
فرزاد بازی‌کن
+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۱۲۸ مگابایت
----------
برنامه‌ای بنویسید که عدد $n$ و سپس یک دنباله $n$-تایی $a_1, a_2, a_3, ..., a_n$ را از ورودی بخواند. سپس به برنامه‌ی شما $q$ پرسش داده میشود که هر پرسش بصورت یک عدد $r$ است و برنامه‌ی شما باید نتیجه‌ی این پرسش را چاپ کند. نتیجه‌ی پرسش $r$ برابر مقدار زیر است:
$$\sum _{i = 1} ^ r a_i \ xor\ (r - i)$$
برنامه‌تان را طوری بنویسید که پیش‌پردازش طولانی نداشته باشد و پاسخ هر پرسش را سریع بدهد؛ یعنی پیش از پرسش اول و پس از دریافت هر پرسش تا پایان خروجی دادن کمتر از ضریب ثابتی از $n$ دستور (مستقل از دیگر متغیرهای ورودی بجز $n$) انجام بشود. همچنین کل اجرای برنامه‌ی شما نباید بیش از ۲ ثانیه طول بکشد.
**راهنمایی:**
روش‌های مختلفی برای پیاده‌سازی بهینه وجود دارد؛ یکی از آنها این‌چنین است: برای هر پرسش مقدار گفته‌شده را با یک حلقه ساده بدست آورید؛ در این روش تنها کاری که برای بهینه‌سازی زمان برنامه باید بکنید این است که پس از محاسبه‌ی نتیجه‌ی یک پرسش، این نتیجه را جایی ذخیره کنید که اگر در ادامه دقیقاً همان پرسش دوباره مطرح شد، دوباره آن را محاسبه نکنید و مقداری که از قبل محاسبه شده بود را خروجی دهید.
# ورودی
در سطر اول ورودی دو عدد $n$ و $q$ آمده است و در سطر دوم $n$ عدد طبیعی آمده است که عدد $i$-ام نمایان‌گر $a_i$ است. سپس در $q$ سطر بعدی هر خط یک سوال بصورت یک عدد طبیعی آمده است که برابر $r$ است.
$$1 \le a_i \le 1\ 000\ 000$$
$$1 \le r \le n \le 10\ 000$$
$$1 \le q \le 500\ 000$$
# خروجی
در $q$ سطر هریک یک عدد چاپ کنید که پاسخ به یکی از پرسش‌های داده شده است.
# مثال
## ورودی نمونه
```
4 4
4 3 6 2
1
2
3
4
```
## خروجی نمونه
```
4
8
14
17
```
پاسخ پرسش‌ها به ترتیب:
$4\ xor\ 0 = 4$
$(4 \ xor\ 1) + (3 \ xor\ 0) = 5 + 3 = 8$
$(4 \ xor\ 2) + (3 \ xor\ 1) + (6 \ xor\ 0) = 6 + 2 + 6 = 14$
$(4 \ xor\ 3) + (3 \ xor\ 2) + (6 \ xor\ 1) + (2 \ xor\ 0) = 7 + 1 + 7 + 2 = 17$
بسی پرسش
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
برنامه‌ای بنویسید که با ورودی گرفتن عدد $n$، همه‌ی زیرمجموعه‌های مجموعه‌ی $\{ 1, 2, 3, ..., n \}$ را چاپ کند. این زیرمجموعه‌ها را به ترتیب الفبایی مرتب کنید؛ یعنی ابتدا عناصر هر زیرمجموعه را مرتب کنید و سپس به آنها مانند کلمات نگاه کنید و به ترتیبی که در لغت‌نامه می‌آیند مرتب‌شان کنید.
تلاش کنید که این کار را تنها به وسیله‌ی تابع بازگشتی انجام دهید؛ یعنی طوری پیاده‌سازی کنید که این مجموعه‌ها به همین ترتیب تولید و چاپ شوند. (به جای این که ابتدا همه را تولید کرده و سپس مرتب کنید.)
برای آشنایی با قالب خروجی دادن به نمونه‌ها توجه کنید.
# ورودی
ورودی تنها شامل یک خط است که در آن یک عدد طبیعی $n$ آمده است.
$$1 \le n \le 15$$
# خروجی
خروجی برنامه‌ی شما باید شامل $2^n$ خط باشد که در هر خط یک زیرمجموعه چاپ شود.
# مثال
## ورودی نمونه ۱
```
1
```
## خروجی نمونه ۱
```
{}
{1}
```
## ورودی نمونه ۲
```
3
```
## خروجی نمونه ۲
```
{}
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{2}
{2, 3}
{3}
```