Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:تئوری نهایی دوم:سوال ۱

جدول تنتتنی

پس از بازی جدول منهتنی(رجوع شود به آزمون مرحله دوم ۱۳۹۴)، فرهاد و علی‌رضا تصمیم گرفتند بازی جدول تنتتنی را انجام دهند. آن‌ها در این بازی یک جدول m×n دارند (m,n>2) و روی آن بازی می‌کنند. خانه‌ی واقع در سطر i-ام و ستون j-ام جدول را با (i,j) نشان می‌دهیم. فاصله‌ی دو خانه‌ی (r1,c1) و (r2,c2) را، برابر |r1r2|+|c1c2| تعریف می‌کنیم. برای مثال، در جدول زیر، فاصله‌ی دو خانه‌ی مشخص شده، برابر ۵ است:

فرهاد k خانه‌ی a1,a2,,ak از جدول را انتخاب می‌کند و به علی‌رضا می‌گوید؛ سپس علی‌رضا یک خانه از جدول مانند X را انتخاب می‌کند. فرض کنید فاصله‌ی خانه‌ی ai تا X برابر bi باشد. علی‌رضا دنباله‌ی اعداد b1,b2,,bk را در نظر می‌گیرد و این k عدد را به ترتیبی دل‌خواه به فرهاد می‌گوید. در واقع تفاوت این بازی با بازی جدول منهتنی این است که فرهاد نمی‌داند هر عدد علی‌رضا مربوط به کدام یک از ai ها است. حال باید فرهاد با توجه به این k عدد، خانه‌ی مورد نظر علی‌رضا (X) را پیدا کند. فرهاد در صورتی می‌برد که خانه‌ی مورد نظر علی‌رضا را بفهمد. فرض کنید هر دو نفر به به‌ترین نحو ممکن بازی می‌کنند و k کم‌ترین عددی باشد که فرهاد روشی برای انتخاب k خانه داشته باشد که ببرد. k را بیابید.


ابزار صفحه