المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۲:سوال ۳۷

سوال ۳۷

یک میدان که به صورت یک صفحه‌ی شطرنجی ‎$n \times n$‎ که $n\geq4$است٬ در مرکز شهر قرار دارد. ‎$k$‎ گانگستر می‌خواهند به این صورت در این میدان دوئل کنند: هر فرد در یک خانه به دلخواه خودش قرار می‌گیرد (در هر خانه حداکثر ‎۱‎‎ نفر) و اسلحه‌ی خود را به سمت یکی از چهار جهت شمال، جنوب، شرق، و یا غرب نشانه گرفته‌است. همه در یک لحظه شلیک می‌کنند. اگر بخواهیم هیچ یک از افراد کشته نشوند، ‎$k$‎ حداکثر چند است؟

  1. $n$
  2. $2n$
  3. $4n$
  4. $4n-2$
  5. $4n-4$

پاسخ

گزینه (۵) درست است.

بهترین حالت ممکن آن است که دور تا دور شبکه٬ ششلول بندها ایستاده و هر کدام از آن‌ها به سمت بیرون شلیک کنند که در این صورت تعداد آن‌ها برابر $n^2-(n-2)^2$؛ یعنی $4n-4$ خواهد شد.


ابزار صفحه