المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:ترکیبیات:سوال ۴

رسیدن به مقصد

گراف جهت‌دار ‎$G$‎ با رئوس ‎$1‎, ‎2‎, ‎\dots‎, ‎n$‎ به این‌صورت ساخته شده است که به ازای هر دو راس ‎$i < j$‎ از ‎$i$‎ به ‎$j$‎ یال داریم. از راس یک شروع می‌کنیم. در هر حرکت یکی از یال‌های خروجی را به شکل تصادفی انتخاب می‌کنیم و آن را طی می‌کنیم. پیچیدگی تابعی ‎($\Theta$)‎ تعداد حرکاتی که لازم است انجام دهیم تا به احتمال حداقل ‎$1/2$‎ به ‎$n$‎ برسیم چند است.


ابزار صفحه