Submission details
Task:Tontti
Sender:konstikas
Submission time:2015-10-05 00:09:29 +0300
Language:Python3
Status:READY
Result:14
Feedback
groupverdictscore
#1ACCEPTED14
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.10 s1details
#2ACCEPTED0.09 s1details
#3ACCEPTED0.08 s1details
#4ACCEPTED0.08 s1details
#5ACCEPTED0.09 s1details
#6--2details
#7--2details
#8ACCEPTED0.71 s2details
#9ACCEPTED0.74 s2details
#10ACCEPTED0.78 s2details
#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
..**..
**....
*...*.
..*...
'''

n, m, k = map(int, input().split())

def laske(x, y, x2, y2, p, laskettavat, kr, ks):
    '''laske pisteestä (x, y) alas ja oikealle sijoittuvat sopivat tontit'''
    maara = 0
    haara_x2 = None
    tasa_nahty = False

    while p <= k:
        if p < k:
            haara_x2 = x2
            haara_y2 = y2
            haara_p = p
        elif p == k:
            maara += 1
            if not tasa_nahty:
                haara_x2 = x2
                haara_y2 = y2
                haara_p = p
                tasa_nahty = True

        if x2 == m or y2 == n:
            break

        x2 += 1
        y2 += 1
        # lisää oikea reuna, myös alakulma
        p += ks[y2][x2] - ks[y - 1][x2]
        # lisää alareuna, ei alakulmaa
        p += kr[y2][x2 - 1] - kr[y2][x - 1]

    if haara_x2:
        if x == haara_x2:
            # 1x1 tontti
            if y == 1 and x < m:
                # haaraudu oikealle (vain ylärivistä)
                haara_x2 = x + 1
                p_oik = kr[y][haara_x2] - kr[y][haara_x2 - 1]
                laskettavat.append((haara_x2, y, haara_x2, y, p_oik))
            # haaraudu alas
            if y < n:
                haara_y2 = y + 1
                p_alas = ks[haara_y2][x] - ks[haara_y2 - 1][x]
                laskettavat.append((x, haara_y2, x, haara_y2, p_alas))
        else:
            if y == 1:
                # haaraudu oikealle (vain ylärivistä)
                # leikkaa puumäärästä vasen ja alarivi pois
                p_oik = haara_p - ks[haara_y2][x]
                p_oik -= kr[haara_y2][haara_x2] - kr[haara_y2][x] # ei vas. alakulmaa
                laskettavat.append((x + 1, y, haara_x2, haara_y2 - 1, p_oik))
            # haaraudu alas
            # leikkaa puumäärästä oikea ja ylärivi pois
            p_alas = haara_p - (ks[haara_y2][haara_x2] - ks[y][haara_x2]) # ei oik. yläkulmaa
            p_alas -= kr[y][haara_x2] - kr[y][x - 1]
            laskettavat.append((x, y + 1, haara_x2 - 1, haara_y2, p_alas))

    return maara

def sopivia_tontteja(p, kum_riv, kum_sar):
    maara = 0
    laskettavat = [(1, 1, 1, 1, kum_riv[1][1])]
    while laskettavat:
        x1, y1, x2, y2, p = laskettavat.pop()
        maara += laske(x1, y1, x2, y2, p, laskettavat, 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():
    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: ACCEPTED

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

correct output
94

user output
94

Test 2

Group: 1

Verdict: ACCEPTED

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

correct output
0

user output
0

Test 3

Group: 1

Verdict: ACCEPTED

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

correct output
4

user output
4

Test 4

Group: 1

Verdict: ACCEPTED

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

correct output
16

user output
16

Test 5

Group: 1

Verdict: ACCEPTED

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

correct output
30

user output
30

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

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

correct output
288

user output
288

Test 9

Group: 2

Verdict: ACCEPTED

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

correct output
786

user output
786

Test 10

Group: 2

Verdict: ACCEPTED

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

correct output
1763

user output
1763

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)