Lähetit

#!/usr/bin/env python3

n, k = map(int, input().split())
uhkaukset = {}
for x in range(1, n + 1):
    for y in range(1, n + 1):
        uhkaukset[(x, y)] = 0

def uhkaa(x0, y0):
    yield (x0, y0)

    x, y = x0, y0
    x -= 1
    y -= 1
    while x and y:
        yield (x, y)
        x -= 1
        y -= 1

    x, y = x0, y0
    x -= 1
    y += 1
    while x and y <= n:
        yield (x, y)
        x -= 1
        y += 1

    x, y = x0, y0
    x += 1
    y -= 1
    while x <= n and y:
        yield (x, y)
        x += 1
        y -= 1

    x, y = x0, y0
    x += 1
    y += 1
    while x <= n and y <= n:
        yield (x, y)
        x += 1
        y += 1

def mahdollisuuksia(lahetteja_jaljella, ruutuja_jaljella, x, y):
    if lahetteja_jaljella == 0:
        return 1
    if lahetteja_jaljella > ruutuja_jaljella:
        return 0
    if lahetteja_jaljella > sum(1 for v in uhkaukset.values() if v == 0):
        # liian vähän uhkaamattomia ruutuja jäljellä
        return 0

    mahd = 0
    while ruutuja_jaljella:
        if uhkaukset[(x, y)] == 0:
            # ruutua ei uhata, sijoitetaan lähetti
            for xu, yu in uhkaa(x, y):
                uhkaukset[(xu, yu)] += 1
            if x == n:
                mahd += mahdollisuuksia(lahetteja_jaljella - 1, ruutuja_jaljella - 1, 1, y + 1)
            else:
                mahd += mahdollisuuksia(lahetteja_jaljella - 1, ruutuja_jaljella - 1, x + 1, y)
            for xu, yu in uhkaa(x, y):
                uhkaukset[(xu, yu)] -= 1

        if x == n:
            x = 1
            y += 1
        else:
            x += 1
        ruutuja_jaljella -= 1

    return mahd

print(mahdollisuuksia(k, n * n, 1, 1))

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED