\ \ \ \ \ لانگ‌ جان سیلور در طی سفر دور و دراز خود به دور دنیا، سرانجام به جزیره‌ی گنج پا گذاشت. همه می‌دانستند که مدت‌ها پیش، آن‌ هنگام که کاپیتان فلینت به این جزیره آمده بود، سکه‌های طلا و صندوق‌چه‌های پر از مروارید خود را در آن مخفی کرد. پس لانگ جان سیلور در صدد یافتن این گنج‌ها برآمد. او به دنبال اطلاعاتی در مورد نقشه‌ی جزیره و مکان گنج‌ها می‌گشت، تا این که کاملا اتفاقی با بن گان که از زمان کاپیتان فلینت در آن جزیره تنها گذاشته شده بود، برخورد کرد. سیلور از بن‌گان خواست که جای گنجینه‌های فلینت را به او نشان دهد، تا در مقابل او را از این جزیره‌ی دور افتاده نجات دهد. بن گان، در عوض این پیشنهاد، تنها گفت: «نقشه‌ی جزیره به صورت یک مستطیل (جدول) $m\times n$ است و در هر یک از این $m\times n$ خانه، ممکن است گنجی نهفته باشد.»

از آن‌جا که سیلور حوصله‌ی جستجو کردن همه‌ی این $m\times n$ خانه را نداشت، به بن گان گفت: «خوب، جای گنج‌ها رو هم بگو!» بن گان که مدت‌ها بود پنیر تست‌شده نخورده بود، به سیلور گفت: «پس به من پنیر تست‌شده بده». لانگ جان سیلور هم که دیگه از دست ادا و اطفار‌های بن‌ گان خسته شده بود به بن گان گفت: «برو بینیم بابا!»

بن گان: عمرا دیگه جای گنج‌ها رو بگم!

لانگ جان: خوب حالا! نمی‌خواد قاطی کنی، بهت پنیر تست‌شده هم می‌دم!

بن گان: دو نقطه دی. توی هر مربع $2\times 2$ از جزیره، تعداد خونه‌هایی که گنج دارن زوجه! من بهت اجازه می‌دم از من یه سری سوال به این شکل بپرسی که ‌آیا تو فلان خونه‌ی جزیره گنج هست یا نه. به ازای هر سوالی که از من بپرسی باید بهم یه پنیر تست‌شده بدی. در ضمن برای این که تنبیهت کنم، تو رو از پرسیدن سوال راجع به بعضی از خونه‌ها محروم می‌کنم. حالا برای این که ارفاق کرده باشم، قبل از این که سوالاتو شروع کنی خونه‌هایی که ازشون محروم شدی رو بهت می‌گم.

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

برنامه‌ای بنویسید که:

• ابعاد جزیره ($m$ و $n$) و خانه‌های ممنوع شده توسط بن گان را از کتاب‌خانه‌ی پیوندی بخواند.
• به کمک کتاب‌خانه‌ی پیوندی سوالات مورد نظر را از بن گان بپرسد.
• با کم‌ترین پرسش به کتا‌ب‌خانه‌ی پیوندی گزارش دهد که دقیقا چه خانه‌هایی شامل گنج هستند یا این که نمی‌توان این موضوع را به طور کامل و یکتا مشخص کرد.

کتاب‌خانه

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

• سوال بعد
• سوال قبل