المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی سوم:دوره ی ۱۹:سوال ۵

ماهی سیاه کوچولو

علی کوچولو یک جدول $5\times 5$ دارد. هر یک از خانه‌های جدول به شکل یک آکواریوم سر باز است که می‌تواند پر ا ز آب یا خالی باشد.

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

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

دقت کنید که علی اجازه دارد خانه‌هایی که در مسیر نیستند را هم پر کند؛ منتهی پر کردن این خانه‌ها نباید مسیر جدیدی برای رفتن از مبدا به مقصد برای ماهی بسازد. دو مسیر را متفاوت می‌گوییم اگر در حداقل یک خانه متفاوت باشند.

اگر تعداد راه‌های انجام این کار را $S$ بگیریم؛ باقی‌مانده‌ی $S$ بر $\Delta$ چند است؟

پاسخ

‎
 
 
 
#include <iostream> 
#include <vector> 
using namespace std; 
 
vector<int> path; 
 
int numones(int x) { 
  int c = 0; 
  for (; x > 0; x/= 2) 
    c += (x % 2); 
  return c; 
} 
 
int mask; 
#define cell(x,y) ((mask >> (x*5+y)) & 1) 
 
int main() { 
  for (int i=0; i<(1<<8); i++) 
    if (numones(i) == 4) 
      path.push_back(i); 
 
  int ans = 0; 
  for (mask = 0; mask <(1<<25); mask++) { 
    if (cell(0,0) == 0 || cell(4,4) == 0) continue; 
 
    int c = 0; 
    for (int k=0; k<(int)path.size(); k++) { 
      int curx = 0, cury = 0; 
      for (int j=0; j<8; j++) { 
        if ((path[k] >> j) & 1) curx++; else cury++; 
        if (cell(curx,cury) == 0) goto nextpath; 
      } 
      c++; 
      nextpath: ; 
   } 
   ans += (c == 1); 
  }  
 
  cout << ans << endl; 
 
  return 0; 
}

ابزار صفحه