Lähetit

#!/usr/bin/env python3

# ajatellaan viistorivejä suorina, jolloin saadaan rivit:
#    x
#   xxx
#  xxxxx
# jne.

# jokaiselle näin saadulle vaakariville voidaan sijoittaa max. yksi lähetti

from functools import wraps

n, k = map(int, input().split())
riveja_yhteensa = 2 * n - 1

def valimuisti(f):
    muisti = {}
    def ymparoiva_funktio(*arg):
        avain = arg
        try:
            tulos = muisti[avain]
        except KeyError:
            tulos = f(*arg)
            muisti[avain] = tulos
        return tulos
    return ymparoiva_funktio

def sarakkeet(rivi):
    # sarakkeet ovat symmetriset
    keskimmainen_sarake = n
    poikkeama = n - abs(n - rivi) - 1
    for s in range(keskimmainen_sarake - poikkeama, keskimmainen_sarake + poikkeama + 1, 2):
        yield s

sarakkeet_per_rivi = [[]] + [list(sarakkeet(r)) for r in range(1, riveja_yhteensa + 1)]
uhatut_sarakkeet = set()

@valimuisti
def mahdollisuuksia(lahetteja_jaljella, ekarivi, kaytetyt_sarakkeet):
    if lahetteja_jaljella == 0:
        return 1

    mahd = 0

    for rivi in range(ekarivi, riveja_yhteensa + 1):
        if riveja_yhteensa - rivi + 1 < lahetteja_jaljella:
            break

        for s in sarakkeet_per_rivi[rivi]:
            if s not in uhatut_sarakkeet:
                uhatut_sarakkeet.add(s)
                mahd += mahdollisuuksia(lahetteja_jaljella - 1, rivi + 1, tuple(sorted(uhatut_sarakkeet)))
                uhatut_sarakkeet.remove(s)
    return mahd

print(mahdollisuuksia(k, 1, tuple()))

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: ACCEPTED

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: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: RUNTIME ERROR

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: ACCEPTED