Rezultati

Up. imeNalogaJezikRezultatČas oddaje
zerodays-2018 Alkani Python 3 0/100Napačen odgovor (WA) 13. okt '18 @ 14:46

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 77,770 MiB 2,904 s OK
#2 5/5 20,914 MiB 0,248 s OK
#3 5/5 22,512 MiB 0,284 s OK
#4 5/5 22,551 MiB 0,325 s OK
#5 5/5 21,945 MiB 0,285 s OK
#6 5/5 14,176 MiB 0,000 s OK
#7 5/5 22,023 MiB 0,295 s OK
#8 5/5 22,035 MiB 0,320 s OK
#9 5/5 22,059 MiB 0,339 s OK
#10 5/5 22,906 MiB 0,386 s OK
#11 5/5 21,840 MiB 0,285 s OK
#12 5/5 22,031 MiB 0,366 s OK
#13 5/5 23,074 MiB 0,406 s OK
#14 5/5 23,359 MiB 0,441 s OK
#15 5/5 9,000 MiB 0,000 s OK
#16 5/5 9,078 MiB 0,000 s OK
#17 5/5 9,043 MiB 0,000 s OK
#18 0/5 9,230 MiB 0,000 s Napačen odgovor
Tvoj izhod:
​3x 3,3,4,4,5,5,6,7,7,9,9-undekametil-dodekan
2x 3,3,4,4,5,5,6,7,7,9,9,10-dodekametil-dodekan
1x 10-metil-dodekan
1x 3,3,4,4,5,5,6,7,9,9-dekametil-dodekan
1x 3,3,4,4,5,5,6,9,9-nonametil-dodekan
1x 3,3,4,4,5,5,6,9-oktametil-dodekan
1x 3,3,4,4,5,5,6-heptametil-dodekan
Pravilen izhod:
​3x 3,3,4,4,5,5,6,7,7,9,9-undekametil-dodekan
2x 3,3,4,4,5,5,6,7,7,9,9,10-dodekametil-dodekan
1x 3,3,4,4,5,5,6,7,9,9-dekametil-dodekan
1x 3,3,4,4,5,5,6,9,9-nonametil-dodekan
1x 3,3,4,4,5,5,6,9-oktametil-dodekan
1x 3,3,4,4,5,5,6-heptametil-dodekan
1x 3,4,4,5,5,6-heksametil-dodekan
#19 5/5 9,137 MiB 0,000 s OK
#20 5/5 9,086 MiB 0,000 s OK

Ocenjevani program (alkani.py):
from collections import deque, defaultdict

verige = {
    1: 'met',
    2: 'et',
    3: 'prop',
    4: 'but',
    5: 'pent',
    6: 'heks',
    7: 'hept',
    8: 'okt',
    9: 'non',
    10: 'dek',
    11: 'undek',
    12: 'dodek'
}

predpone = {
    1: '',
    2: 'di',
    3: 'tri',
    4: 'tetra',
    5: 'penta',
    6: 'heksa',
    7: 'hepta',
    8: 'okta',
    9: 'nona',
    10: 'deka',
    11: 'undeka',
    12: 'dodeka'
}

miza = []
n, m = map(int, input().split())

for _ in range(n):
    miza.append(list(input()))

seen = set()

def dodej_v_graf(x, y, x1, y1, graf, ne_nadaljuj=False):
    if (x, y) not in graf:
        graf[(x, y)] = set()

    graf[(x, y)].add((x1, y1))

    # druga smer
    if not ne_nadaljuj:
        dodej_v_graf(x1, y1, x, y, graf, ne_nadaljuj=True)


def nafuki_verigo(x, y, graf):
    global seen, miza

    if (x, y) in seen:
        return graf
    
    seen.add((x, y))

    if (x, y) not in graf:
        graf[(x, y)] = set()
    
    # gor
    if y > 1 and miza[y-1][x] == '|':
        dodej_v_graf(x, y, x, y-2, graf)
        nafuki_verigo(x, y-2, graf)
        
    # dol
    if y < n - 2 and miza[y+1][x] == '|':
        dodej_v_graf(x, y, x, y+2, graf)
        nafuki_verigo(x, y+2, graf)        

    # desno
    if x < m - 2 and miza[y][x+1] == '-':
        dodej_v_graf(x, y, x+2, y, graf)
        nafuki_verigo(x+2, y, graf)

    # levo
    if x > 1 and miza[y][x-1] == '-':
        dodej_v_graf(x, y, x-2, y, graf)
        nafuki_verigo(x-2, y, graf)

    return graf
    
def najd_najdalsiga(graf):
    dolzina = 0
    najdaljsa_pot = None

    for c in graf.keys():
        if len(graf[c]) == 0:
            return [c]
        if len(graf[c]) != 1:
            continue

        q = deque()

        q.append((c, [c]))
        visited = defaultdict(bool)
        visited[c] = True

        while len(q) > 0:
            node, pot = q.popleft()

            if len(pot) > dolzina:
                najdaljsa_pot = pot
                dolzina = len(pot)

            for sosed in graf[node]:
                if not visited[sosed]:
                    visited[sosed] = True
                    q.append((sosed, pot + [sosed]))
            
    return najdaljsa_pot
        


def poimenuj_pravilno(graf, veriga):
    ime_verige = verige[len(veriga)] + 'an'

    siski1, kolicina_siskov1 = poimenuj_siske(graf, veriga)
    siski2, kolicina_siskov2 = poimenuj_siske(graf, veriga[::-1])

    s1 = [str(i) for i, j in siski1] + [j for i, j in siski1]
    s2 = [str(i) for i, j in siski2] + [j for i, j in siski2]

    if [s1, s2] == list(sorted([s1, s2])):
        siski, kolicina_siskov = siski1, kolicina_siskov1
    else:
        siski, kolicina_siskov = siski2, kolicina_siskov2

    # siski, kolicina_siskov = sorted([(siski1, kolicina_siskov1), (siski2, kolicina_siskov2)])[0]

    rezultat = []

    imena = set(map(lambda x: x[1], siski))
    for ime in sorted(imena):
        kok = kolicina_siskov[ime]
        predpona = predpone[kok]
        
        pozicije = map(str, sorted([i for i, j in siski if j == ime]))
        pozicije = ','.join(pozicije)

        rezultat.append('{}-{}{}'.format(pozicije, predpona, ime))

    rezultat.append(ime_verige)
    return '-'.join(rezultat)




def dolzina_siska(graf, veriga, node):
    seen = set()
    
    for povezava in graf[node]:
        if povezava not in veriga:
            trenutn = povezava
            seen.add(trenutn)
            break
    
    while True:
        povezava = graf[trenutn]
        

def dolzina_siska(graf, start, prej):
    for sosed in graf[start]:
        if sosed != prej:
            return 1 + dolzina_siska(graf, sosed, start)
    return 1

# [(kje, ime priveska)]
def poimenuj_siske(graf, veriga):
    siski = []
    kolicina_siskov = defaultdict(int)
    for i, c in enumerate(veriga):
        if len(graf[c]) <= 2:
            continue
        for sosed in graf[c]:
            if sosed not in veriga:
                d = dolzina_siska(graf, sosed, c)
                if d > 0:
                    ime = verige[d] + 'il'
                    siski.append((i+1, ime))
                    kolicina_siskov[ime] += 1
    return siski, kolicina_siskov



grafi = []

for y in range(n):
    for x in range(m):
        if miza[y][x] == 'C':
            g = nafuki_verigo(x, y, {})
            if len(g) != 0:
                grafi.append(g)

use = defaultdict(int)

for graf in grafi:
    veriga = najd_najdalsiga(graf)
    ime = poimenuj_pravilno(graf, veriga)
    use[ime] += 1

for k in sorted(use.items(), key=lambda x: (-x[1], x[0])):
    ime, kok = k
    print('{}x {}'.format(kok, ime))