+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
به شما عدد صحیح و مثبت $n$ داده می‌شود. از شما می‌خواهیم یک جدول $n \times (2n-1)$ مانند نمونه‌ها با کاراکترهای `.` و `D` بکشید به طوری که لوگو $\Delta$ را نشان دهد.
# ورودی
در تنها سطر ورودی، عدد صحیح و مثبت $n$ داده می‌شود.
$$3 \leq n \leq 20$$
# خروجی
در $n$ سطر، $2n - 1$ کاراکتر را بدون فاصله، درست مطابق نمونه‌ها چاپ کنید.
# مثال‌ها
## ورودی نمونه ۱
```
3
````
## خروجی نمونه ۱
```
..D..
.D.D.
D.D.D
````
## ورودی نمونه ۲
```
8
````
## خروجی نمونه ۲
```
.......D.......
......D.D......
.....D...D.....
....D.....D....
...D.......D...
..D.........D..
.D...........D.
D.D.D.D.D.D.D.D
````
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
در یک کافی‌نت $n$ کامپیوتر در یک ردیف، کنار هم قرار گرفته‌اند. کامپیوترها از $1$ تا $n$ به ترتیب شماره‌گذاری شده‌اند.
در ابتدای روز همه‌ی کامپیوترها خالی است. در یک روز $m$ گروه به ترتیب در زمان‌های مختلف به این کافی‌نت می‌آیند. هر گروه دو عدد $s$ و $\ell$ ارائه می‌دهد. یعنی این گروه شامل یک جمع $\ell$ نفره است و می‌خواهند پشت $\ell$ کامپیوتر متوالی با شماره‌های بیشتر یا مساوی $s$ بنشینند.
حال از شما می‌خواهیم که این سیستم را مدیریت کنید. یعنی این $\ell$ نفر را پشت کامپیوترهای با شماره‌های متوالی و بیشتر یا مساوی $s$ قرار دهید. اگر چند بازه برای نشستن این گروه وجود داشت، آن‌ها را روی بازه‌ای با کمترین شماره قرار دهید. اگر انجام چنین کاری ممکن نبود، به آن‌ها «نه» بگویید تا کافی‌نت را ترک کنند.
برای بهتر متوجه شدن خواسته‌ی سوال به نمونه‌ها مراجعه کنید.
# ورودی
در سطر اول ورودی، به ترتیب دو عدد صحیح و مثبت $n$ و $m$ که با یک فاصله از هم جدا شده‌اند، داده می‌شود.
$$1 \leq n, m \leq 200$$
در $m$ سطر بعدی، در هر سطر به ترتیب دو عدد صحیح $s$ و $\ell$ که با یک فاصله از هم جدا شده‌اند داده می‌شود.
$$1 \leq s, \ell \leq n$$
# خروجی
در $m$ سطر، بعد از درخواست، وضعیت مشغول بودن یا نبودن کامپیوترها را بعد از نشستن آن گروه به صورت یک رشته از `0` (خالی) و `1` (پر) چاپ کنید.
## ورودی نمونه ۱
```
6 5
2 3
1 3
1 2
3 1
1 2
````
## خروجی نمونه ۱
```
011100
011100
011111
011111
011111
````
+ گروه اول، شامل ۳ نفر است و می‌خواهند پشت ۳ کامپیوتر با شماره‌های بیشتر یا مساوی ۲ کنار هم بنشینند. چون همه‌ی کامپیوترها خالی است، اولین بازه‌ی ممکن برای آن‌ها کامپیوترهای ۲، ۳ و ۴ می‌نشینند.
+ گروه دوم، شامل ۳ نفر است و می‌خواهند پشت ۳ کامپیوتر با شماره‌های بیشتر یا مساوی ۱ کنار هم بنشینند. با اینکه ۳ کامپیوتر خالی وجود دارد ولی چون این ۳ کامپیوتر در یک بازه‌ی متوالی نیست، پس آن‌ها از کافی‌نت خارج می‌شوند.
+ گروه سوم، شامل ۲ نفر است و می‌خواهند پشت ۲ کامپیوتر با شماره‌های بیشتر یا مساوی ۱ بنشینند. تنها بازه‌ی ممکن برای آن‌ها کامپیوترهای ۵ و ۶ است.
+ گروه چهارم، شامل ۱ نفر است و می‌خواهد پشت کامپیوتر با شماره‌ی بیشتر یا مساوی ۳ بنشیند، ولی هیچ کامپیوتری با این شماره، خالی نیست. پس او از کافی‌نت خارج می‌شود.
+ گروه پنجم، شامل ۲ نفر است و می‌خواند پشت ۲ کامپیوتر با شماره‌های بیشتر یا مساوی ۱ بنشینند ولی ۲ کامپیوتر خالی در کافی‌نت وجود ندارد، پس آن‌ها از کافی‌نت خارج می‌شوند.
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
به شما عدد صحیح و مثبت $n$ داده می‌شود. از شما می‌خواهیم بسط دو جمله‌ای $(x + y)^n$ را به‌صورت نمادین بنویسید.
توجه کنید باید جملات با `+` از هم جدا شوند، جمله‌ی $i$ باید به ترتیب حاوی ضریب، $x^{n-i}$ و $y^i$ باشد. ($0 \leq i \leq n$) برای نمایش توان از `^` کنید. اگر مقدار توان حاوی بیش از یک رقم بود، آن را داخل `{}` قرار می‌دهیم. ضرایب و توان‌های `1` را نمی‌نویسیم.
برای بهتر متوجه شدن شیوه‌ی نمایش به نمونه‌ها در پایین مراجعه کنید.
<details class="blue">
<summary>
**راهنمایی برای محاسبه‌ی ضریب‌ها**
</summary>
----------
در باز شده‌ی $(x + y)^n$ جملات به صورت $x^i y^{n-i}$ خواهد بود، ضریب این جمله را با $\binom{n}{i}$ نشان می‌دهند.
رابطه بازگشتی زیر مقدار آن را بدست می‌آورد.
$$
\binom{n}{i} = \begin{cases}
\binom{n - 1}{i} + \binom{n - 1}{i - 1} & 1 \leq i \leq n - 1 \\
1 & \text{o.w.} \\
\end{cases}
$$
در گذشته از مثلث خیام-پاسکال برای پیدا کردن این ضرایب استفاده می‌کردند. چند سطر اول مثلث خیام به صورت زیر است:
\[
\begin{array}{cccccccccccc}
& & & & & 1 \\
& & & & 1 & & 1 \\
& & & 1 & & 2 & & 1 \\
& & 1 & & 3 & & 3 & & 1 \\
& 1 & & 4 & & 6 & & 4 & & 1 \\
1 & & 5 & & 10 & & 10 & & 5 & & 1 \\
& & & & & \cdots \\
\end{array}
\]
در این مثلث، عدد هر سطر از جمع دو عدد بالای سرش بدست می‌آید. در واقع می‌توان $\binom{n}{i}$ را هم در مثلث خیام نوشت و به همین ترتیب آن را محاسبه کرد.
\[
\begin{array}{cccccccccccc}
& & & & & \binom{0}{0} \\
& & & & \binom{1}{0} & & \binom{1}{1} \\
& & & \binom{2}{0} & & \binom{2}{1} & & \binom{2}{2} \\
& & \binom{3}{0} & & \binom{3}{1} & & \binom{3}{2} & & \binom{3}{3} \\
& \binom{4}{0} & & \binom{4}{1} & & \binom{4}{2} & & \binom{4}{3} & & \binom{4}{4} \\
\binom{5}{0} & & \binom{5}{1} & & \binom{5}{2} & & \binom{5}{3} & & \binom{5}{4} & & \binom{5}{5} \\
& & & & & \cdots \\
\end{array}
\]
</details>
# ورودی
در تنها سطر ورودی، عدد صحیح و مثبت $n$ داده می‌شود.
$$1 \leq n \leq 20$$
# خروجی
در یک سطر، بدون فاصله، باز شده‌ی عبارت $(x + y)^n$ را درست مثل نمونه‌ها چاپ کنید.
# مثال‌ها
## ورودی نمونه ۱
```
1
````
## خروجی نمونه ۱
```
x+y
````
## ورودی نمونه ۲
```
2
````
## خروجی نمونه ۲
```
x^2+2xy+y^2
````
## ورودی نمونه ۳
```
10
````
## خروجی نمونه ۳
```
x^{10}+10x^9y+45x^8y^2+120x^7y^3+210x^6y^4+252x^5y^5+210x^4y^6+120x^3y^7+45x^2y^8+10xy^9+y^{10}
````
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
در یک شهر نامتناهی خانه وجود دارد. نقشه‌ی این شهر به صورت خط‌های موازی با محورهای $x$ و $y$ صحیح در صفحه است. (مانند شکل) خانه‌های این شهر روی تقاطع‌ها قرار دارند.
شهرداری با الگویی که در تصویر زیر می‌بینید از مبدا مختصات شروع کرده و خانه‌ها را پلاک گذاری کرده است.
به شما مختصات یک خانه داده می‌شود و از شما می‌خواهیم پلاک آن خانه را پیدا کنید.
# ورودی
در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد تست‌ها را نشان می‌دهد.
$$1 \leq t \leq 10 \, 000$$
در تنها سطر هر تست، دو عدد صحیح $x$ و $y$ که به یک فاصله از هم جدا شده‌اند، داده می‌شود که مختصات یک خانه را نشان می‌دهد.
$$-100 \leq x, y \leq 100$$
# خروجی
برای هر تست، در تنها یک سطر، شماره‌ی پلاک آن خانه را چاپ کنید.
# مثال
## ورودی نمونه ۱
```
5
0 0
0 6
-3 4
3 -2
-2 1
````
## خروجی نمونه ۱
```
1
62
111
49
24
````
+ محدودیت زمان: ۱ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
از شما می‌خواهیم، قسمتی از سایت برای ارائه فیلم‌های سینمایی را طراحی کنیم. قرار است تعدادی فیلم به سایت اضافه شود، هر بازیگر یک پروفایل دارد که به فیلم‌هایی که در آن بازی کرده را نشان می‌دهد. هر فیلم هم یک پروفایل دارد که جزئیات آن مثل اسم، سال انتشار، کیفیت فیلم و لیست بازیگران آن را نشان می‌دهد.
ساختار دستورها به این صورت است که ابتدا بازیگرها و فیلم‌ها روی سایت تعریف می‌شوند، سپس در دستورهایی به شما گفته می‌شود که این بازیگر در این فیلم بازی کرده است و شما باید این مورد را ثبت کنید. همچنین ممکن است پروفایل یک بازیگر یا فیلم از سایت حذف شود و شما نباید دیگر آن‌ها را نشان دهید.
فیلم‌ها باید قابلیت دسته بندی شدن داشته بر اساس ویژگی‌هایشان داشته باشند.
# دستورها
<details class="blue">
<summary>
**دستور `ADD-MOVIE`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
ADD-MOVIE <title> <date> <quality>
```
یعنی فیلمی با نام `<title>`، محصول سال `<date>` با کیفیت `<quality>` روی سایت آپلود شده است.
رشتهی `<title>` باید حداکثر ۲۰ کاراکتر باشد. رشتهی `<date>` باید یک عدد صحیح بین `1888` تا `2024` باشد. رشتهی `<quality>` باید یکی از مقادیر `720p`، `1080p` یا `4K` باشد.
بعد از اضافه شدن هر فیلم باید یک عدد نسبت دهید که به آن `<movie-id>` می‌گوییم. برای هر فیلم، این عدد برابر تعداد فیلم‌هایی است که قبل از این فیلم با دستور `ADD-MOVIES` با موفقیت اضافه شده‌اند. (مهم نیست اگر بعداً پاک شده باشند.)
یعنی اولین فیلم که بدون خطا اضافه می‌شود، `<movie-id>` آن برابر ۰، دومین فیلم ۱، سومین فیلم ۲ و... خواهد بود.
+ اگر رشتهی `<title>` قابل قبول نبود، خطای `invalid title` را چاپ کنید.
+ اگر رشتهی `<date>` قابل قبول نبود، خطای `invalid date` را چاپ کنید.
+ اگر رشتهی `<quality>` قابل قبول نبود، خطای `invalid quality` را چاپ کنید.
+ در صورتی که هیچکدام از خطاهای بالا پیش نیامد، پیام `added successfully <movie-id>` را چاپ کنید، که به‌جای `<movie-id>` مقدار آن را قرار می‌دهید.
</details>
<details class="blue">
<summary>
**دستور `REM-MOVIE`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
REM-MOVIE <movie-id>
```
این دستور یعنی می‌خواهیم فیلم `<movie-id>` از سایت حذف شود.
+ اگر فیلمی با این `<movie-id>` اکنون روی سایت وجود ندارد، خطای `invalid movie id` را چاپ کنید.
+ در صورتی که خطای بالا پیش نیامد، پیام `removed successfully <movie-id>` را چاپ کنید، که به‌جای `<movie-id>` مقدار آن را قرار می‌دهید.
</details>
<details class="blue">
<summary>
**دستور `ADD-CAST`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
ADD-CAST <name>
```
این دستور یعنی می‌خواهیم بازیگری با نام `<name>` را به سایت اضافه کنیم.
رشتهی `<name>` باید حداکثر ۲۰ کاراکتر باشد و فقط شامل حروف بزرگ و کوچک انگلیسی باشد.
بعد از اضافه شدن هر بازیگر باید یک عدد نسبت دهید که به آن `<cast-id>` می‌گوییم. مشابه `<movie-id>`، برای هر بازیگر، این عدد برابر تعداد بازیگرهایی است که قبل از این بازیگر با این دستور با موفقیت اضافه شده‌اند. (مهم نیست اگر بعداً پاک شده باشند.)
+ اگر رشتهی `<name>` قابل قبول نبود، خطای `invalid name` را چاپ کنید.
+ در صورتی که هیچکدام از خطاهای بالا پیش نیامد، پیام `added successfully <cast-id>` را چاپ کنید، که به‌جای `<cast-id>` مقدار آن را قرار می‌دهید.
</details>
<details class="blue">
<summary>
**دستور `REM-CAST`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
REM-CAST <cast-id>
```
این دستور یعنی می‌خواهیم بازیگری با نام `<cast-id>` را از سایت حذف کنیم.
+ اگر بازیگری با این `<cast-id>` اکنون روی سایت وجود ندارد، خطای `invalid cast id` را چاپ کنید.
+ در صورتی که خطای بالا پیش نیامد، پیام `removed successfully <cast-id>` را چاپ کنید، که به‌جای `<cast-id>` مقدار آن را قرار می‌دهید.
</details>
<details class="blue">
<summary>
**دستور `SHOW-MOVIE`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
SHOW-MOVIE <movie-id>
```
در این دستور به شما یک `<movie-id>` داده می‌شود و از شما می‌خواهیم در فرمت زیر مشخصات این فیلم را چاپ کنید:
```
{title:"title", date:"date", quality:"quality", casts:["cast-id-1", "cast-id-2", ...]}
```
که در داخل `"`، مقدارهای `title`، `date`، `quality` قرار می‌گیرد. توجه کنید `cast-id`ها باید به ترتیب از کوچک به بزرگ باشند.
اگر فیلمی با این `<movie-id>` وجود ندارد. خطای `invalid movie id` را چاپ کنید.
</details>
<details class="blue">
<summary>
**دستور `SHOW-CAST`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
SHOW-CAST <cast-id>
```
در این دستور به شما یک `<cast-id>` داده می‌شود و از شما می‌خواهیم در فرمت زیر مشخصات این بازیگر را چاپ کنید:
```
{name:"name", movies:["movie-id-1", "movie-id-2", ...]}
```
که در داخل `"`، مقدار `name` قرار می‌گیرد. توجه کنید `movie-id`ها باید به ترتیب از کوچک به بزرگ باشند.
اگر بازیگری با این `<cast-id>` وجود ندارد. خطای `invalid cast id` را چاپ کنید.
</details>
<details class="blue">
<summary>
**دستور `LINK-CAST-TO-MOVIE`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
LINK-CAST-TO-MOVIE <cast-id> <movie-id>
```
این دستور یعنی بازیگر با شماره‌ی `<cast-id>` در فیلم `<movie-id>` حضور داشته و باید این دو را به هم متصل کنید.
+ اگر بازیگری با این `<cast-id>` اکنون روی سایت وجود ندارد، خطای `invalid cast id` را چاپ کنید.
+ اگر فیلمی با این `<movie-id>` اکنون روی سایت وجود ندارد، خطای `invalid movie id` را چاپ کنید.
+ اگر قبلاً این بازیگر به این فیلم اضافه متصل شده بود خطای `already linked` را چاپ کنید.
+ در صورتی که هیچ کدام از خطاهای بالا پیش نیامد، پیام `successfully linked <cast-id> to <movie-id>` را چاپ کنید، که به‌جای `<movie-id>` و `<cast-id>` مقدار آن را قرار می‌دهید.
</details>
<details class="blue">
<summary>
**دستور `FILTER-MOVIES-BY-TITLE`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
FILTER-MOVIES-BY-TITLE <pattern>
```
در این دستور باید `movie-id` تمام فیلم‌هایی که عنوان آن‌ها با `<pattern>` شروع می‌شود را به ترتیب صعودی که داخل `[]` قرار دارند و با `,` از هم جدا شده‌اند چاپ کنید. (دقیقاً مشابه نمونه‌ها)
</details>
<details class="blue">
<summary>
**دستور `FILTER-MOVIES-BY-DATE`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
FILTER-MOVIES-BY-DATE <ineq> <n>
```
در این دستور باید `movie-id` تمام فیلم‌هایی که تاریخ انتشار آن‌ها با `<date-pattern>` سازگار است را به ترتیب صعودی که داخل `[]` قرار دارند و با `,` از هم جدا شده‌اند چاپ کنید. (دقیقاً مشابه نمونه‌ها)
مقدار `<ineq> <n>` یکی از حالت‌های`>= n`، `> n` ،`= n`، `< n` یا `<= n` را دارد که به‌جای `n` یک عدد صحیح قرار می‌گیرد و شما باید همه‌ی فیلم‌هایی که `data` آن‌ها در سمت چپ این رابطه قرار می‌گیرد و حاصل درست می‌شود را چاپ کنید.
</details>
<details class="blue">
<summary>
**دستور `FILTER-MOVIES-BY-QUALITY`**
</summary>
----------
فرمت کلی دستور به صورت زیر است:
```
FILTER-MOVIES-BY-QUALITY <pattern>
```
در این دستور باید `movie-id` تمام فیلم‌هایی که کیفیت آن برابر `<pattern>` است را به ترتیب صعودی که داخل `[]` قرار دارند و با `,` از هم جدا شده‌اند چاپ کنید. (دقیقاً مشابه نمونه‌ها)
</details>
# ورودی
در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد دستورها را نشان می‌دهد.
$$1 \leq n \leq 3000$$
در $n$ سطر بعدی، در هر سطر یک دستور مطابق توضیحات سوال داده می‌شود.
# خروجی
در $n$ سطر و در هر سطر، خروجی متناسب با هر دستور را چاپ کنید.
# مثال‌ها
## ورودی نمونه ۱
```
14
ADD-MOVIE Hezarpa 2018 1080p
ADD-MOVIE Dracula 2016 720p
ADD-CAST RezaAttaran
ADD-CAST SiamakAnsari
ADD-CAST JavadEzati
LINK-CAST-TO-MOVIE 2 0
LINK-CAST-TO-MOVIE 1 1
LINK-CAST-TO-MOVIE 0 0
LINK-CAST-TO-MOVIE 0 1
SHOW-CAST 0
SHOW-CAST 1
SHOW-CAST 2
SHOW-MOVIE 0
SHOW-MOVIE 1
````
## خروجی نمونه ۱
```
added successfully 0
added successfully 1
added successfully 0
added successfully 1
added successfully 2
successfully linked 2 to 0
successfully linked 1 to 1
successfully linked 0 to 0
successfully linked 0 to 1
{name:"RezaAttaran", movies:[0, 1]}
{name:"SiamakAnsari", movies:[1]}
{name:"JavadEzati", movies:[0]}
{title:"Hezarpa", date:"2018", quality:"1080p", casts:[0, 2]}
{title:"Dracula", date:"2016", quality:"720p", casts:[0, 1]}
````
## ورودی نمونه ۲
```
23
ADD-MOVIE Hezarpa 2018 1080p
ADD-MOVIE Dracula 2016 720p
ADD-MOVIE The_Shawshank_Redemption 1994 1080p
ADD-MOVIE The_Godfather 1972 720p
ADD-MOVIE Interstellar 2014 4K
ADD-CAST Tom_Hanks
ADD-CAST Leonardo_DiCaprio
ADD-CAST Brad_Pitt
ADD-CAST InvalidCastNameWithMoreThan20
REM-CAST 3
REM-MOVIE 4
LINK-CAST-TO-MOVIE 0 0
LINK-CAST-TO-MOVIE 1 1
LINK-CAST-TO-MOVIE 2 0
SHOW-MOVIE 0
SHOW-MOVIE 1
SHOW-CAST 0
SHOW-CAST 1
SHOW-CAST 2
SHOW-CAST 3
FILTER-MOVIES-BY-TITLE The_
FILTER-MOVIES-BY-DATE > 2000
FILTER-MOVIES-BY-QUALITY 1080p
````
## خروجی نمونه ۲
```
added successfully 0
added successfully 1
invalid title
added successfully 2
added successfully 3
invalid name
invalid name
invalid name
invalid name
invalid cast id
invalid movie id
invalid cast id
invalid cast id
invalid cast id
{title:"Hezarpa", date:"2018", quality:"1080p", casts:[]}
{title:"Dracula", date:"2016", quality:"720p", casts:[]}
invalid cast id
invalid cast id
invalid cast id
invalid cast id
[2]
[0, 1, 3]
[0]
````