CSES - Putka Open 2015 – 1/6 - Results
Submission details
Task:Lähetit
Sender:
Submission time:2015-07-18 18:55:38 +0300
Language:Python3
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.13 s1details
#2ACCEPTED0.12 s1details
#3ACCEPTED0.12 s1details
#4ACCEPTED0.12 s1details
#5ACCEPTED0.12 s1details
#6ACCEPTED0.55 s2details
#7--2details
#8--2details
#9--2details
#10ACCEPTED0.13 s2details
#11--3details
#121.42 s3details
#13--3details
#14--3details
#15ACCEPTED0.12 s3details

Code

#!/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 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:

input
10 8

correct output
209594075

user output
(empty)

Test 8

Group: 2

Verdict:

input
10 12

correct output
811277399

user output
(empty)

Test 9

Group: 2

Verdict:

input
10 16

correct output
17275136

user output
(empty)

Test 10

Group: 2

Verdict: ACCEPTED

input
10 20

correct output
0

user output
0

Test 11

Group: 3

Verdict:

input
100 40

correct output
126883191

user output
(empty)

Test 12

Group: 3

Verdict:

input
100 80

correct output
785497039

user output
(empty)

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

input
100 200

correct output
0

user output
0