Submission details
Task:Tontti
Sender:konstikas
Submission time:2015-10-04 01:58:43 +0300
Language:Python3
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.08 s1details
#20.08 s1details
#30.08 s1details
#40.08 s1details
#50.07 s1details
#6--2details
#7--2details
#8--2details
#9--2details
#10--2details
#11--3details
#12--3details
#13--3details
#14--3details
#15--3details

Code

#!/usr/bin/env python3

# miten monella n x m -ruudukon k x k -neliötontilla on p puuta?

# esimerkkisyöte:
'''
4 6 3
..**..
**....
*...*.
..*...
'''

def viistorivin_osumat(x, y, p, kum_riv, kum_sar):
    '''palauta sopivien (p puuta) neliötonttien määrä viistorivillä'''
    maara = 0
    y_max = len(kum_riv) - 1
    x_max = len(kum_riv[0]) - 1
    vika_x = x + min(x_max - x, y_max - y)
    x2 = x
    y2 = y
    puita_nyt = kum_riv[y][x] - kum_riv[y][x - 1]
    while x2 <= vika_x:
        if puita_nyt <= p:
            if puita_nyt == p:
                maara += 1
            # venytetään tonttia oikeasta alakulmasta
            x2 += 1
            if x2 > vika_x:
                break
            y2 += 1
            # oikea pystysivu lisää, ilman alakulmaa
            puita_nyt += kum_sar[y2 - 1][x2] - kum_sar[y - 1][x2]
            # alasivu lisää, oikean alakulman kanssa
            puita_nyt += kum_riv[y2][x2] - kum_sar[y2][x - 1]
        else:
            # siirretään aloituskohtaa yhdellä eteenpäin, alaviistoon
            x += 1
            y += 1
            x2 = x
            y2 = y
            puita_nyt = kum_riv[y][x] - kum_riv[y][x - 1]
    return maara

def sopivia_tontteja(p, kum_riv, kum_sar):
    y_max = len(kum_riv) - 1
    x_max = len(kum_riv[0]) - 1
    maara = 0
    for x in range(1, x_max + 1):
        maara += viistorivin_osumat(x, 1, p, kum_riv, kum_sar)
    for y in range(2, y_max + 1):
        maara += viistorivin_osumat(1, y, p, kum_riv, kum_sar)
    return maara

def lue_ruudukko(n, m):
    kum_riv = [[0] * (m + 1)]
    kum_sar = [[0] * (m + 1)]
    for y in range(n):
        rivi = [1 if c == '*' else 0 for c in input().rstrip()]
        kr = [0]
        ks = [0]
        for x, v in enumerate(rivi):
            kr.append(kr[-1] + v)
            ks.append(kum_sar[-1][x + 1] + v)
        kum_riv.append(kr)
        kum_sar.append(ks)
    return kum_riv, kum_sar

def main():
    n, m, k = map(int, input().split())
    kum_rivit, kum_sarakkeet = lue_ruudukko(n, m)
    print(sopivia_tontteja(k, kum_rivit, kum_sarakkeet))

if __name__ == '__main__':
    main()

Test details

Test 1

Group: 1

Verdict:

input
10 10 1
......*...
.......*..
*..*....*.
*....*....
...

correct output
94

user output
21

Test 2

Group: 1

Verdict:

input
10 10 5
**********
**********
**********
**********
...

correct output
0

user output
6

Test 3

Group: 1

Verdict:

input
10 10 10
**...*...*
*..*.**.*.
...**.*..*
*...**.*..
...

correct output
4

user output
3

Test 4

Group: 1

Verdict:

input
10 10 5
****......
*.*.**..**
....*.*..*
...*.***..
...

correct output
16

user output
14

Test 5

Group: 1

Verdict:

input
10 10 2
**.***..*.
...*.*....
.***.*...*
***.***..*
...

correct output
30

user output
19

Test 6

Group: 2

Verdict:

input
500 500 1
.................................

correct output
9552040

user output
(empty)

Test 7

Group: 2

Verdict:

input
500 500 5
.................................

correct output
1536063

user output
(empty)

Test 8

Group: 2

Verdict:

input
500 500 25000
**...*...**..*.*..*.**.*..*.*....

correct output
288

user output
(empty)

Test 9

Group: 2

Verdict:

input
500 500 12500
**.**.*..*...*.**...*.***........

correct output
786

user output
(empty)

Test 10

Group: 2

Verdict:

input
500 500 5000
.*.*.**..*.*.**.**..*..**...*....

correct output
1763

user output
(empty)

Test 11

Group: 3

Verdict:

input
2000 2000 1
.................................

correct output
489611392

user output
(empty)

Test 12

Group: 3

Verdict:

input
2000 2000 5
.................................

correct output
120725884

user output
(empty)

Test 13

Group: 3

Verdict:

input
2000 2000 400000
..*..**.**.**.*.***...**.*..**...

correct output
1849

user output
(empty)

Test 14

Group: 3

Verdict:

input
2000 2000 200000
***.*....*.*..*....**..*..*.*....

correct output
2665

user output
(empty)

Test 15

Group: 3

Verdict:

input
2000 2000 80000
**.**...*.***.**....**.*....*....

correct output
5587

user output
(empty)