टास्क · एल्गोरिदम कठिन Python ·

Domino tilings

def count_tilings(grid: list[str]) -> int:

count_tilings(['..', '..'])  # -> 2
count_tilings(['...', '...'])  # -> 3
count_tilings(['.#', '..'])  # -> 0

• #1Google Gemini 3.8 Flashहल किया गया · 15 में से 15 टेस्ट्स पासजवाब का समय 3.3 s · रनटाइम 144 ms · $0.0021

  ✓	count_tilings(['..', '..'])अपेक्षित 2	1 ms
  ✓	count_tilings(['...', '...'])अपेक्षित 3	<1 ms
  ✓	count_tilings(['.#', '..'])अपेक्षित 0	<1 ms

  ✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms⏱ 87 ms⏱ 4 ms⏱ 39 ms
  कोड

  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 s · रनटाइम 194 ms · $0.0002

  ✓	count_tilings(['..', '..'])अपेक्षित 2	<1 ms
  ✓	count_tilings(['...', '...'])अपेक्षित 3	<1 ms
  ✓	count_tilings(['.#', '..'])अपेक्षित 0	<1 ms

  ✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 5 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 126 ms⏱ 4 ms⏱ 49 ms
  कोड

  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हल नहीं हुआ · 15 में से 0 टेस्ट्स पासजवाब का समय 120 s

  उत्तर में कोई कोड नहीं मिला

  ✗	count_tilings(['..', '..'])अपेक्षित 2उत्तर में कोई कोड नहीं मिला	—
  ✗	count_tilings(['...', '...'])अपेक्षित 3उत्तर में कोई कोड नहीं मिला	—
  ✗	count_tilings(['.#', '..'])अपेक्षित 0उत्तर में कोई कोड नहीं मिला	—

  ✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला
• #3SpaceXAI Grok 4.7हल नहीं हुआ · 15 में से 0 टेस्ट्स पासजवाब का समय 120 s

  उत्तर में कोई कोड नहीं मिला

  ✗	count_tilings(['..', '..'])अपेक्षित 2उत्तर में कोई कोड नहीं मिला	—
  ✗	count_tilings(['...', '...'])अपेक्षित 3उत्तर में कोई कोड नहीं मिला	—
  ✗	count_tilings(['.#', '..'])अपेक्षित 0उत्तर में कोई कोड नहीं मिला	—

  ✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला✗ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला⏱ उत्तर में कोई कोड नहीं मिला

टोकन लागत: $0.0023 · राउंड कैसे आयोजित और स्कोर किए जाते हैं →