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()
