+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در زبان ستاره‌ای کلماتی وجود دارد که به آنها پولاریس گفته میشود. کلمات پولاریس، کلماتی هستند که تمام حروف الفبای ستاره **حداقل یکبار به صورت بزرگ یا کوچک** در آن قابل مشاهده باشد. حروفی که در الفبای زبان ستاره وجود دارد از `a` تا `z` همانند زبان انگلیسی می‌باشند. مهدی به کلمات پولاریس علاقه دارد ولی از آنجایی که بد کد میزند از شما می‌خواهد برنامه‌ای بنویسید که تشخیص دهد یک کلمه پولاریس است یا خیر. # ورودی در خط اول ورودی یک کلمه از زبان ستاره به شما داده میشود. تضمین میشود همه ی حروف ورودی به صورت `a-z & A-Z` می‌باشد. بزرگ یا کوچک بودن حروف در خروجی تاثیر ندارد. تضمین می‌شود طول کلمه ورودی بیشتر از `1` و حداکثر `200` می‌باشد. # خروجی اگر کلمه ی داده شده پولاریس باشد، باید در خروجی `YES` چاپ کنید در غیر این صورت عبارت `NO` را چاپ کنید. حروف خروجی همه باید به صورت **بزرگ** باشد. # مثال ## ورودی نمونه ۱ ``` toosmallword ``` ## خروجی نمونه ۱ ``` NO ``` ## ورودی نمونه ۲ ``` TheQuickBrownFoxJumpsOverTheLazyDog ``` ## خروجی نمونه ۲ ``` YES ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- در این مسئله به شما یک رشته‌ی بزرگ از حروف کوچک انگلیسی و تعداد زیادی رشته‌های کوچک (از حروف کوچک انگلیسی و حداکثر به طول ۴ کاراکتر) داده می‌شود و از شما خواسته می‌شود که تعداد رشته‌های کوچکی که زیر رشته‌ی رشته‌اصلی هستند را بیابید. # ورودی در خط اول ورودی رشته‌ی اصلی (حداکثر به طول ۱۰۰۰۰۰۰ کاراکتر از حروف کوچک انگلیسی) وارد می‌شود. سپس در خط بعد n (تعداد رشته‎‌های کوچک) وارد می‌شود. $$1 \le n \le 1\ 000\ 000$$ سپس nتا رشته کوچک (حداکثر به طول ۴ کاراکتر) وارد می‌شوند. # خروجی خروجی تنها شامل یک عدد است که تعداد رشته‌های کوچکی که زیررشته‌ی رشته‌ی اصلی هستند را نشان می‌دهد. # مثال ## ورودی نمونه ``` abcdefghijklmnopqrstuvwxyz 10 a bc df ghij ac zy st mnop c xz ``` ## خروجی نمونه ``` 6 ``` توضیح: رشته‌های `{"a", "bc", "ghij", "st", "mnop", "c"}` زیررشته‌ی رشته‌ی اصلی هستند.

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- گالوم و فرودو در مسیر رفتن به موردور برای از بین‌بردن حلقه حوصله‌شان سررفته و می‌خواهند بازی کنند. این بازی به این‌صورت است که فرودو $n$ عدد طبیعی به گالوم می‌دهد و می‌گوید بین هر عدد و مقسوم‌علیه های آن و هرکدام از مقسوم‌علیه‌ها و مقسوم‌علیه‌هایشان و به همین‌ترتیب تا ۱، یک یال بدون‌جهت وجود دارد. دراین گراف هیچ راسی به خودش یال ندارد. حال گالوم باید تعداد دورهای موجود در گراف حاصل را بین کند. اگر گالوم درست بگوید؛ فرودو حلقه را برای مدتی به او می‌دهد. به گالوم کمک کنید تا بتواند حلقه را به‌دست آورد. # ورودی ورودی شامل دو خط می‌باشد که در خط اول عدد طبیعی $n$ و در خط دوم $n$ عدد طبیعی با فاصله از هم آمده‌اند. اعداد ورودی در خط دوم حداقل ۱ و حداکثر ۱۰۰۰ می‌باشند. $$1 \le n \le 1\ 000$$ # خروجی خروجی تنها شامل یک خط است که تعداد دورهای موجود در گراف حاصل را نشان می‌دهد. # مثال ## ورودی نمونه ۱ ``` 4 1 2 4 8 ``` ## خروجی نمونه ۱ ``` 7 ``` <details> <summary>توضیحات نمونه‌ی یک</summary>  در گراف حاصل ۷ دور وجود دارد. </details> ## ورودی نمونه ۲ ``` 3 6 4 5 ``` ## خروجی نمونه ۲ ``` 6 ``` <details> <summary>توضیحات نمونه‌ی دو</summary>  در گراف حاصل ۶ دور وجود دارد. </details>

+ محدودیت زمان: ۱۰ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در این مسئله یک گراف اصلی و یک گراف الگو به شما داده می‌شود. حال شما می‌بایست تعداد زیر گراف‌های موجود از گراف اصلی (شبیه به گراف الگو) را بیابید. + گراف‌ها رنگی و جهت‌دار هستند. + هر راس گراف شامل یک ‌‌‌شناسه یکتا و یک رنگ است. + هر یال گراف شامل یک شناسه راس مبدا و یک شناسه راس مقصد است. # ورودی 1. در خط اول ورودی ‌‌$n_1$ (تعداد راس‌های گراف اصلی) وارد می‌شود. $$1 \le n_1 \le 10\ 000$$ 2. سپس در $n_1$ خط بعدی یک رشته (شناسه راس) و $a_i$ (شماره رنگ راس‌) برای راس‌های گراف اصلی با یک فاصله از هم وارد می‌شوند. $$1 \le a_i \le 5$$ 3. سپس مقدار ‌‌$m_1$ (تعداد یال‌های گراف اصلی) وارد می‌شود. $$1 \le m_1 \le 50\ 000$$ 4. سپس در $m_1$ خط بعدی دو رشته برای شناسه‌ی راس مبدا و شناسه‌ی راس مقصد یال‌های گراف اصلی با یک فاصله از هم وارد می‌شوند. 5. در خط بعد ‌‌$n_2$ (تعداد راس‌های گراف الگو) وارد می‌شود. $$1 \le n_2 \le 5$$ 6. سپس در $n_2$ خط بعدی یک رشته (شناسه راس) و $b_i$ (شماره رنگ راس‌) برای راس‌های گراف الگو با یک فاصله از هم وارد می‌شوند. $$1 \le b_i \le 5$$ 7. سپس مقدار ‌‌$m_2$ (تعداد یال‌های گراف الگو) وارد می‌شود. $$1 \le m_2 \le 20$$ 8. سپس در $m_2$ خط بعدی دو رشته‌ی شناسه‌ی راس مبدا و شناسه‌ی راس مقصد یال‌های گراف الگو با یک فاصله از هم وارد می‌شوند. # خروجی خروجی تنها شامل یک عدد است که تعداد زیرگراف‌های موجود از گراف اصلی (شبیه به گراف الگو) را نشان می‌دهد. # مثال ## ورودی نمونه ۱ ``` 5 1 1 2 2 3 2 4 2 5 2 8 1 2 1 5 2 3 2 4 2 5 3 4 5 3 5 4 3 A 1 B 2 C 2 2 A B B C ``` ## خروجی نمونه ۱ ``` 5 ``` <details> <summary>توضیحات نمونه ۱</summary>   | |راس A|راس B|راس C| |:-------:|:---:|:---:|:---:| |زیرگراف ۱|راس ۱|راس ۲|راس ۳| |زیرگراف ۲|راس ۱|راس ۲|راس ۴| |زیرگراف ۳|راس ۱|راس ۲|راس ۵| |زیرگراف ۴|راس ۱|راس ۵|راس ۳| |زیرگراف ۵|راس ۱|راس ۵|راس ۴| </details> ## ورودی نمونه ۲ ``` 5 1 1 2 2 3 2 4 2 5 2 4 1 2 1 3 1 4 1 5 3 A 1 B 2 C 2 2 A B A C ``` ## خروجی نمونه ۲ ``` 12 ``` <details> <summary>توضیحات نمونه ۲</summary>   | |راس A|راس B|راس C| |:--------:|:---:|:---:|:---:| |زیرگراف ۱ |راس ۱|راس ۲|راس ۳| |زیرگراف ۲ |راس ۱|راس ۲|راس ۴| |زیرگراف ۳ |راس ۱|راس ۲|راس ۵| |زیرگراف ۴ |راس ۱|راس ۳|راس ۲| |زیرگراف ۵ |راس ۱|راس ۳|راس ۴| |زیرگراف ۶ |راس ۱|راس ۳|راس ۵| |زیرگراف ۷ |راس ۱|راس ۴|راس ۲| |زیرگراف ۸ |راس ۱|راس ۴|راس ۳| |زیرگراف ۹ |راس ۱|راس ۴|راس ۵| |زیرگراف ۱۰|راس ۱|راس ۵|راس ۲| |زیرگراف ۱۱|راس ۱|راس ۵|راس ۳| |زیرگراف ۱۲|راس ۱|راس ۵|راس ۴| </details> ## ورودی نمونه ۳ ``` 2 1 1 2 1 2 1 2 2 1 2 A 1 B 1 1 A B ``` ## خروجی نمونه ۳ ``` 2 ``` <details> <summary>توضیحات نمونه ۳</summary>   | |راس A|راس B| |:-------:|:---:|:---:| |زیرگراف ۱|راس ۱|راس ۲| |زیرگراف ۲|راس ۲|راس ۱| </details>

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۰ مگابایت + **در این سوال به هر بخش که پاسخ بدهید، نمرۀ همان قسمت را خواهید گرفت (توضیحات مربوط به امتیازدهی در انتهای صفحه قرار دارد)** ---------- در این سوال قصد داریم یک ماشین حساب برای ساده‌سازی عبارت‌های جبری پیاده‌سازی کنیم. این ماشین حساب ۴ عمل اصلی جمع، تفریق، ضرب و تقسیم را پشتیبانی می‌کند. + عملگر `+` : این عملگر مشابه جمع در ریاضی بوده و اگر عبارت‌های سمت چپ و سمت راست این عملگر از یک درجه باشند، ضرایب آن دو جمع می‌شوند؛ در غیر اینصورت تغییری ایجاد نمی‌شود. + عملگر `-` : این عملگر مشابه تفریق در ریاضی بوده و اگر عبارت‌های سمت چپ و سمت راست این عملگر از یک درجه باشند، ضریبِ عبارتِ سمتِ راست از ضریبِ عبارتِ سمتِ چپ کم می‌شود؛ در غیر اینصورت تغییری ایجاد نمی‌شود. + عملگر `*` : این عملگر مشابه ضرب در ریاضی بوده و ضرایب عبارت‌های سمت چپ و سمت راست را در یکدیگر ضرب می‌کند و توانِ $ x $ آن‌ها را جمع می‌کند. + عملگر `%` : این عملگر مشابه تقسیم در ریاضی بوده و ضرایب عبارت‌های سمت چپ را بر ضرایب عبارت‌های سمت راست تقسیم می‌کند و توانِ $ x $ آن‌ها را تفریق می‌کند. اولویت محاسباتی، از زیاد به کم، به ترتیب پرانتز، توان، ضرب، تقسیم، جمع و تفریق می‌باشد. برای عملگرهایی که اولویت یکسان دارند، عملگری که در سمت چپ قرار دارد اولویت بالاتری به‌دست می‌آورد. + عملگرهای جمع و تفریق دارای اولویت یکسان می‌باشند. + عملگرهای ضرب و تقسیم دارای اولویت یکسان می‌باشند. ---------- # ورودی ورودی تنها شامل یک خط است که در آن یک عبارت جبری با طول حداکثر **۱۰۰۰** داده می‌شود. + تنها متغیرِ این عبارت جبری $ x $ می‌باشد. + ضریبِ $ x $ از دامنه‌ی اعداد گویا می‌باشد و تنها به دو صورتِ کسری (مثلاً `a/b`) و صحیح (مثلاً `c`) داده می‌شود. + توانِ $ x $ از دامنه‌ی اعداد صحیح نامنفی می‌باشد و تنها به صورت صحیح (مثلاً `d`) داده می‌شود. $$ -2\ 147\ 483\ 648 \le a, b, c \le 2\ 147\ 483\ 647 $$ $$ b \ne 0 $$ $$ 0 \le d \le 2\ 147\ 483\ 647 $$ # خروجی خروجی برنامه‌ی شما باید شامل یک خط باشد که فرم‌ ساده‌شده‌ی ورودی را به ترتیبِ نزولیِ توانِ $ x $ چاپ کند. + عبارتی که ضریب صفر دارد در خروجی نشان‌داده نشود. + عبارتی که در آن $ x $ از درجه‌ی صفر باشد، فقط ضریب آن نمایش داده‌شود. مثلاً به جای `23x^0` باید `23` نمایش داده‌شود. + ضریبِ `1` نمایش داده‌نشود. مثلاً به جای `2x^3` باید `x^3` نمایش داده‌شود. + توانِ `1` نمایش داده‌نشود. مثلاً به جای `23x^1` باید `23x` نمایش داده‌شود. + ضرایب به صورتِ کسری (مثلاً `p/q`) نمایش‌داده شوند، که در آن `q` باید یک عدد طبیعی و `p` یک عدد صحیح ‌باشد و `p` بر `q` بخش‌پذیر نباشد. در صورتی که `q` برابر با عدد `1` بود، ضریب به صورت صحیح (مثلاً `p`) نمایش داده‌شود. تضمین می‌شود که `q` هیچگاه برابر با `0` نمی‌شود. + عبارت خروجی باید در ساده‌ترین شکلِ ممکن باشد. ---------- # مثال ## ورودی نمونه ۱ ``` 2+x+x^2+x^0-1x^1-x ``` ## خروجی نمونه ۱ ``` x^2-x+3 ``` <details> <summary>توضیحات نمونه ۱</summary> ابتدا جملات را به شکل زیر ساده می‌کنیم: $x^0 \rightarrow 1$ $1x^1 \rightarrow x$ عبارت زیر بدست‌می‌آید: $2+x+x^2+1-x-x$ در نهایت ضرایبِ جملاتی را که درجۀ یکسان دارند، باهم جمع می‌کنیم و پاسخ مسئله بدست‌می‌آید: $x^2-x+3$ </details> ## ورودی نمونه ۲ ``` 2+2x^4+x^2-x^2-2*(1+x^4) ``` ## خروجی نمونه ۲ ``` 0 ``` <details> <summary>توضیحات نمونه ۲</summary> ابتدا جملات را به شکل زیر ساده می‌کنیم: $2*(1+x^4) \rightarrow 2+2x^4$ عبارت زیر بدست‌می‌آید: $2+2x^4+x^2-x^2-2-2x^4$ در نهایت ضرایبِ جملاتی را که درجۀ یکسان دارند، باهم جمع می‌کنیم و پاسخ مسئله بدست‌می‌آید: $0$ </details> ## ورودی نمونه ‎۳ ``` 0+1*x+2*x^1+4/4 ``` ## خروجی نمونه ۳ ``` 3x+1 ``` ## ورودی نمونه ‎۴ ``` (2+4*x^3+6*x^2)%(3*x^2+1+2*x^3) ``` ## خروجی نمونه ۴ ``` 2 ``` ## ورودی نمونه ‎۵ ``` (x^3+5x^2+x^1)%(2x+1) ``` ## خروجی نمونه ۵ ``` 1/2x^2+9/4x-5/8 ``` ## امتیاز‌دهی + برای پیاده‌سازی درست جمع و تفریق، **۷۰** امتیاز دریافت خواهیدکرد. + برای پیاده‌سازی درست ضرب و تقسیم، **۴۰** امتیاز دریافت خواهیدکرد. + برای پشتیبانی ضرایب ورودی سوال از دامنه اعداد گویا، ‍‍**۴۰** امتیاز دریافت خواهیدکرد. + برای پشتیبانی درست جمع، تفریق و ضرب از پرانتز **۸۰** امتیاز دریافت خواهیدکرد. + برای پشتیبانی درست تقسیم از پرانتز زمانی که عبارت سمت چپ بر عبارت سمت راست بخش پذیر باشد، **۵۰** امتیاز دریافت خواهیدکرد. + برای پشتیبانی درست تقسیم از پرانتز در تمام حالات، **۱۲۰** امتیاز دریافت خواهیدکرد.