خانه‌ی دوست

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

ببعی قصد دارد سری به فامیل و خانواده اش در دور بزند. اما متأسفانه، دوری ها از پلاک برای آدرس دادن استفاده نمی‌کنند. به جای آن، اهالی مساحت خانه ی خود را به سایرین اعلام می‌کنند که ظاهراً یکتا است. ببعی که از مشکلات سفر دور آگاهی دارد از گاوی می‌خواهد که به او در رسیدن به خانه‌ی فامیل کمک کند. گاوی هم طی یک تماس تلفنی، دیوی را از حضور ببعی مطلع می کند و از او می‌خواهد در محاسبه‌ی مساحت خانه ها به ببعی کمک کند. ببعی پس از ورود به دور، دیوی را یافته و با هم به جستن خانه روی می‌آورند! روش آن‌ها به این صورت است که ببعی یک خانه را به دیوی نشان می‌دهد و دیوی با نگاهی موشکافانه اندازه‌ی یکی از اضلاع خانه را به ببعی اعلام می‌کند. خوشبختانه، همه‌ی خانه ها به شکل مربع هستند. قرار است به ببعی در محاسبه‌ی مساحت خانه‌ها کمک کنیم. به این منظور قرار است برنامه ای بنویسیم که این کار را برای ببعی انجام دهد.

ورودی🔗

در خط اول ورودی، عدد طبیعی $n$ (طول ضلع خانه) آمده است. $1 \leq n \leq 100$

خروجی🔗

در تنها خط خروجی، مساحت خانه را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- سینا با شروع تعطیلات تابستانی سال دوم دبستان قصد دارد ماجراجویی کند. او با تلاش بسیار فراوان، پورتال گان «ریک سانچز» را پیدا می‌کند. او با سفر به دنیاهای مختلف، با سرزمینی جالب آشنا می‌شود. هیولاهای ساکن در این سرزمین، برای نمایش اعداد از انگشتان دست‌های خود کمک می‌گیرند. آن‌ها برای نمایش عدد صفر، تمام انگشت‌های خود را بسته نگه می‌دارند و برای نمایش اعداد بزرگ‌تر از صفر، با شروع از صفر و انگشت‌های بسته، به ازای هر واحد افزایش، یکی از انگشت‌های خود را باز می‌کنند. برای مثال برای نمایش عدد ٣ ،ابتدا یک انگشت را باز کرده تا عدد یک را نمایش دهند و سپس یک انگشت دیͽر را باز کرده تا عدد دو را نمایش دهند و در انتها انگشت سوم را باز کرده تا عدد سه را نمایش دهند. در واقع در انتها سه انگشت خود را باز کرده‌اند. در هنگام شمارش، اگر به حالتی برسند که تمام انگشت هایشان باز بوده و هم چنان باید عدد بزرگ تری را بشمارند، به اندازه ی تعداد انگشتان خود از عدد کم نموده و انگشتان خود را کامل می بندند. سپس از ابتدا شروع به شمارش می کنند. برای مثال اگر تعداد کل انگشتان هیولاها سه باشد، عدد سه را با همان سه انگشت نشان می‌دهند، ولی برای نمایش عدد چهار بعد از اینکه سه انگشت خود را باز کرده اند، تمام آن ها را می بندند و سپس یک انگشت را باز می کنند. در واقع در صورتی که هیولاها سه انگشت داشته باشند، عدد چهار را با یک انگشت نمایش می دهند. به هنگام جمع نمودن دو عدد نیز، هیولا های این سرزمین ابتدا با انگشت های خود عدد اول را نمایش داده و سپس عدد دوم را به وسیله انگشتان به عدد اول اضافه می کنند. سینا که تعداد دست و انگشتانش همانند هیولا ها نیست، نمی تواند همانند آن ها جمع اعداد را محاسبه کند. به سینا کمک کنید با دانستن تعداد دست ها و انگشت های یک هیولا، جمع دو عدد را محاسبه کند. # ورودی در خط اول تعداد انگشتان یک دست، در خط دوم تعداد دست‌ها و در خطوط سوم و چهارم دو عددی که باید با یک دیگر جمع شوند آمده‌اند. تمامی اعداد ورودی بزرگ‌تر یا مساوی صفر و کوچک‌تر از $10^4$ هستند. مجموع تعداد انگشتان هیولاها بزرگ‌تر از صفر است. # خروجی در تنها خط خروجی، عدد نمایش داده شده با دست هیولاها (تعداد انگشت‌های باز) پس از عملیات جمع را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 4 37 27 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 3 2 3 3 ``` ## خروجی نمونه ۲ ``` 6 ``` ## ورودی نمونه ۳ ``` 4 5 0 0 ``` ## خروجی نمونه ۳ ``` 0 ```

جمع باستانی

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

سینا با شروع تعطیلات تابستانی سال دوم دبستان قصد دارد ماجراجویی کند. او با تلاش بسیار فراوان، پورتال گان «ریک سانچز» را پیدا می‌کند. او با سفر به دنیاهای مختلف، با سرزمینی جالب آشنا می‌شود. هیولاهای ساکن در این سرزمین، برای نمایش اعداد از انگشتان دست‌های خود کمک می‌گیرند. آن‌ها برای نمایش عدد صفر، تمام انگشت‌های خود را بسته نگه می‌دارند و برای نمایش اعداد بزرگ‌تر از صفر، با شروع از صفر و انگشت‌های بسته، به ازای هر واحد افزایش، یکی از انگشت‌های خود را باز می‌کنند. برای مثال برای نمایش عدد ٣ ،ابتدا یک انگشت را باز کرده تا عدد یک را نمایش دهند و سپس یک انگشت دیͽر را باز کرده تا عدد دو را نمایش دهند و در انتها انگشت سوم را باز کرده تا عدد سه را نمایش دهند. در واقع در انتها سه انگشت خود را باز کرده‌اند.

در هنگام شمارش، اگر به حالتی برسند که تمام انگشت هایشان باز بوده و هم چنان باید عدد بزرگ تری را بشمارند، به اندازه ی تعداد انگشتان خود از عدد کم نموده و انگشتان خود را کامل می بندند. سپس از ابتدا شروع به شمارش می کنند. برای مثال اگر تعداد کل انگشتان هیولاها سه باشد، عدد سه را با همان سه انگشت نشان می‌دهند، ولی برای نمایش عدد چهار بعد از اینکه سه انگشت خود را باز کرده اند، تمام آن ها را می بندند و سپس یک انگشت را باز می کنند. در واقع در صورتی که هیولاها سه انگشت داشته باشند، عدد چهار را با یک انگشت نمایش می دهند.

به هنگام جمع نمودن دو عدد نیز، هیولا های این سرزمین ابتدا با انگشت های خود عدد اول را نمایش داده و سپس عدد دوم را به وسیله انگشتان به عدد اول اضافه می کنند. سینا که تعداد دست و انگشتانش همانند هیولا ها نیست، نمی تواند همانند آن ها جمع اعداد را محاسبه کند. به سینا کمک کنید با دانستن تعداد دست ها و انگشت های یک هیولا، جمع دو عدد را محاسبه کند.

ورودی🔗

در خط اول تعداد انگشتان یک دست، در خط دوم تعداد دست‌ها و در خطوط سوم و چهارم دو عددی که باید با یک دیگر جمع شوند آمده‌اند.

تمامی اعداد ورودی بزرگ‌تر یا مساوی صفر و کوچک‌تر از $10^4$ هستند.

مجموع تعداد انگشتان هیولاها بزرگ‌تر از صفر است.

خروجی🔗

در تنها خط خروجی، عدد نمایش داده شده با دست هیولاها (تعداد انگشت‌های باز) پس از عملیات جمع را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

اعداد شبه‌باینری

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

کامران به عنوان یک کامپیوتری باسابقه، علاقه زیادی به اعداد باینری و هر آنچه به آن‌ها مربوط می‌شود دارد. او به دنبال اعداد شبه باینری می‌گردد. عدد شبه باینری عددی است که جمع مقسوم علیه هایش (به غیر از خودش) توانی از ٢ شود. برنامه ای بنویسید که به کامران کمک کند اعداد شبه باینری را تشخیص دهد.

ورودی🔗

در تنها خط ورودی، عدد طبیعی $n$ داده می‌شود. $1 \leq n \leq 2^{14}$

خروجی🔗

اگر عدد داده شده شبه باینری است، در تنها خط خروجی عدد 1 را چاپ کنید؛ درغیر این صورت عدد 0 را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

ورودی نمونه ۴🔗

خروجی نمونه ۴🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مسابقه‌ی فوتبال بین دو تیم پائوزو و کوریه در حال شروع شدن است و بحث سر این که کدام تیم برنده خواهد شد به بالاترین حد خود رسیده است. طبق تجارب پیشین می‌دانیم همیشه تیمی برنده شده است که خفن‌ترین گروه هواداران را داشته باشد. این مسابقه تعدادی تماشاچی دارد که در یک ردیف کنار هم نشسته‌اند و هرکس یا طرفدار پائوزو است یا کوریه که اولی را با `0` و دومی را با `1` نمایش می‌دهیم. گروه هواداران به هر کلونی (حداقل ١ نفر) از تماشاچی‌ها گفته می‌شود که کنار هم نشسته اند و همه طرفدار یک تیم مشترک اند (همه `0` یا همه `1` هستند). خفن‌ترین گروه هواداران برای هر تیم، بزرگ‌ترین آن گروه‌ها در نظر گرفته می‌شود. حال ما که هوادار دوآتشه‌ی پائوزو هستیم می‌خواهیم تعداد اعضای خفن‌ترین گروه هواداران پائوزو را در سوپرگروه تلگرامی «کل کل دربی» اعلام کنیم تا در ادامه به رجزخوانی بپردازیم. # ورودی در تنها خط ورودی یک رشته متشکل از حروف `0` و `1` آمده است که آرایش نشستن تماشاچیان را نشان می‌دهد. طول رشته‌ی ورودی حداکثر $10^4$ است. # خروجی در تنها خط خروجی، تعداد اعضای خفن‌ترین گروه هواداران پائوزو را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 1000100100001 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 0001111001 ``` ## خروجی نمونه ۲ ``` 3 ``` ## ورودی نمونه ۳ ``` 010011100000 ``` ## خروجی نمونه ۳ ``` 5 ``` ## ورودی نمونه ۴ ``` 10101010101 ``` ## خروجی نمونه ۴ ``` 1 ```

خفن‌ترین هواداران

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

مسابقه‌ی فوتبال بین دو تیم پائوزو و کوریه در حال شروع شدن است و بحث سر این که کدام تیم برنده خواهد شد به بالاترین حد خود رسیده است. طبق تجارب پیشین می‌دانیم همیشه تیمی برنده شده است که خفن‌ترین گروه هواداران را داشته باشد.

این مسابقه تعدادی تماشاچی دارد که در یک ردیف کنار هم نشسته‌اند و هرکس یا طرفدار پائوزو است یا کوریه که اولی را با 0 و دومی را با 1 نمایش می‌دهیم. گروه هواداران به هر کلونی (حداقل ١ نفر) از تماشاچی‌ها گفته می‌شود که کنار هم نشسته اند و همه طرفدار یک تیم مشترک اند (همه 0 یا همه 1 هستند). خفن‌ترین گروه هواداران برای هر تیم، بزرگ‌ترین آن گروه‌ها در نظر گرفته می‌شود.

حال ما که هوادار دوآتشه‌ی پائوزو هستیم می‌خواهیم تعداد اعضای خفن‌ترین گروه هواداران پائوزو را در سوپرگروه تلگرامی «کل کل دربی» اعلام کنیم تا در ادامه به رجزخوانی بپردازیم.

ورودی🔗

در تنها خط ورودی یک رشته متشکل از حروف 0 و 1 آمده است که آرایش نشستن تماشاچیان را نشان می‌دهد.

طول رشته‌ی ورودی حداکثر $10^4$ است.

خروجی🔗

در تنها خط خروجی، تعداد اعضای خفن‌ترین گروه هواداران پائوزو را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

1000100100001

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

0001111001

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

010011100000

خروجی نمونه ۳🔗

ورودی نمونه ۴🔗

10101010101

خروجی نمونه ۴🔗

خانه‌ی بازنده

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

جدول $A$ با ابعاد $n \times n$ به شما داده شده است. ارزش هر خانه از جدول برابر با $A_{i, j}$ است. دو خانه از جدول همسایه اند اگر یک ضلع مشترک داشته باشند. یک خانه بازنده است اگر ارزشی کم تر یا مساوی همه‌ی همسایه‌های خود داشته باشد. برنامه‌ای بنویسید تا تعداد خانه‌های بازنده‌ی جدول را بیابد.

ورودی🔗

در خط اول ورودی عدد صحیح $n$ آمده است که ابعاد جدول $A$ را نشان می‌دهد.

$1 \leq n \leq 100$

در $n$ خط بعدی، جدول $A$ آمده است. در خط $i$ ام، $n$ عدد $A_{i, 1}, A_{i, 2}, \dots, A_{i, n} \,$ آمده است. بین اعداد دقیقاً یک فاصله وجود دارد.

$0 \leq A_{i, j} \leq 10^6$

خروجی🔗

در تنها خط خروجی، یک عدد معادل تعداد خانه‌های بازنده‌ی جدول ورودی را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

1
1

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

2
1 2
2 1

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- باران شدیدی در جنگل شروع به باریدن گرفته و حیوانات جنگل به خانه ی خاله مرجان هجوم می‌آورند تا شب را در آنجا سپری کنند. خاله مرجان هم مثل همیشه در خانه اش را به روی حیوانات جنگل باز می‌گذارد و $n$ حیوان از سراسر جنگل وارد خانه ی خاله مرجان می‌شوند. خانه‌ی خاله مرجان به شکل یک تالار به طول $10^6$ و عرض $1$ متر است که در ابتدای این تالار در ورودی قرار دارد. هر کدام از حیوانات بعد از وارد شدن به خانه‌ی خاله مرجان در یک فاصله‌ای از در می‌خوابند. قد تمام حیوانات یک متر و عرض آن‌ها صفر است! آن‌ها به گونه‌ای می‌خوابند که قدشان در موازات عرض تالار باشد. پس با توجه به لاغری تمام حیوانات، می‌توان محل خوابیدن هر کدام از آن‌ها را با یک عدد طبیعی بین $1$ تا $10^6$ نشان داد که فاصله‌ی آن‌ها از در است. خاله مرجان که نگران سرما خوردن مهمان های خود است، تصمیم می‌گیرد با کم ترین تعداد پتو، تمام مهمان‌ها را پوشش دهد. پتوهای خاله مرجان مستطیل شکل به طول $d$ و عرض یک متر هستند. حال می‌خواهیم به خاله مرجان بگوییم چند پتو نیاز دارد. برای مثال اگر طول پتوها $3$ باشد و یکی از حیوانات در فاصله‌ی $2$ متری در و دیگری در فاصله‌ی $5$ متری در باشد، می‌توان با یک پتو که بازه‌ی $[2 ,5]$ را پوشش می‌دهد، هر دو حیوان را پوشش داد. # ورودی در خط اول ورودی دو عدد طبیعی $n$ و $d$ آمده است که به ترتیب تعداد حیوانات و طول پتوهای خاله مرجان را نشان می‌دهد. $$1 \leq n \leq 5000, \quad \quad 1 \leq d \leq 10^6$$ در خط بعدی، $n$ عدد طبیعی آمده است که $i$امین آن ها محل خوابیدن $i$امین حیوان را نشان می‌دهد. محل خوابیدن هر حیوان حداکثر $10^6$ است. # خروجی در خروجی، کم‌ترین تعداد پتوی لازم را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 4 2 4 3 2 1 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 6 3 7 4 13 1 11 15 ``` ## خروجی نمونه ۲ ``` 4 ```

مهمان نوازی

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

باران شدیدی در جنگل شروع به باریدن گرفته و حیوانات جنگل به خانه ی خاله مرجان هجوم می‌آورند تا شب را در آنجا سپری کنند. خاله مرجان هم مثل همیشه در خانه اش را به روی حیوانات جنگل باز می‌گذارد و $n$ حیوان از سراسر جنگل وارد خانه ی خاله مرجان می‌شوند. خانه‌ی خاله مرجان به شکل یک تالار به طول $10^6$ و عرض $1$ متر است که در ابتدای این تالار در ورودی قرار دارد. هر کدام از حیوانات بعد از وارد شدن به خانه‌ی خاله مرجان در یک فاصله‌ای از در می‌خوابند. قد تمام حیوانات یک متر و عرض آن‌ها صفر است! آن‌ها به گونه‌ای می‌خوابند که قدشان در موازات عرض تالار باشد. پس با توجه به لاغری تمام حیوانات، می‌توان محل خوابیدن هر کدام از آن‌ها را با یک عدد طبیعی بین $1$ تا $10^6$ نشان داد که فاصله‌ی آن‌ها از در است.

خاله مرجان که نگران سرما خوردن مهمان های خود است، تصمیم می‌گیرد با کم ترین تعداد پتو، تمام مهمان‌ها را پوشش دهد. پتوهای خاله مرجان مستطیل شکل به طول $d$ و عرض یک متر هستند. حال می‌خواهیم به خاله مرجان بگوییم چند پتو نیاز دارد. برای مثال اگر طول پتوها $3$ باشد و یکی از حیوانات در فاصله‌ی $2$ متری در و دیگری در فاصله‌ی $5$ متری در باشد، می‌توان با یک پتو که بازه‌ی $[2 ,5]$ را پوشش می‌دهد، هر دو حیوان را پوشش داد.

ورودی🔗

در خط اول ورودی دو عدد طبیعی $n$ و $d$ آمده است که به ترتیب تعداد حیوانات و طول پتوهای خاله مرجان را نشان می‌دهد. $1 \leq n \leq 5000, \quad \quad 1 \leq d \leq 10^6$

در خط بعدی، $n$ عدد طبیعی آمده است که $i$ امین آن ها محل خوابیدن $i$ امین حیوان را نشان می‌دهد.

محل خوابیدن هر حیوان حداکثر $10^6$ است.

خروجی🔗

در خروجی، کم‌ترین تعداد پتوی لازم را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

4 2
4 3 2 1

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

6 3
7 4 13 1 11 15

خروجی نمونه ۲🔗

برج مراقبت

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

علی به تازگی از دانشگاه فارغ التحصیل شده است و به دنبال شغل می‌گردد. امیر کار در برج مراقبت شهر قوتل را به او پیشنهاد می‌دهد. علی با اشتیاق این پیشنهاد را پذیرفت و در آزمون استخدامی شرکت کرد. در این امتحان علی با یک سوال عجیب روبه رو شده که برای حلش از شما کمک می‌خواهد. یک دنباله از اعداد طبیعی متمایز به ما داده شده است. به یک زیر دنباله‌ی متوالی از آن قوتلی می‌گوییم اگر اعداد دو سر آن از بقیه اعداد آن زیر دنباله بیشتر باشند (منظور از یک زیردنباله‌ی متوالی، تعدادی از اعضای دنباله هستند که بصورت متوالی کنار هم قرار گرفته اند.) علی باید بزرگ‌ترین زیر دنباله‌ی متوالی قوتلی را از نظر تعداد اعضا پیدا کند.

ورودی🔗

در خط اول $n$ تعداد اعضای دنباله و در خط دوم اعضای دنباله که اعداد طبیعی متمایز هستند به شما داده می‌شود.

$1 \leq n \leq 1000$

اعضای دنباله حداکثر $10^6$ هستند.

خروجی🔗

در تنها خط خروجی، طول بزرگ ترین زیر دنباله‌ی متوالی قوتلی را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

6
1 5 4 6 2 3

خروجی نمونه ۱🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ببعی به تازگی یک تلویزیون خریده است که دارای ۱۰۰ شبکه است. کنترل این تلویزیون شامل دکمه‌های `0` تا `9` ، `_` ، بالا و پایین است. دکمه‌های بالا و پایین، کانال تلویزیون را یکی زیاد یا کم می‌کنند و برای رفتن به کانالی به صورت مستقیم اگر شماره کانال دو رقمی باشد باید اول دکمه‌ی `_` را فشار دهیم. مثلاً برای رفتن به کانال $85$ به صورت مستقیم، باید به ترتیب ٣ دکمه‌ی `_` ، `8` و `5` را زد. ولی برای رفتن به کانال $6$ تنها کافیست تا دکمه `6` را بزنیم. یک روز ببعی متوجه می‌شود که گاوی به علت گشنگی(!)، تعدادی از دکمه‌های کنترل را بلعیده است. حال آقای مجری از ببعی می‌خواهد با دکمه‌های باقی‌مانده با کم‌ترین تعداد زدن دکمه از کانال جاری ($X$) به کانال دیگری برود ($Y$). به ببعی کمک کنید! # ورودی در چهار خط اول ورودی وضعیت دکمه‌های کنترل به ترتیب نشان داده شده آمده است. (`1` یعنی سالم و `0` یعنی خراب) \[ \begin{array}{cccl} 1 & 2 & 3 & \text{up} \\ 4 & 5 & 6 & \text{down} \\ 7 & 8 & 9 \\ \_ & 0 \end{array} \] در خط آخر دو عدد $X$ و $Y$ آمده که به ترتیب کانالی که روی آن هستیم و کانالی که می‌خواهیم به آن برویم هستند. $$ 0 \leq X, Y \leq 99$$ # خروجی در تنها خط خروجی، کم‌ترین تعداد زدن دکمه‌ها را چاپ کنید و اگر رفتن به کانال مذکور امکان پذیر نیست، `-1` را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 1 1 1 1 1 1 1 1 1 1 1 1 1 23 52 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 0 0 1 1 1 1 1 1 1 1 1 1 1 23 52 ``` ## خروجی نمونه ۲ ``` 4 ```

کنترل تلویزیون

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

ببعی به تازگی یک تلویزیون خریده است که دارای ۱۰۰ شبکه است. کنترل این تلویزیون شامل دکمه‌های 0 تا 9 ، _ ، بالا و پایین است. دکمه‌های بالا و پایین، کانال تلویزیون را یکی زیاد یا کم می‌کنند و برای رفتن به کانالی به صورت مستقیم اگر شماره کانال دو رقمی باشد باید اول دکمه‌ی _ را فشار دهیم. مثلاً برای رفتن به کانال $85$ به صورت مستقیم، باید به ترتیب ٣ دکمه‌ی _ ، 8 و 5 را زد. ولی برای رفتن به کانال $6$ تنها کافیست تا دکمه 6 را بزنیم.

یک روز ببعی متوجه می‌شود که گاوی به علت گشنگی(!)، تعدادی از دکمه‌های کنترل را بلعیده است. حال آقای مجری از ببعی می‌خواهد با دکمه‌های باقی‌مانده با کم‌ترین تعداد زدن دکمه از کانال جاری ( $X$ ) به کانال دیگری برود ( $Y$ ). به ببعی کمک کنید!

ورودی🔗

در چهار خط اول ورودی وضعیت دکمه‌های کنترل به ترتیب نشان داده شده آمده است. (1 یعنی سالم و 0 یعنی خراب)

$\begin{array}{cccl} 1 & 2 & 3 & \text{up} \\ 4 & 5 & 6 & \text{down} \\ 7 & 8 & 9 \\ \_ & 0 \end{array}$

در خط آخر دو عدد $X$ و $Y$ آمده که به ترتیب کانالی که روی آن هستیم و کانالی که می‌خواهیم به آن برویم هستند. $0 \leq X, Y \leq 99$

خروجی🔗

در تنها خط خروجی، کم‌ترین تعداد زدن دکمه‌ها را چاپ کنید و اگر رفتن به کانال مذکور امکان پذیر نیست، -1 را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

کلم‌پلو

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

ببعی به تازگی وارد تجارت و هم چنین عضو شبکه‌ی اجتماعی کاهوگرام شده است. در این شبکه، هر فرد دارای یک نشان اختصاصی (ID) است. هر عضو شبکه، تعدادی از اعضای دیگر این شبکه را دنبال می‌کند و هر مطلبی که هر کدام از آن ها منتشر کند را بازنشر می‌کند. حال ببعی می‌خواهد به تعدادی از اعضای این شبکه یک بیت کلم ارسال کند تا تبلیغ شرکتش را در صفحه خودشان بگذارند که در نهایت همه‌ی اعضای شبکه تبلیغش را ببینند. از آن جایی که بیت کلم لحظه به لحظه گران تر می‌شود، به ببعی بگویید کم ترین تعداد بیت کلمی که نیاز دارد چه قدر است.

ورودی🔗

در خط اول $n$ (تعداد اعضای شبکه) می‌آید.

$1 \leq n \leq 50 \, 000$

در خط $i + 1$ ام تعداد افرادی که فرد $i$ ام را دنبال می‌کنند و سپس ID آن افراد می‌آید. IDها شامل اعداد $1$ تا $n$ هستند. تعداد دنبال کردن ها از $200 \, 000$ بیش تر نمی‌شود.

خروجی🔗

در تنها خط خروجr، کم ترین تعداد بیت کلمr که ببعr نیاز دارد را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗