Rezultati

Up. imeNalogaJezikRezultatČas oddaje
JayZCrew Prijateljske besede Python 3 100/100OK 20. apr '17 @ 19:01

Test Točke Porabljen spomin Porabljen čas Status
#1 12/12 8,668 MiB 0,000 s OK
#2 12/12 8,730 MiB 0,000 s OK
#3 12/12 9,828 MiB 0,000 s OK
#4 12/12 9,715 MiB 0,000 s OK
#5 13/13 9,625 MiB 0,000 s OK
#6 13/13 9,613 MiB 0,000 s OK
#7 13/13 9,664 MiB 0,000 s OK
#8 13/13 9,699 MiB 0,000 s OK

Ocenjevani program (nikj.py):
import sys
import bisect

def druzabnik(b1,b2):
    if b1[:3] == b2[:3]:
        return True
    elif b1[-3:] == b2[-3:]:
        return True
    return False

N = sys.stdin.readline().strip()
N = int(N)
inord = []
postord = []
Besede = list()
for i in range(N):
    B = sys.stdin.readline().strip()
    Besede.append(B)
    inord.append((B[:3],i))
    postord.append((B[-3:],i))

inord.sort()
postord.sort()


friends = set([0])
krog = set([0])

while len(krog) > 0:
    novkrog = set()
    for ind in krog:
        zac3 = Besede[ind][:3]
        najdi = bisect.bisect_left(inord, (zac3, ind))
        levo = najdi
        while levo >= 0 and inord[levo][0] == zac3:
            if inord[levo][1] not in friends:
                friends.add(inord[levo][1])
                novkrog.add(inord[levo][1])
            levo -= 1
        desno = najdi
        while desno < N and inord[desno][0] == zac3:
            if inord[desno][1] not in friends:
                friends.add(inord[desno][1])
                novkrog.add(inord[desno][1])
            desno += 1
        kon3 = Besede[ind][-3:]
        najdi2 = bisect.bisect_left(postord, (kon3, ind))
        levo = najdi2
        while levo >= 0 and postord[levo][0] == kon3:
            if postord[levo][1] not in friends:
                friends.add(postord[levo][1])
                novkrog.add(postord[levo][1])
            levo -= 1
        desno = najdi2
        while desno < N and postord[desno][0] == kon3:
            if postord[desno][1] not in friends:
                friends.add(postord[desno][1])
                novkrog.add(postord[desno][1])
            desno += 1
    krog = novkrog

print(len(friends))