Rezultati

Up. imeNalogaJezikRezultatČas oddaje
muzik-2018 Alkani Python 3 100/100OK 13. okt '18 @ 15:38

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 12,793 MiB 0,378 s OK
#2 5/5 13,445 MiB 0,023 s OK
#3 5/5 13,395 MiB 0,135 s OK
#4 5/5 13,324 MiB 0,099 s OK
#5 5/5 13,305 MiB 0,115 s OK
#6 5/5 11,855 MiB 0,000 s OK
#7 5/5 13,477 MiB 0,038 s OK
#8 5/5 13,309 MiB 0,018 s OK
#9 5/5 13,461 MiB 0,038 s OK
#10 5/5 13,477 MiB 0,079 s OK
#11 5/5 13,375 MiB 0,079 s OK
#12 5/5 13,309 MiB 0,043 s OK
#13 5/5 13,488 MiB 0,125 s OK
#14 5/5 13,344 MiB 0,155 s OK
#15 5/5 10,871 MiB 0,000 s OK
#16 5/5 11,020 MiB 0,000 s OK
#17 5/5 10,879 MiB 0,000 s OK
#18 5/5 11,090 MiB 0,000 s OK
#19 5/5 10,891 MiB 0,000 s OK
#20 5/5 10,887 MiB 0,000 s OK

Ocenjevani program (alkani.in.py):
import sys

#sys.stdin = open("alk.in")

from queue import deque

for line in sys.stdin:
    N, M = map(int, line.split())
    break

data = [list(line.strip()) for line in sys.stdin]


class Node:
    def __init__(self, uid, i, j):
        self.children = []
        self.uid = uid
        self.i = i
        self.j = j
        self.ma = 0
    def __str__(self):
        return str(self.__dict__)

    def __repr__(self):
        return "NODE()"
        return "Node(" + str(self) + ")"


radi = "metan", "etan", "propan", "butan", "pentan", "heksan", "heptan", "oktan", "nonan", "dekan", "undekan", "dodekan"
nums_pre = "","di", "tri", "tetra", "penta", "heksa", "hepta", "okta", "nona", "deka", "undeka", "dodeka"
radi2 = [ra.replace("an", "il") for ra in radi]

nnu = list(radi)
nnu.sort()

def parse_one(i,j):
    graph = []
    uid = 0
    stack = []
    data[i][j] = "x"
    stack.append(Node(uid,i,j))
    graph.append(stack[0])
    uid += 1
    while stack:
        top= stack.pop()
        i = top.i
        j = top.j
        if i > 0 and data[i-1][j] == "|":
            data[i-1][j] = "x"
            data[i-2][j] = "x"
            nn = Node(uid, i-2, j)
            nn.children.append(top)
            top.children.append(nn)
            stack.append(nn)
            graph.append(nn)
            uid += 1
        if i + 1 < N and data[i+1][j] == "|":
            data[i+1][j] = "x"
            data[i+2][j] = "x"
            nn = Node(uid, i+2, j)
            nn.children.append(top)
            top.children.append(nn)
            stack.append(nn)
            graph.append(nn)
            uid += 1
        if j > 0 and data[i][j-1] == "-":
            data[i][j-1] = "x"
            data[i][j-2] = "x"
            nn = Node(uid, i, j-2)
            nn.children.append(top)
            top.children.append(nn)
            stack.append(nn)
            graph.append(nn)
            uid += 1

        if j +1< M and data[i][j+1] == "-":
            data[i][j+1] = "x"
            data[i][j+2] = "x"
            nn = Node(uid, i, j+2)
            nn.children.append(top)
            top.children.append(nn)
            stack.append(nn)
            graph.append(nn)
            uid += 1

    #print(len(graph), uid)
    ma = 0
    cur_f = None
    cur_l = None
    cur_par = []
    # find longest
    if len(graph) == 1:
        return "metan"
    for node in graph:
        if len(node.children) == 1:
            visited = [0 for j in range(uid)]
            depths = [0 for j in range(uid)]
            par = [None for j in range(uid)]
            q = deque()
            q.append([node.children[0], 2])
            par[node.children[0].uid] = node

            visited[node.uid] = 1
            while q:
                ne, dep = q.popleft()
                depths[ne.uid] = dep
                visited[ne.uid] = 1
                for nn in ne.children:
                    if not visited[nn.uid]:
                        par[nn.uid] = ne
                        q.append([nn, dep+1])
            if dep > ma:
                #print("here")
                #print(par)
                ma = dep
                cur_f = node
                cur_l = ne
                cur_par = par
    #
    #print(cur_f)
    #print(cur_l)
    #print(cur_par)
    # Retrace:
    cur_l.ma = 1
    cc_l = cur_l
    #print(cur_par)
    while 1:
        ne = cur_par[cc_l.uid]
        if ne.uid == cur_f.uid:
            break
        ne.ma = 1
        cc_l = ne

    sub_d = []
    sub_d2 = []
    #print(cur_f, cur_l)

    # Search
    cc_f = cur_f.children[0]
    cur_f.ma = 1
    dst = 2
    visited = [0 for j in range(uid)]
    visited[cur_f.uid] = 1
    visited[cc_f.uid] = 1
    while 1:
        visited[cc_f.uid] = 1
        if len(cc_f.children) == 1:
            break
        for ne in cc_f.children:
            if not ne.ma:
                cu = ne
                visited[cu.uid] = 1
                lee = 1
                while 1:
                    for ccc in cu.children:
                        if not visited[ccc.uid]:
                            visited[ccc.uid] = 1
                            lee += 1
                            cu = ccc
                            break
                    if len(cu.children) == 1:
                        break
                sub_d.append([dst, lee])
                sub_d2.append([ma-dst+1, lee])

        for ne in cc_f.children:
            if ne.ma and not visited[ne.uid]:
                cc_f = ne
        dst += 1

    ##
    #print(sub_d)
    fst = list(sorted([j[0] for j in sub_d]))
    snd = list(sorted([j[0] for j in sub_d2]))
    #print(fst, snd)
    if fst < snd:
        pass
    elif fst == snd:
        nom1 = [radi[j[1]] for j in sorted(sub_d)]
        nom2 = [radi[j[1]] for j in sorted(sub_d2)]
        if nom1 < nom2:
            sub_d = sub_d2
    else:
        sub_d = sub_d2
    #print(sub_d)
    nums = [0 for j in range(len(radi)+3)]
    for (i, nn) in sub_d:
        nums[nn] += 1
    #print(nums)
    #print(nnu)
    full = []
    for sample in nnu:
        sam_num = radi.index(sample) + 1


        if nums[sam_num]:
            ali = []
            prefix = nums_pre[nums[sam_num]-1]
            #print(radi2[sam_num-1], sam_num, nums[sam_num], prefix)
            for (i, nn) in sub_d:
                if nn == sam_num:
                    ali.append(i)
            ali.sort()
            to = ",".join(map(str, ali)) + "-" + prefix + radi2[sam_num-1]
            full.append(to)
    if full:
        return "-".join(full)      + "-" + radi[ma-1]
    return radi[ma-1]

result = []

for i in range(len(data)):
    for j in range(len(data[i])):
        if data[i][j] == "C":
            result.append(parse_one(i,j))

from collections import Counter

cc = Counter(result)
ll = []
for (i,j ) in cc.items():
    ll.append([-j,i])

ll.sort()
for nummm, name in ll:
    print(str(-nummm) + "x " + name)
#result.sort(key=lambda x: (-x[0], x[1]))