CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:Kurns
Submission time:2018-10-11 16:02:31 +0300
Language:Python3
Status:READY
Result:45
Feedback
groupverdictscore
#1ACCEPTED31
#2ACCEPTED14
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.04 s1details
#6ACCEPTED0.05 s1details
#7ACCEPTED0.06 s1details
#8ACCEPTED0.04 s1details
#9ACCEPTED0.05 s1details
#10ACCEPTED0.05 s1details
#11ACCEPTED0.06 s2details
#12ACCEPTED0.05 s2details
#13ACCEPTED0.04 s2details
#14ACCEPTED0.07 s2details
#15ACCEPTED0.10 s2details
#16ACCEPTED0.15 s2details
#17ACCEPTED0.17 s2details
#18ACCEPTED0.17 s2details
#19ACCEPTED0.17 s2details
#20ACCEPTED0.17 s2details
#21--3details
#22--3details
#23--3details
#24--3details
#25--3details
#26--3details
#27--3details
#28--3details
#29--3details
#30--3details

Code

import sys

rivilkm = int(input())

ruudukko = []
muuteltava = []
mahdollisetAPaikat = []
onATaiB = False

for a in range(0, rivilkm):
    ruudukko.append([])
    muuteltava.append([])
    rivi = input()
    for i in rivi:
        if i == "A" or i == "B":
            onATaiB = True
        ruudukko[a].append(i)
        muuteltava[a].append(i)
        

#Alustus on ok      
def printtaa(arr):     
    for rivi in range(0, rivilkm):
        for sarake in range(0, rivilkm):
            print(arr[rivi][sarake], end = "")
        print("")
    print("")

#Tulostukset ok

deranDict = {0:1, 1:0}
def deran(k):
    if k in deranDict:
        return deranDict[k]
    
    ans = (k-1) * (deran(k-1) + deran(k-2)) 
    deranDict[k] = ans
    return ans

def fact(i):
    ans = 1
    for k in range(i, 0, -1):
        ans *= k
    return ans

if onATaiB == False:
    print(fact(rivilkm)*deran(rivilkm)%1000000007)
    sys.exit(0)

def canPlace(merkki, rivi, sarake):
    if ruudukko[rivi][sarake] != ".":
        return False
    for row in range(0, rivilkm):
        if muuteltava[row][sarake] == merkki: #Samassa sarakkeessa
            return False
    for column in range(0, rivilkm):
        if muuteltava[rivi][column] == merkki: #Samalla rivillä
            return False
    return True


def sijoita(merkki, rivi):
    global muuteltava
    
    #print("HAETAAN", merkki, rivi)
    
    if rivi == rivilkm:
        #print("ADDED TO LIST")
        toadd = [row[:] for row in muuteltava]
        mahdollisetAPaikat.append(toadd)
        return
        
    
    for col in range(0, rivilkm):
        #print("Ollaan menossa row =", rivi, "col=", col)
        if canPlace(merkki, rivi, col) == False and ruudukko[rivi][col] != merkki:
            continue
        if ruudukko[rivi][col] == merkki:
            sijoita(merkki, rivi+1)
        else:
            muuteltava[rivi][col] = merkki
            sijoita(merkki, rivi+1)
            muuteltava[rivi][col] = ruudukko[rivi][col]


mahdollisetRatkaisut = 0           
def sijoitaB(merkki, rivi):
    global mahdollisetRatkaisut
    global muuteltava
    
    #print("HAETAAN", merkki, rivi)
    
    if rivi == rivilkm:
        mahdollisetRatkaisut += 1
        return
        
    
    for col in range(0, rivilkm):
        #print("Ollaan menossa row =", rivi, "col=", col)
        if canPlace(merkki, rivi, col) == False and ruudukko[rivi][col] != merkki:
            continue
        if muuteltava[rivi][col] == "A":
            continue
        if ruudukko[rivi][col] == merkki:
            sijoitaB(merkki, rivi+1)
        else:
            muuteltava[rivi][col] = merkki
            sijoitaB(merkki, rivi+1)
            muuteltava[rivi][col] = ruudukko[rivi][col]



sijoita("A", 0)

for i in mahdollisetAPaikat:
    muuteltava = i
    sijoitaB("B", 0)
    #printtaa(i)

print(mahdollisetRatkaisut)

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2
..
..

correct output
2

user output
2

Test 2

Group: 1

Verdict: ACCEPTED

input
2
..
A.

correct output
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
2
B.
.A

correct output
0

user output
0

Test 4

Group: 1

Verdict: ACCEPTED

input
3
...
...
...

correct output
12

user output
12

Test 5

Group: 1

Verdict: ACCEPTED

input
4
....
....
....
....

correct output
216

user output
216

Test 6

Group: 1

Verdict: ACCEPTED

input
5
.....
.....
.....
.....
...

correct output
5280

user output
5280

Test 7

Group: 1

Verdict: ACCEPTED

input
5
....A
.....
.....
.....
...

correct output
264

user output
264

Test 8

Group: 1

Verdict: ACCEPTED

input
5
B....
.....
.....
.A.B.
...

correct output
22

user output
22

Test 9

Group: 1

Verdict: ACCEPTED

input
5
B.A..
....A
.....
A.B..
...

correct output
2

user output
2

Test 10

Group: 1

Verdict: ACCEPTED

input
5
A.B..
BA...
.B.A.
...BA
...

correct output
1

user output
1

Test 11

Group: 2

Verdict: ACCEPTED

input
10
..........
..........
..........
..........
...

correct output
306442892

user output
306442892

Test 12

Group: 2

Verdict: ACCEPTED

input
50
.................................

correct output
694861480

user output
694861480

Test 13

Group: 2

Verdict: ACCEPTED

input
111
.................................

correct output
555319110

user output
555319110

Test 14

Group: 2

Verdict: ACCEPTED

input
222
.................................

correct output
108372237

user output
108372237

Test 15

Group: 2

Verdict: ACCEPTED

input
333
.................................

correct output
259107857

user output
259107857

Test 16

Group: 2

Verdict: ACCEPTED

input
444
.................................

correct output
19906314

user output
19906314

Test 17

Group: 2

Verdict: ACCEPTED

input
497
.................................

correct output
224313667

user output
224313667

Test 18

Group: 2

Verdict: ACCEPTED

input
498
.................................

correct output
929574601

user output
929574601

Test 19

Group: 2

Verdict: ACCEPTED

input
499
.................................

correct output
600226043

user output
600226043

Test 20

Group: 2

Verdict: ACCEPTED

input
500
.................................

correct output
198353194

user output
198353194

Test 21

Group: 3

Verdict:

input
499
.................................

correct output
840243733

user output
(empty)

Test 22

Group: 3

Verdict:

input
499
........................A........

correct output
4146290

user output
(empty)

Test 23

Group: 3

Verdict:

input
499
B.........A......................

correct output
173518884

user output
(empty)

Test 24

Group: 3

Verdict:

input
499
...A....B........................

correct output
20044800

user output
(empty)

Test 25

Group: 3

Verdict:

input
499
AB...............................

correct output
2

user output
(empty)

Test 26

Group: 3

Verdict:

input
500
.................................

correct output
121064146

user output
(empty)

Test 27

Group: 3

Verdict:

input
500
.................................

correct output
848435259

user output
(empty)

Test 28

Group: 3

Verdict:

input
500
.....B........A..................

correct output
296240911

user output
(empty)

Test 29

Group: 3

Verdict:

input
500
.A......B........................

correct output
2196

user output
(empty)

Test 30

Group: 3

Verdict:

input
500
...AB............................

correct output
1

user output
(empty)