29 ianuarie 2019

Codejam for Women - 2018 - ex3

A treia problemă propusă de acest Codejam: Centrists


Trei politicieni candidează pentru niște alegeri. Numele/poreclele lor sunt distincte, dar au aceeași lungime.
Ei sunt preocupați de ordinea în care intră la vorbitor - ei știu că mereu vor intra dupa o ordine alfabetică necunoscută.
Văzând că cel care intră nici primul nici ultimul are mai mult succes, candidații sunt preocupați să existe cel puțin un alfabet prin care numele lor va ajunge la mijlocul listei.
Astfel, dându-se numele lor, se cere să se afle cine va fi întotdeauna dezavantajat - candidatul al cărui nume este imposibil să fie așezat la jumătatea listei, conform oricărui alfabet.
// Alfabetul reprezintă o ordonare a tuturor literelor care apar în numele candidaților

-----

Idee:
Pentru 3 candidați vor exista întotdeauna 6 ordini posibile în care pot fi așezați.
Pentru fiecare ordine, se extrag reguli de precedență ale literelor în alfabet, conform așezării numelor lor. Dacă una din reguli este inversul alteia deja salvate, înseamnă că acea ordine nu este posibilă și cel care se află la mijloc în acea ordonare (imposibilă) este un candidat dezavantajat.

Ex.
Nume: BCB, CAB, CBC
Pentru ordonarea [CAB, BCB, CBC] regulile extrase sunt C>B (C înaintea lui B), apoi B>C care contrazice regula anterioară. Deci BCB nu se poate afla la mijloc, conform niciunui alfabet.

-----

outputFile = open("ex3.out", 'w')

def isRuleAccepted(rules, char1, char2):
    if str(char2+char1) in rules:
        return False
    return True


def addRule(rules, char1, char2):
    # char1 comes before char2
    if str(char1+char2) not in rules and char1 != char2:
        rules.append(str(char1+char2))


def findIfPossible(L, names, rules): 
    if L == 0:
        return True

    if len(names) == 3 and names[0][0] == names[1][0] and names[1][0] == names[2][0]:
        if L > 0:
            return findIfPossible(L-1, [x[1:] for x in names], rules)
        else:
            # all names are equal
            return True

    if isRuleAccepted(rules, names[0][0], names[1][0]):
        addRule(rules, names[0][0], names[1][0])
    else:
        return False

    if len(names) == 3:
        if isRuleAccepted(rules, names[1][0], names[2][0]):
            addRule(rules, names[1][0], names[2][0])
        else:
            return False
 
    if names[0][0] == names[1][0]:
        return findIfPossible(L-1, [names[0][1:], names[1][1:]], rules)
 
    if len(names) == 3 and names[1][0] == names[2][0]:
        return findIfPossible(L-1, [names[1][1:], names[2][1:]], rules)

    return True


def solve(L, names):

    result = ["YES", "YES", "YES"]
    orderings = [[0,1,2], [0,2,1], [1,2,0], [1,0,2], [2,1,0], [2,0,1]]

    for order in orderings:
        rules = []  # list of "ab" where a is before b in the alphabet
        newNamesOrdering = [names[order[0]], names[order[1]], names[order[2]]]
        if not findIfPossible(L, newNamesOrdering, rules):
            result[order[1]] = "NO"

    return result[0] + " " + result[1] + " " + result[2]


with open("C-large-practice.in", "r") as myFile:
    T = eval(myFile.readline()) 
    for case in range(T):

        L = eval(myFile.readline())
        names = [k.replace("\n","") for k in myFile.readline().split(' ')]

        line = "Case #" + str(case+1) + ": " + solve(L, names) + "\n"
        #print(line)
        outputFile.write(line)

myFile.close()
outputFile.close()

Niciun comentariu: