Завдання · алгоритми складний 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 · Як проходять раунди та нараховується рейтинг →

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 с · виконання 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у відповіді немає коду	—