+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی فردی بسیار کنجکاو می‌باشد. روزی لطفی به او یک فلش می‌دهد و از او می‌خواهد که فلش را تا چند روز پیش خودش نگه دارد مهدی که بسیار کنجکاو هست می‌خواهد بداند درون فلش چیست. ولی لطفی فلش را رمزگذاری کرده است و رمز آن را «عددی شش‌رقمی» گذاشته است. برای همین مهدی سعی می‌کند رمز را پیدا کند. مهدی می‌داند لطفی به رمز های تعادلی علاقه دارد برای همین یک یا چندین رمز تعادلی را تست می‌کند که ببیند آیا این اعداد می توانند جزء رمز باشد یا خیر. مهدی به رمزی تعادلی می‌گوید که **جمع سه رقم اول** با **جمع سه رقم آخر** برابر باشد. مهدی از شما می‌خواهد برای چند رمز داده‌شده، مشخص کنید هر رمز «تعادلی» هست یا نه. # ورودی خط اول ورودی شامل یک عدد صحیح $t$ که برابر با تعداد تست کیس ها می‌باشد داده می‌شود. $$1 \le t \le 1000$$در هر یک از $t$ خط بعد، **شش عدد صحیح یک‌رقمی** با فاصله داده می‌شود. $$0 \le q \le 9$$ # خروجی برای هر تست، در یک خط: اگر شرایط گفته شده رو داشته باشد عبارت **Possible** رو در خروجی نمایش دهد در غیر این صورت عبارت **Impossible** نمایش داده شود. # مثال ## ورودی نمونه ۱ ``` 5 2 1 3 1 3 2 9 7 3 8 9 4 0 4 5 2 0 7 0 0 0 0 0 0 0 5 5 7 7 6 ``` ## خروجی نمونه ۱ ``` Possible Impossible Possible Possible Impossible ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در ظرفی $n$ برگ کاهو وجود دارد که طول برگ $i$ ام، $a_i$ است. در هر مرحله شما می‌توانید یک برگ کاهو با طول $x$ را به دو برگ کاهو به طول‌های $y$ و $z$ تبدیل کنید به طوری که $y + z = x$ می‌خواهیم طوری این برگ های کاهو را تکه تکه کنیم که به ازای هر دو برگ کاهو، طول هر کدام از دوبرابر طول دیگری کم تر باشد. در واقع نباید در میان کاهوها، دو برگ کاهو به طول‌های $x$ و $y$ وجود داشته باشند که $2*x\leq y$ باشد. با توجه به برگ‌های داده شده، حداقل چند مرحله برای برقراری این شرایط لازم است؟ # ورودی در خط اول ما $t$ تست کیس داریم. $$1 \leq t \leq 10^2$$ سپس در خط اول هر تست کیس ابتدا عدد $n$ داده شده است. $$1 \leq n \leq 10^2$$ سپس $n$ عدد وارد شده که از کوچک به بزرگ مرتب شده اند و طول برگ کاهو ها می‌باشد. $$1 \leq a_i \leq 10^7$$ # خروجی برای هر تست کیس حداقل تعداد مراحل برای برقراری شرایط گفته شده را به عنوان خروجی چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 5 1 2 3 4 5 1 1033 5 600 900 1300 2000 2550 ``` ## خروجی نمونه ۱ ``` 10 0 4 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پوریا و سینا در حال رقابت بودند که بفهمند چه کسی ریاضیاتش بهتر است. متاسفانه پوریا در این رقابت شکست خورد. پوریا برای تلافی این شکست سعی کرد چالشی برای سینا آماده کند تا او را شکست دهد و اثبات کند که ریاضیات خودش بهتر است. برای همین به سینا گفت باید برنامه ای بنویسد که دو عدد $a$ , $b$ را در ورودی بگیرد و تعداد مقسوم علیه های عدد **$b! / a!$** را در خروجی چاپ کند. # ورودی در خط اول دو عدد $a$ , $b$ در ورودی به شما داده می شود. $$ 0 \leq a \leq b \leq 10^{6}$$ # خروجی در تنها سطر خروجی تعداد مقسوم علیه های عدد $b! /a!$ را در خروجی چاپ کنید. **توجه** : جواب سوال را باقی‌مانده بر یک میلیارد و هفت بگیرید. # مثال ## ورودی نمونه ۱ ``` 2 4 ``` ## خروجی نمونه ۱ ``` 6 ```

+ محدودیت زمان: 2 ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در سرزمین دوردست کوئرا آباد، پوریا به همراه دوستانش، پویا و پریا، تصمیم به تصاحب این سرزمین گرفتند. آن‌ها در ابتدا $n$ سرباز ضد کوئرایی داشتند که هر کدام در لشکر خود به تنهایی می‌جنگیدند. پوریا، پویا و پریا می‌دانستند که برای شکست دادن دشمنان، باید لشکرهای خود را قوی‌تر کنند. بنابراین، آن‌ها شروع به انجام عملیات‌هایی کردند تا لشکرها را یکی کنند. عملیات‌ها به سه نوع تقسیم می‌شدند: # عملیات نوع اول عملیات نوع اول که توسط پویا انجام می‌شد، به این صورت بود: 1 x y اگر لشکر سرباز $x$ و لشکر سرباز $y$ با هم متفاوت بودند، تمام اعضای لشکر $x$ و لشکر $y$ به یک لشکر واحد تبدیل می‌شدند. اما اگر یکسان بودند، هیچ اتفاقی نمی‌افتاد. # عملیات نوع دوم عملیات نوع دوم که توسط پریا انجام می‌شد، به شکل زیر بود: 2 x y در این عملیات، تمام اعضای لشکر سرباز $x$ و لشکر سرباز $x + 1$ به یک لشکر واحد تبدیل می‌شدند. این روند ادامه پیدا می‌کرد و اعضای لشکرهای $y - 1$ و $y$ نیز یکی می‌شدند. # عملیات نوع سوم عملیات نوع سوم که توسط پوریا انجام می‌شد، به این شکل بود: 3 x y در اینجا، پوریا از پریا و پویا می‌پرسید که آیا سربازان $x$ و $y$ در یک لشکر هستند یا خیر. حالا، آن‌ها باید با انجام این عملیات‌ها، به پیروزی در برابر دشمنان خود دست یابند و به تصاحب کوئرا آباد نزدیک‌تر شوند. # ورودی در خط اول ورودی، تعداد سربازان ضد کوئرایی $n$ و تعداد عملیات‌ها $q$ به شما داده می‌شود. $$3 \leq n \le 2 \cdot 10^5$$ $$2 \leq q \le 5 \cdot 10^5 $$ # خروجی برای هر عملیات نوع سوم، در صورت اینکه سربازان ضد کوئرایی $x$ و $y$ در یک لشکر باشند، باید YES و در غیر این صورت NO چاپ شود. # مثال ## ورودی نمونه ۱ ``` 8 6 3 2 5 1 2 5 3 2 5 2 4 7 2 1 2 3 1 7 ``` ## خروجی نمونه ۱ ``` NO YES YES ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در‬ ‫کشوری $n$ شهر‬ ‫وجود‬ ‫دارد‬ ‫که‬ ‫از‬ $1$ ‫تا‬ $n$ ‫شماره‬ ‫گذاری‬ ‫شده‌اند‪.‬‬ ‫به‬ ‫لطف‬ ‫تحقیقات‬ ‫مهدی ‫سرانجام ‬‫ساخت‬ ‫لوله‬ ‫های‬ ‫تله‬ ‫پورت‬ ‫بین‬ ‫دو‬ ‫شهر‬ ‫ممکن‬ ‫شد‪.‬‬ ‫یک‬ ‫لوله‬ ‫تله‬ ‫پورت‬ ‫دو‬ ‫شهر‬ ‫را‬ ‫به‬ صورت ‬‫یک‬ ‫طرفه‬ ‫به‬ ‫هم‬ ‫وصل‬ ‫می‌کند‬ ‫یعنی‬ ‫نمی‌توان‬ ‫از‬ ‫یک‬ ‫لوله‬ ‫تله‬ ‫پورت‬ ‫از‬ ‫شهر‬ $x$ ‫به‬ ‫شهر‬ $y$ ‫برای‬ سفر ‬‫از‬ ‫شهر‬ ‫$y$ به‬ ‫شهر‬ $x$ ‫استفاده‬ ‫کرد‬‫‪.‬ حمل‬ ‫و‬ ‫نقل‬ ‫در‬ ‫هر‬ ‫شهر‬ ‫بسیار‬ ‫توسعه‬ ‫یافته‬ ‫است‬ ‫بنابراین‬ اگر یک لوله از شهر $x$ به شهر $y$ و یک لوله از شهر $y$ به $z$ ساخته شود مردم می‌توانند از شهر $x$ به شهر $z$ سفر کنند. مهدی ‫در‬ ‫سیاست‬ ‫ملی‬ ‫نیز‬ ‫دخالت‬ ‫دارد‪.‬‬ ‫او‬ ‫حمل‬ ‫و‬ ‫نقل‬ ‫بین‬ ‫‪$m$‬‬ ‫جفت‬ ‫شهر‬ $(a_i,b_i)$ را ‫مهم‬ ‫می‌داند‪.‬‬ ‫او‬ ‫در‬ ‫حال‬ ‫برنامه‬ ‫ریزی‬ ‫برای‬ ‫ساخت‬ ‫لوله‬ ‫های‬ ‫تله‬ ‫پورت‬ ‫است‬ ‫به‬‫ طوری‬ ‫که‬ ‫برای‬ ‫هر‬ ‫جفت‬ ‫مهم‬ $(a_i,b_i)$ امکان سفر از شهر $a_i$ به شهر $b_i$ (‌ اما نه لزوما از $b_i$ به $a_i$ ) با استفاده از یک یا چند لوله وجود داشته باشد. حداقل‬ ‫تعداد‬ ‫لوله‬ های‬ ‫تله‬ های تله پورت ‬را که باید ساخته شود را پیدا کنید. تاکنون ‫هیچ‬ ‫لوله‬ ‫انتقالی‬ ‫ساخته‬ ‫نشده‬ ‫است‬ ‫و‬ ‫حمل‬ ‫و‬ ‫نقل ‬‫موثر‬ ‫دیگری‬ ‫بین‬ ‫شهرها‬ ‫وجود‬ ‫ندارد‪.‬‬ # ورودی خط اول شامل دو عدد صحیح $n$ و $m$ است که به ترتیب تعداد شهر‌ها و تعداد جفت های مهم را نشان می‌دهد. $$2 \le n \le 10^5$$ $$1 \le m \le 10^5$$ در $m$ خط بعدی جفت های مهم را توصیف می‌کند. که نشان دهنده این می‌باشد که باید از شهر $a_i$ به شهر $b_i$ سفر کرد. همچنین تضمین می شود که همه جفت‌های $(a_i,b_i)$ متمایز هستند. ‬‬ $$1 \le i \le m$$ $$1 \le a_i,b_i \le n$$ $$ a_i \neq b_i$$ # خروجی حداقل تعداد لوله‌های مورد نیاز برای انتقال از راه دور برای تحقق هدف مهدی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 5 1 2 1 3 1 4 2 3 2 4 ‬‬ ``` ## خروجی نمونه ۱ ``` 3 ``` ‫یکی ‬‫از‬ ‫روش‬ ‫های‬ ‫بهینه‬ ‫ساخت‬ ‫لوله‬ ‫این است که یک لوله از ۱ به ۲ یک لوله از ۲ به ۳ و یک لوله از ۲ به ۴ ساخته شود ## ورودی نمونه ۲ ``` 4 6 1 2 1 4 2 3 2 4 3 2 3 4 ``` ## خروجی نمونه ۲ ``` 4 ```

+ محدودیت زمان: 1 ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در یک سرزمین دور، دختری به نام یانگوم زندگی می‌کرد که به ساخت زبان‌های جدید علاقه‌مند بود. او تصمیم گرفت زبانی به اسم یانگومی بسازد که شامل $n$ کلمه با $k$ حرف مشخص باشد. اما این زبان باید ویژگی خاصی داشته باشد هیچ کلمه‌ای نباید پیشوند اولیه کلمه دیگری باشد. به این ترتیب، یانگوم باید به دقت انتخاب کند که کلمات را چگونه بسازد. همچنین هر حرفی که یانگوم انتخاب می‌کرد، هزینه‌ای داشت. برای مثال، اگر حرف اول $x$ با هزینه ۵ و حرف دوم $y$ با هزینه ۴ باشد، هزینه کلمه "$xy$" برابر با ۵ + ۴ = ۹ بود. یانگوم می‌خواست زبان یانگومی $n$ کلمه ای متشکل از $k$ حرف بسازد که هیچ دوحرفی پیشوند یکدیگر نباشد و همچنین مجموع هزینه ساخت کلمات کمترین هزینه ممکن را داشته باشد. # ورودی در سطر اول دو عدد صحیح $n$ و $k$ که به ترتیب نمایانگر تعداد کلمات و حروف است داده میشوند. که $$1 \leq n \leq 200$$ $$2 \leq k \leq 200$$ سپس در خط بعدی، هزینه‌های مربوط به هر حرف داده می‌شد. # خروجی حداقل هزینه ساخت زبان یانگومی با $n$ کلمه و $k$ حرف را محاسبه کنید و نمایش دهید. # مثال ## ورودی نمونه ۱ ``` 3 3 2 5 20 ``` ## خروجی نمونه ۱ ``` 16 ``` برای مثال بالا اگر فرض کنیم حروف به ترتیب $a, b, c$ هستند جواب مطلوب به صورت$ b,ab,aa$ که برابر ۵ + ۴ + 7 که برابر $16$ میشود.