CSES - Putka Open 2015 – 1/6 - Results
Submission details
Task:Lähetit
Sender:
Submission time:2015-07-24 10:30:42 +0300
Language:Python3
Status:READY
Result:35
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED23
#30
Test results
testverdicttimegroup
#1ACCEPTED0.08 s1details
#2ACCEPTED0.08 s1details
#3ACCEPTED0.08 s1details
#4ACCEPTED0.09 s1details
#5ACCEPTED0.07 s1details
#6ACCEPTED0.08 s2details
#7ACCEPTED0.09 s2details
#8ACCEPTED0.08 s2details
#9ACCEPTED0.08 s2details
#10ACCEPTED0.09 s2details
#11ACCEPTED0.57 s3details
#12ACCEPTED1.81 s3details
#13--3details
#14--3details
#15--3details

Code

#!/usr/bin/env python3

# ajatellaan viistorivejä suorina, jolloin esim. 3x3-ruudukosta saadaan rivit:
#    x
#   x x
#  x x x
#   x x
#    x
#
# järjestetään rivit uudestaan laskennan yksinkertaistamiseksi
#    x
#    x
#   x x
#   x x
#  x x x

# jokaiselle näin saadulle vaaka- ja pystyriville voidaan sijoittaa max. yksi lähetti

TULOKSEN_JAKAJA = 10 ** 9 + 7
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

@valimuisti
def mahdollisuuksia(rivi, lahetteja_jaljella, parittomilla, parillisilla):
    if lahetteja_jaljella == 0:
        # kaikki asetettu, ratkaisu siis löytyi
        return 1
    if rivi > riveja_yhteensa:
        # lähettejä jäi asettamatta, ei ratkaisua
        return 0

    ruutuja = (rivi + 1) // 2
    mahd = 0

    if ruutuja % 2:
        # ollaan parittomalla rivillä
        if ruutuja > parittomilla:
            # vielä on ruutuja jäljellä, asetetaan lähetti sille
            mahd += (ruutuja - parittomilla) * mahdollisuuksia(rivi + 1, lahetteja_jaljella - 1, parittomilla + 1, parillisilla)
    else:
        # ollaan parillisella rivillä
        if ruutuja > parillisilla:
            # lähetti sopii, siis asetetaan
            mahd += (ruutuja - parillisilla) * mahdollisuuksia(rivi + 1, lahetteja_jaljella - 1, parittomilla, parillisilla + 1)

    # ei aseteta -laskuhaara
    mahd += mahdollisuuksia(rivi + 1, lahetteja_jaljella, parittomilla, parillisilla)

    return mahd % TULOKSEN_JAKAJA

print(mahdollisuuksia(1, k, 0, 0) % TULOKSEN_JAKAJA)

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
5 2

correct output
240

user output
240

Test 2

Group: 1

Verdict: ACCEPTED

input
5 4

correct output
2728

user output
2728

Test 3

Group: 1

Verdict: ACCEPTED

input
5 6

correct output
1960

user output
1960

Test 4

Group: 1

Verdict: ACCEPTED

input
5 8

correct output
32

user output
32

Test 5

Group: 1

Verdict: ACCEPTED

input
5 10

correct output
0

user output
0

Test 6

Group: 2

Verdict: ACCEPTED

input
10 4

correct output
1809464

user output
1809464

Test 7

Group: 2

Verdict: ACCEPTED

input
10 8

correct output
209594075

user output
209594075

Test 8

Group: 2

Verdict: ACCEPTED

input
10 12

correct output
811277399

user output
811277399

Test 9

Group: 2

Verdict: ACCEPTED

input
10 16

correct output
17275136

user output
17275136

Test 10

Group: 2

Verdict: ACCEPTED

input
10 20

correct output
0

user output
0

Test 11

Group: 3

Verdict: ACCEPTED

input
100 40

correct output
126883191

user output
126883191

Test 12

Group: 3

Verdict: ACCEPTED

input
100 80

correct output
785497039

user output
785497039

Test 13

Group: 3

Verdict:

input
100 120

correct output
324216296

user output
(empty)

Test 14

Group: 3

Verdict:

input
100 160

correct output
895190039

user output
(empty)

Test 15

Group: 3

Verdict:

input
100 200

correct output
0

user output
(empty)