Editing 3058 - vip (section)

= Exemplul 1: =
<code>vipIN.txt</code>
 2 
 8 6 
 corleone 
 vasilica 
 5 2 
 marko 
 ghita
<code>vipOUT.txt</code>
 caaliisv 
 -1

=== Explicație: ===
În primul set cea mai mică anagramă a șirului <code>vasilica</code>, din punct de vedere lexicografic, care diferă de șirul <code>corleone</code> pe exact <code>6</code> poziții, este <code>caaliisv</code> În al doilea set nici una din anagramele șirului <code>ghita</code> nu poate să difere pe exact două poziții de șirul <code>marko</code>.

== Exemplul 2: ==
<code>vipIN.txt</code>
 2 
 80000000000 6
 corleone 
 vasilica 
 5 2 
 marko 
 ghita
<code>vipOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_intrare(nume_fisier):
    with open(nume_fisier, 'r') as f:
        t = int(f.readline().strip())
        cazuri = []
        for _ in range(t):
            n, k = map(int, f.readline().strip().split())
            s1 = f.readline().strip()
            s2 = f.readline().strip()
            cazuri.append((n, k, s1, s2))
    return cazuri

def verifica_invariant(freq1, freq2, egali, diferiti, sigma=26):
    nevoie_extra_op = 0
    max_extra = 0
    for i in range(1, sigma + 1):
        extra_car = freq1[i] + freq2[i] - diferiti
        extra_op = (extra_car + 1) // 2
        if extra_op > min(freq1[i], freq2[i]):
            return False
        max_extra += min(freq1[i], freq2[i])
        if extra_op > 0:
            nevoie_extra_op += extra_op
    return nevoie_extra_op <= egali and egali <= max_extra

def rezolva_caz(n, k, s1, s2):
    freq1 = [0] * 27
    freq2 = [0] * 27
    answer = [''] * (n + 1)

    for char in s1:
        freq1[ord(char) - ord('a') + 1] += 1
    for char in s2:
        freq2[ord(char) - ord('a') + 1] += 1

    egali = n - k
    diferiti = k

    if not verifica_invariant(freq1, freq2, egali, diferiti):
        return "-1"

    for i in range(1, n + 1):
        freq1[ord(s1[i-1]) - ord('a') + 1] -= 1
        for j in range(1, 27):
            if freq2[j] == 0:
                continue
            freq2[j] -= 1
            if ord(s1[i-1]) - ord('a') + 1 == j:
                egali -= 1
            else:
                diferiti -= 1

            if verifica_invariant(freq1, freq2, egali, diferiti):
                answer[i] = chr(j + ord('a') - 1)
                break

            if ord(s1[i-1]) - ord('a') + 1 == j:
                egali += 1
            else:
                diferiti += 1

            freq2[j] += 1

    return ''.join(answer[1:])

def scrie_iesire(nume_fisier, rezultate):
    with open(nume_fisier, 'w') as f:
        for rez in rezultate:
            f.write(f"{rez}\n")

def verifica_restricții(cazuri, nume_fisier_iesire):
    suma_n = sum(caz[0] for caz in cazuri)  # Suma tuturor valorilor lui N
    if not all(1 <= caz[0] <= 100000 and 1 <= caz[1] <= 100000 for caz in cazuri) or suma_n > 1000000:
        with open(nume_fisier_iesire, 'w') as f:
            f.write("Datele nu corespund restrictiilor impuse\n")
        return False
    return True

def main():
    cazuri = citeste_intrare("vipIN.txt")
    if not verifica_restricții(cazuri, "vipOUT.txt"):
        return  # Oprește execuția dacă datele nu corespund restricțiilor
    
    rezultate = []
    for caz in cazuri:
        rezultate.append(rezolva_caz(*caz))
    scrie_iesire("vipOUT.txt", rezultate)

if __name__ == "__main__":
    main()

</syntaxhighlight>