المپدیا

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

ابزار کاربر

ابزار سایت


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

فرار ایشانگولولو

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

حالا باکتری ستمدیده‌ی ما می‌خواهد از طریق این غار فرار کند. به این صورت عمل می‌کند که وارد غار می‌شود و بسته به این‌که به چه چیزی برسد یکی از این سه کار را انجام می‌دهد:

+++++++++اگر به یک بن‌بست برسد، برمی‌گردد به دهانه‌ی غار و جلوی پنجره می‌نشیند. اگر به دنیای آزاد برسد، باکتری آزاد می‌شود و فرار می‌کند. اگر به دو راهی برسد، باکتری دو تا می‌شود و هر کدام از این دو تا وارد یک طرف دوراهی می‌شود و با همین الگوریتم راهش را ادامه می‌دهد!

یک نکته‌ی دیگر درباره‌ی این باکتری‌ها این است که هر کدام دارای یک «عدد جادویی» می‌باشند. عدد جادویی باکتری اولیه ۱ بوده است. هر گاه یک باکتری با عدد جادویی $x$ دوتا می‌شود، دو باکتری خواهیم داشت با عدد جادویی $x+1$. هر باکتری، عدد جادویی خودش را می‌داند.

حالا فرض کنیم که از زمان ورود باکتری اولیه به غار مدتی گذشته و دیگر هیچ باکتری در غار وجود ندارد. حال $n$‌ تا باکتری جلوی پنجره جمع شده‌اند. حالا سوال این است که آیا راهی برای فرار وجود داشته؟ از آن‌جا که باکتری‌ها از $IQ$ خیلی زیادی برخوردار نیستند، به یک آدم هوشمند و خیر مثل شما نیاز دارند که با دریافت عددهای جادوییشان، این سوال را جواب بدهد.

ورودی

در هر فایل ورودی، ممکن است چند نمونه ورودی وجود داشته باشد. در سطر اول فایل ورودی ، عدد $k$ آمده است. سپس $k$ سری اطلاعات بدین صورت می‌آید: در یک خط، عدد $n$ نوشته شده است. در خط بعد، $n$ عدد آمده است که هرکدام عدد جادویی یک باکتری است که جلوی پنجره نشسته.( $k$ و $n$ به ترتیب از ۱۰ و ۲۰۰۰۰ بیش‌تر نیستند)

خروجی

در فایل خروجی،$k$ خط بنویسید. در خط $i$ام، اگر در ورودی $i$ام فایل ورودی راه فرار وجود داشت، بنویسید Yes و در غیر این صورت بنویسید No.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2
4
4 3 2 4
7
3 6 4 3 6 5 4
No
Yes

ابزار صفحه