المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۱۷:عملی:سوال ۱۲

هپید

از آنجا که هپید دوباره شروع کرده بود به گریه کردن، افشین او را روی یکی از رأس‌های یک گراف جهت دار ‎$n$‎ رأسی گذاشت (رأس ‎$s$‎) و بهش گفت که توی رأس ‎$t$‎ از این گراف، یک مهدکودک جدید ساخته‌اند.

هپید هم تصمیم گرفت که مسافرت خود را از ‎$s$‎ به ‎$t$‎ شروع کند. او با خود قرار گذاشت که در روز ‎$i$‎ام از مسافرتش ‎($i \ge 1$)‎، دقیقاً ‎$2^{i-1}$‎ یال از گراف را طی کند و اگر پس از طی این ‎$2^{i-1}$‎ جاده، در مهدکودک قرار نداشت، صبر کند تا روز بعد. البته این را در نظر داشته باشید که هپید تا ‎$k$‎ روز بعد از لحظه‌ی شروع مسافرتش عمر می‌کند.

برنامه‌ای بنویسید که با دریافت گراف جهت‌دار و ساده‎ (در یک گراف ساده، از هیچ رأس به خودش یال نیست و از رأس ‎$i$‎ به رأس ‎$j$‎ بیش از یک یال وجود ندارد)، دو راس ‎$s$‎ و ‎$t$‎ از گراف، و عدد ‎$k$‎، اولین روزی که هپید می‌تواند قبل از پایان عمرش به مهدکودک برسد را در صورت وجود چاپ کند.

ورودی

  • ‎‎در سطر اوّل ورودی، به ترتیب اعداد ‎$n$‎ و ‎$k$‎ آمده‌اند.
  • ‎در سطر دوم به ترتیب ‎$s$‎ و ‎$t$‎ نوشته شده‌اند که ‎$1 \leq s,t \leq n$‎ و ‎$s \neq t$‎.
  • ‎سپس در ‎$n$‎ سطر، ماتریس مجاورت گراف به صورت یک ماتریس از $0$‎ و ‎$1$‎ آمده است.
    • در این ماتریس، عدد ‎$j$‎امِ سطر ‎$i$‎ام، ‎$1$‎ است اگر و تنها اگر $i \neq j$‎ و در گراف، یال جهت‌داری از رأس ‎$i$‎ام به را‎ٔس $j$‎ام وجود داشته باشد.
  • $2 \leq n \leq 100$‎.
  • $1 \leq k \leq 50$‎ ولی در ‎$30$‎ درصد تست‌ها ‎$k \leq 15$‎ است.

خروجی

  • ‎در صورت وجود، کم‌ترین ‎$x$‎ای که ‎$x \leq k$‎ و هپید پس از پایان روز ‎$x$‎ام می‌تواند به مهدکودک برسد را چاپ کند.
  • ‎‎در غیر این‌صورت، یعنی اگر هپید نمی‌تواند تا آخر ‎$k$‎ روز به مهدکودک برسد، در خروجی پیام ‎happied is not happy را‎ چاپ کنید.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5 2
1 4
‎0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
2
5 1
1 4
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
‎0 0 0 0 0
happied is not happy

‎‎ ‎‎


ابزار صفحه