CSES - Datatähti 2016 peili

Submission details
Task:	Tontti
Sender:	konstikas
Submission time:	2015-10-04 01:51:24 +0300
Language:	Python3
Status:	READY
Result:	0

Feedback
subtask	verdict	score
#1	RUNTIME ERROR	0
#2	RUNTIME ERROR	0
#3	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	subtask
#1	RUNTIME ERROR	0.08 s	1	details
#2	WRONG ANSWER	0.08 s	1	details
#3	WRONG ANSWER	0.09 s	1	details
#4	WRONG ANSWER	0.09 s	1	details
#5	RUNTIME ERROR	0.09 s	1	details
#6	RUNTIME ERROR	0.28 s	2	details
#7	RUNTIME ERROR	0.26 s	2	details
#8	WRONG ANSWER	0.40 s	2	details
#9	RUNTIME ERROR	0.40 s	2	details
#10	RUNTIME ERROR	0.41 s	2	details
#11	TIME LIMIT EXCEEDED	--	3	details
#12	TIME LIMIT EXCEEDED	--	3	details
#13	TIME LIMIT EXCEEDED	--	3	details
#14	TIME LIMIT EXCEEDED	--	3	details
#15	TIME LIMIT EXCEEDED	--	3	details

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][1] if x == 1 else kum_sar[1][x]
    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:
            # kavennetaan tonttia vasemmasta yläkulmasta
            # xxx    xxx   ...
            # xxx -> .xx + .xx
            # xxx    .xx   .xx
            x += 1
            y += 1
            # vasen pystysivu pois, ilman yläkulmaa
            puita_nyt -= kum_sar[y2][x - 1] - kum_sar[y - 1][x - 1]
            # yläsivu pois, myös yläkulma
            puita_nyt -= kum_riv[y - 1][x2] - kum_sar[y - 1][x - 2]
    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

Subtask: 1

Verdict: RUNTIME ERROR

input
`10 10 1 ......... ......... ....... ....*.... ...` view save

correct output
`94` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 79, in <module>
    main()
  File "input/code.py", line 76, in main
    print(sopivia_tontteja(k, kum_rivit, kum_sarakkeet))
  File "input/code.py", line 56, in sopivia_tontteja
    maara += viistorivin_osumat(1, y, p, kum_riv, kum_sar)
  File "input/code.py", line 44, in viistorivin_osumat
    puita_nyt -= kum_sar[y2][x - 1] - kum_sar[y - 1][x - 1]
IndexError: list index out of range

Test 2

Subtask: 1

Verdict: WRONG ANSWER

input
`10 10 5 ******** ****** ****** ******** ...` view save

correct output
`0` view save

user output
`6` view save

Test 3

Subtask: 1

Verdict: WRONG ANSWER

input
`10 10 10 *......* ...*.. ...*...* ...... ...` view save

correct output
`4` view save

user output
`5` view save

Test 4

Subtask: 1

Verdict: WRONG ANSWER

input
`10 10 5 ***...... ....* .......* ....**.. ...` view save

correct output
`16` view save

user output
`17` view save

Test 5

Subtask: 1

Verdict: RUNTIME ERROR

input
`10 10 2 .... ........ .**....* *... ...` view save

correct output
`30` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 79, in <module>
    main()
  File "input/code.py", line 76, in main
    print(sopivia_tontteja(k, kum_rivit, kum_sarakkeet))
  File "input/code.py", line 56, in sopivia_tontteja
    maara += viistorivin_osumat(1, y, p, kum_riv, kum_sar)
  File "input/code.py", line 44, in viistorivin_osumat
    puita_nyt -= kum_sar[y2][x - 1] - kum_sar[y - 1][x - 1]
IndexError: list index out of range

Test 6

Subtask: 2

Verdict: RUNTIME ERROR

input
`500 500 1 .................................` view save

correct output
`9552040` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 79, in <module>
    main()
  File "input/code.py", line 76, in main
    print(sopivia_tontteja(k, kum_rivit, kum_sarakkeet))
  File "input/code.py", line 54, in sopivia_tontteja
    maara += viistorivin_osumat(x, 1, p, kum_riv, kum_sar)
  File "input/code.py", line 44, in viistorivin_osumat
    puita_nyt -= kum_sar[y2][x - 1] - kum_sar[y - 1][x - 1]
IndexError: list index out of range

Test 7

Subtask: 2

Verdict: RUNTIME ERROR

input
`500 500 5 .................................` view save

correct output
`1536063` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 79, in <module>
    main()
  File "input/code.py", line 76, in main
    print(sopivia_tontteja(k, kum_rivit, kum_sarakkeet))
  File "input/code.py", line 54, in sopivia_tontteja
    maara += viistorivin_osumat(x, 1, p, kum_riv, kum_sar)
  File "input/code.py", line 44, in viistorivin_osumat
    puita_nyt -= kum_sar[y2][x - 1] - kum_sar[y - 1][x - 1]
IndexError: list index out of range

Test 8

Subtask: 2

Verdict: WRONG ANSWER

input
`500 500 25000 *......*......*........` view save

correct output
`288` view save

user output
`309` view save

Test 9

Subtask: 2

Verdict: RUNTIME ERROR

input
`500 500 12500 ............***........` view save

correct output
`786` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 79, in <module>
    main()
  File "input/code.py", line 76, in main
    print(sopivia_tontteja(k, kum_rivit, kum_sarakkeet))
  File "input/code.py", line 56, in sopivia_tontteja
    maara += viistorivin_osumat(1, y, p, kum_riv, kum_sar)
  File "input/code.py", line 44, in viistorivin_osumat
    puita_nyt -= kum_sar[y2][x - 1] - kum_sar[y - 1][x - 1]
IndexError: list index out of range

Test 10

Subtask: 2

Verdict: RUNTIME ERROR

input
`500 500 5000 ...*.........*.......` view save

correct output
`1763` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 79, in <module>
    main()
  File "input/code.py", line 76, in main
    print(sopivia_tontteja(k, kum_rivit, kum_sarakkeet))
  File "input/code.py", line 56, in sopivia_tontteja
    maara += viistorivin_osumat(1, y, p, kum_riv, kum_sar)
  File "input/code.py", line 44, in viistorivin_osumat
    puita_nyt -= kum_sar[y2][x - 1] - kum_sar[y - 1][x - 1]
IndexError: list index out of range

Test 11

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 2000 1 .................................` view save

correct output
`489611392` view save

user output
(empty)

Test 12

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 2000 5 .................................` view save

correct output
`120725884` view save

user output
(empty)

Test 13

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 2000 400000 ........*......*...` view save

correct output
`1849` view save

user output
(empty)

Test 14

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 2000 200000 **.....................` view save

correct output
`2665` view save

user output
(empty)

Test 15

Subtask: 3

Verdict: TIME LIMIT EXCEEDED

input
`2000 2000 80000 ..........*.....*....` view save

correct output
`5587` view save

user output
(empty)

Datatähti 2016 peili

Tontti

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions (konstikas)