CSES - Putka Open 2015 – 1/6 - Results
Submission details
Task:Lähetit
Sender:
Submission time:2015-07-18 15:33:19 +0300
Language:Python2
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.09 s1details
#2ACCEPTED0.12 s1details
#30.08 s1details
#40.09 s1details
#5ACCEPTED0.10 s1details
#6--2details
#7--2details
#8--2details
#9--2details
#10ACCEPTED0.11 s2details
#11--3details
#12--3details
#13--3details
#14--3details
#15ACCEPTED0.08 s3details

Code

import sys
import math
import itertools
from collections import defaultdict

n, k = map(int, sys.stdin.readline().rstrip().split())

if k > 2*n - 2:
	print 0
	sys.exit()

def countways(diags, board):
	thisdiag = diags[0]
	y = min(thisdiag, n - 1)
	x = max(0, thisdiag - (n-1))
	tot = 0
	while y >= 0 and x < n:
		if board[x][y] == False:
			x += 1
			y -= 1
			continue
		elif len(diags) == 1 and board[x][y] == True:
			tot += 1
			x += 1
			y -= 1
			continue
		xnew = x
		ynew = y
		while ynew < n and xnew < n:
			board[xnew][ynew] = False
			xnew += 1
			ynew += 1
		else:
			tot += countways(diags[1:], board)
		xnew = x
		ynew = y
		while ynew < n and xnew < n:
			board[xnew][ynew] = True
			xnew += 1
			ynew += 1
		x += 1
		y -= 1
	return tot

board = [[True]*n for k in range(n)]#range(1,n+1) + list(reversed(range(1,n)))
	
alltot = 0
for t in itertools.combinations(range(2*n - 1), k):
	alltot += countways(t, board)

print alltot % (10**9 + 7)
'''
	di = diags[:]
	thistot = 1
	for i in t:
		thistot *= max(di[i], 1)
		k = i + 2
		while k < len(di):
			di[k] -= 1
			k += 2
	tot += thistot
'''


# 1 2 2 3 3 2 1 

Test details

Test 1

Group: 1

Verdict:

input
5 2

correct output
240

user output
2728

Test 2

Group: 1

Verdict: ACCEPTED

input
5 4

correct output
2728

user output
2728

Test 3

Group: 1

Verdict:

input
5 6

correct output
1960

user output
2728

Test 4

Group: 1

Verdict:

input
5 8

correct output
32

user output
2728

Test 5

Group: 1

Verdict: ACCEPTED

input
5 10

correct output
0

user output
0

Test 6

Group: 2

Verdict:

input
10 4

correct output
1809464

user output
(empty)

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