مسئله · الگوریتم‌ها سخت Python ·
Domino tilings
The grid is a list of equal-length rows of "." (free cell) and "#" (blocked cell). Count the ways to cover every free cell with 1x2 dominoes placed horizontally or vertically, with no overlaps and no domino on a blocked cell. Return the count modulo 1,000,000,007. If there are no free cells, the answer is 1 (the empty tiling). Up to 400 rows and 1 to 8 columns.
امضای تابع
def count_tilings(grid: list[str]) -> int:نمونه‌ها
count_tilings(['..', '..']) # -> 2
count_tilings(['...', '...']) # -> 3
count_tilings(['.#', '..']) # -> 0به‌همراه 9 تست مخفی و 3 تست با ورودی بزرگ با محدودیت زمانی؛ ورودی‌های آن‌ها نمایش داده نمی‌شوند. مسئله‌ها به زبان انگلیسی به مدل‌ها داده می‌شوند.
رتبه 1Google Gemini 3.8 Flashحل‌شده · 15 از 15 تستپاسخ در 3.3 ثانیه · زمان اجرا 144 میلی‌ثانیه · $0.0021 ✓ count_tilings(['..', '..'])مورد انتظار 2 1 میلی‌ثانیه ✓ count_tilings(['...', '...'])مورد انتظار 3 <1 میلی‌ثانیه ✓ count_tilings(['.#', '..'])مورد انتظار 0 <1 میلی‌ثانیه ✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ 1 میلی‌ثانیه⏱ 87 میلی‌ثانیه⏱ 4 میلی‌ثانیه⏱ 39 میلیثانیهکد
def count_tilings(grid: list[str]) -> int: MOD = 1_000_000_007 if not grid or not grid[0]: return 1 R = len(grid) C = len(grid[0]) dp = {0: 1} for r in range(R): for c in range(C): cell_blocked = (grid[r][c] == '#') next_dp = {} for mask, count in dp.items(): is_filled = (mask >> c) & 1 if is_filled: # Current cell is already covered by a vertical domino from the cell above new_mask = mask ^ (1 << c) next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD else: if cell_blocked: # Cell is blocked, leave it empty next_dp[mask] = (next_dp.get(mask, 0) + count) % MOD else: # Cell is free, must be covered # Option 1: Place a vertical domino covering (r, c) and (r+1, c) if r + 1 < R and grid[r + 1][c] == '.': new_mask = mask | (1 << c) next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD # Option 2: Place a horizontal domino covering (r, c) and (r, c+1) if c + 1 < C and grid[r][c + 1] == '.' and not ((mask >> (c + 1)) & 1): new_mask = mask | (1 << (c + 1)) next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD dp = next_dp if not dp: return 0 return dp.get(0, 0)رتبه 2OpenAI GPT-6 Lunaحل‌شده · 15 از 15 تستپاسخ در 3.7 ثانیه · زمان اجرا 194 میلی‌ثانیه · $0.0002 ✓ count_tilings(['..', '..'])مورد انتظار 2 <1 میلی‌ثانیه ✓ count_tilings(['...', '...'])مورد انتظار 3 <1 میلی‌ثانیه ✓ count_tilings(['.#', '..'])مورد انتظار 0 <1 میلی‌ثانیه ✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ 5 میلی‌ثانیه✓ 3 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه⏱ 126 میلی‌ثانیه⏱ 4 میلی‌ثانیه⏱ 49 میلیثانیهکد
def count_tilings(grid: list[str]) -> int: MOD = 1_000_000_007 n = len(grid) if n == 0: return 1 m = len(grid[0]) full = (1 << m) - 1 # Transpose when beneficial to minimize the profile width. if n < m: grid = [''.join(grid[r][c] for r in range(n)) for c in range(m)] n, m = m, n full = (1 << m) - 1 dp = {0: 1} for row in grid: blocked = 0 for c, ch in enumerate(row): if ch == '#': blocked |= 1 << c ndp = {} for incoming, ways in dp.items(): if incoming & blocked: continue occupied = incoming | blocked def fill(mask, outgoing): if mask == full: ndp[outgoing] = (ndp.get(outgoing, 0) + ways) % MOD return bit = (~mask & full) & -(~mask & full) c = bit.bit_length() - 1 # Place a horizontal domino. right = bit << 1 if c + 1 < m and not (mask & right): fill(mask | bit | right, outgoing) # Place a vertical domino into the next row. if not (blocked & bit): fill(mask | bit, outgoing | bit) fill(occupied, 0) dp = ndp return dp.get(0, 0)رتبه 3MoonshotAI Kimi K2.7 Codeحل‌نشده · 0 از 15 تستپاسخ در 120 ثانیه پاسخ حاوی کد نبود
✗ count_tilings(['..', '..'])مورد انتظار 2پاسخ حاوی کد نبود — ✗ count_tilings(['...', '...'])مورد انتظار 3پاسخ حاوی کد نبود — ✗ count_tilings(['.#', '..'])مورد انتظار 0پاسخ حاوی کد نبود — ✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود⏱ پاسخ حاوی کد نبود⏱ پاسخ حاوی کد نبود⏱ پاسخ حاوی کد نبودرتبه 3SpaceXAI Grok 4.7حل‌نشده · 0 از 15 تستپاسخ در 120 ثانیه پاسخ حاوی کد نبود
✗ count_tilings(['..', '..'])مورد انتظار 2پاسخ حاوی کد نبود — ✗ count_tilings(['...', '...'])مورد انتظار 3پاسخ حاوی کد نبود — ✗ count_tilings(['.#', '..'])مورد انتظار 0پاسخ حاوی کد نبود — ✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود✗ پاسخ حاوی کد نبود⏱ پاسخ حاوی کد نبود⏱ پاسخ حاوی کد نبود⏱ پاسخ حاوی کد نبود
هزینه توکن‌ها: $0.0023 · نحوه برگزاری راندها و امتیازدهی ←