#!/usr/bin/env python3 def closest_prev(_counts, target): """ Funkce, která vrátí lexikograficky nejbližší nižší řetězec pro řetězec target, který jde poskládat z písmenek v _counts. Přičemž: - _counts je pole délky 26, kde _counts[0] = počet dostupných Aček, _counts[1] = počet dostupných Bček atd. - target je pole obsahujcí cílový řetězec nasekaný na znaky a převedený na čísla 0–25. """ out = [] # Nakopírujeme počty písmenek, abychom je mohli upravovat, ale neměnil jsme původní pole counts = _counts[:] def use(c): """Použije zadané písmenko a přidá ho na výstup.""" assert counts[c] > 0 counts[c] -= 1 out.append(c) def unuse(): """Odpoužije momentálně poslední písmenko na výstupu.""" c = out.pop() counts[c] += 1 def nonempty(): """Vrátí seznam všech písmenek abecedy (kódovaných jako 0–25), kterých máme momentálně k dispozici nenulový počet.""" return [i for i, count in enumerate(counts) if count > 0] # enumerate(pole) vrací postupně (0, pole[0]), (1, pole[1]), … # Dokud můžeme, používáme stejná písmenka jako vstupní řetězec. for c in target: if counts[c] <= 0: break use(c) # Buď jsme zvládli vyrobit celý řetězec… if len(out) == len(target): return out # …nebo ne, takže se snažíme vyrobit nejbližší menší. To znamená vzít teď # nejbližší menší písmenko a pak hladově brát vždy to největší, co ještě # máme k dispozici. (Nejbližší menší řetězec k kspcaaa je kspbzzz.) # Jenže co když žádné menší písmenko k dispozici nemáme? Pak musíme # backtrackovat, dokud taková situace nenastane. # Backtracking, dokud s daným prefixem neumíme vyrobit menší řetězec. for i in range(len(out), -1, -1): c = target[i] if min(nonempty()) < c: break if len(out) == 0: # Jsme tak zoufalí, že bychom chtěli zkracovat prázdný řetězec, # protože žádná z předchozích možností nevyšla. To znamená, že # žádný menší řetězec nejde vyrobit. return None unuse() # filter dostane funkci a pole a vrátí všechny prvky v poli, pro které # funkce vrací True. Tady je funkce zapsaná pomocí lambda výrazu, ale # ekvivalentní by bylo napsat filter(je_vetsi, nonempty()) a předtím # zadefinovat: # def je_vetsi(x): # return x < c largest_smaller = max(filter(lambda x: x < c, nonempty())) use(largest_smaller) # A teď už jen hladově bereme co největší písmenka. while len(out) < len(target): use(max(nonempty())) return out def closest_next(_counts, _target): """Podobně jako closest_next, ale tentokrát vrací nejbližší vyšší řetězec od _target.""" # Trik je prostý: obrátíme celou abecedu (prohodíme a <-> z, b <-> y, …), # tam najdeme nejbližší nizší řetězec (což už umíme) a pak výsledek zase # obrátíme zpátky. def flip(l): return [25 - x for x in l] # Pokud jsme měli k dispozici x Aček, v obráceném problému máme k dispozici # x Ztek. counts = list(reversed(_counts)) target = flip(_target) flipped_out = closest_prev(counts, target) return flip(flipped_out) def intify(s): """Převede řetězec z písmen anglické abecedy na seznam čísel 0–25.""" # funkce ord(znak) vrací číslo odpovídající ASCII hodnotě znaku znak. Malá # anglická abeceda je v ASCII tabulce uložená souvisle, takže např. # ord("e") = ord("a") + 5 return [ord(c) - ord("a") for c in s] def stringify(l): """Inverzní funkce k intify, převede seznam čísel 0–25 na řetězec.""" # Funkce chr je inverzní k ord, tj. vrací znak na dané pozici ASCII tabulky. return "".join(chr(i + ord("a")) for i in l) counts = [int(x) for x in input().split()] N = int(input()) target = intify(input()) out = closest_prev(counts, target) if out is None: out = closest_next(counts, target) # Aspoň jedním směrem dostaneme platný výsledek. assert out is not None print(stringify(out))