CSES - Putka Open 2015 – 4/6 - Results
Submission details
Task:Labyrintti
Sender:
Submission time:2015-10-11 16:35:37 +0300
Language:Python3
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.09 s1details
#2ACCEPTED0.10 s1details
#3ACCEPTED0.08 s1details
#4ACCEPTED0.10 s1details
#5ACCEPTED0.08 s1details
#6--2details
#7--2details
#8--2details
#9--2details
#10--2details
#110.08 s3details
#120.08 s3details
#130.08 s3details
#140.09 s3details
#150.08 s3details

Code

from itertools import cycle

y1, x1, y2, x2 = map(int, input().split())

if max(abs(x) for x in (y1, x1, y2, x2)) > 500:
    print(1)
    exit()

seinat = set()
seinat.add((0, 0))
y, x = 0, 0
suunnat = ((0, 1), (-1, 0), (0, -1), (1, 0))
suunnat_toisto = cycle(suunnat)
p = 1
while max(abs(y), abs(x)) <= 500:
    dy, dx = next(suunnat_toisto)
    for i in range(2 ** p):
        y += dy
        x += dx
        seinat.add((y, x))
    p += 1

n = 1
edell = set([(y1, x1)])
saav = set()
while True:
    nyk = set()
    for y, x in edell:
        for dy, dx in suunnat:
            uusi = (y + dy, x + dx)
            if max(abs(d) for d in uusi) > 500:
                continue
            if uusi == (y2, x2):
                print(n)
                exit()
            if uusi in saav or uusi in seinat:
                continue
            nyk.add(uusi)
            saav.add(uusi)
    edell = nyk
    n += 1        

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
6 -1 8 -2

correct output
3

user output
3

Test 2

Group: 1

Verdict: ACCEPTED

input
-8 2 8 -9

correct output
27

user output
27

Test 3

Group: 1

Verdict: ACCEPTED

input
3 2 -5 -1

correct output
13

user output
13

Test 4

Group: 1

Verdict: ACCEPTED

input
4 4 2 7

correct output
5

user output
5

Test 5

Group: 1

Verdict: ACCEPTED

input
-5 4 -6 -3

correct output
8

user output
8

Test 6

Group: 2

Verdict:

input
-156 226 -9 7

correct output
438

user output
(empty)

Test 7

Group: 2

Verdict:

input
403 265 10 0

correct output
1100

user output
(empty)

Test 8

Group: 2

Verdict:

input
146 462 9 -3

correct output
1160

user output
(empty)

Test 9

Group: 2

Verdict:

input
223 82 -1 5

correct output
725

user output
(empty)

Test 10

Group: 2

Verdict:

input
1 390 -5 2

correct output
436

user output
(empty)

Test 11

Group: 3

Verdict:

input
-540305713988379 -580514137141...

correct output
1233409841814111

user output
1

Test 12

Group: 3

Verdict:

input
-156703691254895 -816797859965...

correct output
1086091541904259

user output
1

Test 13

Group: 3

Verdict:

input
-438806811971369 -748477242640...

correct output
1299874045296142

user output
1

Test 14

Group: 3

Verdict:

input
939351840049839 -9541207461566...

correct output
2118652567575152

user output
1

Test 15

Group: 3

Verdict:

input
-840127817790022 1113515308437...

correct output
1007774343975947

user output
1