CSES - Datatähti 2022 loppu

CSES - Datatähti 2022 loppu - Results

Submission details
Task:	Sokkelo
Sender:	okkokko
Submission time:	2022-01-22 19:37:38 +0200
Language:	PyPy3
Status:	READY
Result:	28

Feedback
group	verdict	score
#1	ACCEPTED	28
#2	RUNTIME ERROR	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.04 s	1, 2	details
#2	ACCEPTED	0.06 s	1, 2	details
#3	ACCEPTED	0.07 s	1, 2	details
#4	RUNTIME ERROR	0.15 s	2	details
#5	RUNTIME ERROR	0.14 s	2	details
#6	RUNTIME ERROR	0.14 s	2	details
#7	ACCEPTED	0.07 s	1, 2	details
#8	RUNTIME ERROR	0.18 s	2	details
#9	RUNTIME ERROR	0.69 s	2	details
#10	ACCEPTED	0.04 s	1, 2	details
#11	RUNTIME ERROR	0.14 s	2	details
#12	ACCEPTED	0.04 s	1, 2	details
#13	ACCEPTED	0.28 s	2	details
#14	ACCEPTED	0.04 s	1, 2	details
#15	ACCEPTED	0.31 s	2	details
#16	ACCEPTED	0.05 s	2	details
#17	ACCEPTED	0.07 s	2	details

Code

from itertools import product


def I():
    return map(int, input().split())


def main():
    n, m = I()  # y,x
    sokStr = [input() for _ in range(n)]

    def findPerson(person):
        for i in range(n):
            a = sokStr[i].find(person)
            if a != -1:
                return a, i
    Ax, Ay = findPerson("A")
    Bx, By = findPerson("B")
    sokkelo = [[1 if i == "#" else 0 for i in s] for s in sokStr]
    # wall is 1, A is 2, B is 3

    def isA(x, y):
        if 0 <= x < m and 0 <= y < n:
            return sokkelo[y][x] == 2
        return False

    mi = n + m  # ensimmäinen arvo on suurin mahdollinen (manhattan-etäisyys vastakkaisten kulmien välillä)

    def Diamond(x, y, d):
        "generates all coordinates whose manhattan distance to (x,y) is d"
        for i in range(d):
            yield (x + d - i, y + i)
            yield (x - d + i, y - i)
            yield (x + i, y - d + i)
            yield (x - i, y + d - i)

    def ClosestA(x, y, g):
        for d in (range(g - 1, g + 2) if g is not None else range(mi)):
            # käy läpi g-1,g,g+1
            if any(isA(ix, iy) for ix, iy in Diamond(x, y, d)):
                return d

    def updateMin(x, y, g):
        # g on lähin etäisyys A:n polkuun jonka viereinen kohta sai. Oma lähin etäisyys pitäisi poiketa tästä vain yhdellä
        nonlocal mi
        e = ClosestA(x, y, g)
        if e < mi:
            mi = e
        return e

    def markA(x, y):
        if not sokkelo[y][x]:
            sokkelo[y][x] = 2
            for a in (1, -1):
                if 1 <= x + a < m - 1:  # jokainen reunaruutu on seinää
                    markA(x + a, y)
                if 1 <= y + a < n - 1:
                    markA(x, y + a)

    def markB(x, y, g=None):
        # g on lähin etäisyys A:n polkuun jonka edellinen kohta sai. Oma lähin etäisyys pitäisi poiketa tästä vain yhdellä
        if not sokkelo[y][x]:
            sokkelo[y][x] = 3
            e = updateMin(x, y, g)
            for a in (1, -1):
                if 1 <= x + a < m - 1:  # jokainen reunaruutu on seinää
                    markB(x + a, y, e)
                if 1 <= y + a < n - 1:
                    markB(x, y + a, e)
    # try:
    markA(Ax, Ay)  # Virhe on täällä, virhe on RecursionError
    # except:
    #     pass
    if sokkelo[By][Bx] == 2:
        print(1)
        return
    # try:
    markB(Bx, By)
    # except:
    #     pass
    print(mi)
    return


if __name__ == "__main__":
    main()

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
`20 20 #################### #A.................# #..................# #..................# ...` view save

correct output
`1` view save

user output
`1` view save

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
`20 20 #################### #A.................# #..................# #..................# ...` view save

correct output
`2` view save

user output
`2` view save

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
`20 20 #################### #A.................# #..................# #..................# ...` view save

correct output
`9` view save

user output
`9` view save

Test 4

Group: 2

Verdict: RUNTIME ERROR

input
`1000 1000 ##############################...` view save

correct output
`1` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 86, in <module>
    main()
  File "input/code.py", line 71, in main
    markA(Ax, Ay)  # Virhe on t\xe4\xe4ll\xe4, virhe on RecursionError
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  [Previous line repeated 994 more times]
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  [Previous line repeated 890 more times]
  File "input/code.py", line 52, in markA
    if not sokkelo[y][x]:
RecursionError: maximum recursion depth exceeded

Test 5

Group: 2

Verdict: RUNTIME ERROR

input
`1000 1000 ##############################...` view save

correct output
`2` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 86, in <module>
    main()
  File "input/code.py", line 71, in main
    markA(Ax, Ay)  # Virhe on t\xe4\xe4ll\xe4, virhe on RecursionError
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  [Previous line repeated 994 more times]
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  [Previous line repeated 495 more times]
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  [Previous line repeated 339 more times]
  File "input/code.py", line 51, in markA
    def markA(x, y):
RecursionError: maximum recursion depth exceeded

Test 6

Group: 2

Verdict: RUNTIME ERROR

input
`1000 1000 ##############################...` view save

correct output
`335` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 86, in <module>
    main()
  File "input/code.py", line 71, in main
    markA(Ax, Ay)  # Virhe on t\xe4\xe4ll\xe4, virhe on RecursionError
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  [Previous line repeated 994 more times]
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  [Previous line repeated 328 more times]
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  [Previous line repeated 552 more times]
  File "input/code.py", line 52, in markA
    if not sokkelo[y][x]:
RecursionError: maximum recursion depth excee...

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
`20 20 #################### #####.############## ###.....############ ##.......########### ...` view save

correct output
`10` view save

user output
`10` view save

Test 8

Group: 2

Verdict: RUNTIME ERROR

input
`1000 1000 ##############################...` view save

correct output
`436` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 86, in <module>
    main()
  File "input/code.py", line 71, in main
    markA(Ax, Ay)  # Virhe on t\xe4\xe4ll\xe4, virhe on RecursionError
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  [Previous line repeated 196 more times]
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  [Previous line repeated 16 more times]
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  [Previous line repeated 6 more times]
  File "input/code.py", line 56, in markA
    markA(x...

Test 9

Group: 2

Verdict: RUNTIME ERROR

input
`1000 1000 ##############################...` view save

correct output
`2` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 86, in <module>
    main()
  File "input/code.py", line 78, in main
    markB(Bx, By)
  File "input/code.py", line 67, in markB
    markB(x + a, y, e)
  File "input/code.py", line 67, in markB
    markB(x + a, y, e)
  File "input/code.py", line 67, in markB
    markB(x + a, y, e)
  [Previous line repeated 994 more times]
  File "input/code.py", line 69, in markB
    markB(x, y + a, e)
  File "input/code.py", line 67, in markB
    markB(x + a, y, e)
  File "input/code.py", line 67, in markB
    markB(x + a, y, e)
  File "input/code.py", line 67, in markB
    markB(x + a, y, e)
  [Previous line repeated 879 more times]
  File "input/code.py", line 64, in markB
    e = updateMin(x, y, g)
  File "input/code.py", line 46, in updateMin
    e = ClosestA(x, y, g)
  File "input/code.py", line 38, in ClosestA
    for d in (range(g - 1, g + 2) if g is not None else range(mi)):
RecursionError: maximum recursion depth exceeded

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
`20 20 #################### #B................## #################.## #################.## ...` view save

correct output
`2` view save

user output
`2` view save

Test 11

Group: 2

Verdict: RUNTIME ERROR

input
`1000 1000 ##############################...` view save

correct output
`2` view save

user output
(empty)

Error:

Traceback (most recent call last):
  File "input/code.py", line 86, in <module>
    main()
  File "input/code.py", line 71, in main
    markA(Ax, Ay)  # Virhe on t\xe4\xe4ll\xe4, virhe on RecursionError
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  File "input/code.py", line 58, in markA
    markA(x, y + a)
  [Previous line repeated 993 more times]
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  File "input/code.py", line 56, in markA
    markA(x + a, y)
  [Previous line repeated 397 more times]
  File "input/code.py", line 54, in markA
    for a in (1, -1):
RecursionError: maximum recursion depth exceeded

Test 12

Group: 1, 2

Verdict: ACCEPTED

input
`20 20 #################### ##########A######### ##########.######### ##########.######### ...` view save

correct output
`2` view save

user output
`2` view save

Test 13

Group: 2

Verdict: ACCEPTED

input
`1000 1000 ##############################...` view save

correct output
`2` view save

user output
`2` view save

Test 14

Group: 1, 2

Verdict: ACCEPTED

input
`20 20 #################### ##########A######### ##########.######### ##########.######### ...` view save

correct output
`12` view save

user output
`12` view save

Test 15

Group: 2

Verdict: ACCEPTED

input
`1000 1000 ##############################...` view save

correct output
`502` view save

user output
`502` view save

Test 16

Group: 2

Verdict: ACCEPTED

input
`3 1000 ##############################...` view save

correct output
`1` view save

user output
`1` view save

Test 17

Group: 2

Verdict: ACCEPTED

input
`1000 3 ### #A# #.# #.# ...` view save

correct output
`1` view save

user output
`1` view save

Datatähti 2022 loppu

Sokkelo

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

Test 16

Test 17

Tasks

Submissions (okkokko)