|
|
| Line 1: |
Line 1: |
| == Cerința ==
| |
| Într-un depozit, mărfurile sunt aranjate pe rafturi sub formă de șiruri de caractere. Mărfurile trebuie rearanjate astfel încât fiecare caracter să fie adiacent în șirul rearanjat doar dacă exista o cale în graf între cele două caractere inițial. Să se determine o rearanjare validă a șirului de caractere pe baza conexiunilor date.
| |
| == Date de intrare ==
| |
| Programul citește de la tastatură:
| |
|
| |
|
| Un șir de caractere s reprezentând mărfurile pe rafturi.
| |
| Un număr întreg m reprezentând numărul de conexiuni între caractere.
| |
| O listă de m perechi de caractere reprezentând conexiunile din graf.
| |
| == Date de ieșire ==
| |
| Pe ecran se va afișa un șir de caractere rearanjat conform conexiunilor din graf. Dacă nu există nicio rearanjare validă, se va afișa mesajul "Rearanjare imposibilă".
| |
| == Restricții și precizări ==
| |
| *1 ⩽ lungime sir '''s''' ⩽ 100
| |
| *1 ⩽ '''m''' ⩽ 100
| |
| * Toate caracterele din sirul 's' sunt distincte.
| |
| == Exemplu 1 ==
| |
| ;Intrare
| |
| abc <br>
| |
| 2<br>
| |
| a b<br>
| |
| b c
| |
|
| |
| ;Iesire
| |
| cba
| |
| == Exemplu 2 ==
| |
| ;Intrare
| |
| abcdef<br>
| |
| 3<br>
| |
| a b<br>
| |
| c d<br>
| |
| e f
| |
|
| |
| ;Iesire
| |
| Rearanjare imposibilă
| |
|
| |
| == Rezolvare ==
| |
| <syntaxhighlight lang="python" line>
| |
| from collections import defaultdict, deque
| |
|
| |
| def citeste_date():
| |
| try:
| |
| s = input("Introduceți șirul de caractere: ")
| |
| m = int(input("Introduceți numărul de conexiuni: "))
| |
| conexiuni = []
| |
| for _ in range(m):
| |
| conexiune = input().strip().split()
| |
| conexiuni.append(conexiune)
| |
| return s, m, conexiuni
| |
| except ValueError:
| |
| return None, None, None
| |
|
| |
| def construieste_graf(s, conexiuni):
| |
| graf = defaultdict(list)
| |
| for u, v in conexiuni:
| |
| graf[u].append(v)
| |
| graf[v].append(u)
| |
| return graf
| |
|
| |
| def bfs(graf, start, vizitat):
| |
| coada = deque([start])
| |
| componenta = []
| |
| vizitat.add(start)
| |
|
| |
| while coada:
| |
| nod = coada.popleft()
| |
| componenta.append(nod)
| |
| for vecin in graf[nod]:
| |
| if vecin not in vizitat:
| |
| vizitat.add(vecin)
| |
| coada.append(vecin)
| |
|
| |
| return componenta
| |
|
| |
| def rearanjeaza_caractere(s, conexiuni):
| |
| graf = construieste_graf(s, conexiuni)
| |
| vizitat = set()
| |
| componente = []
| |
|
| |
| for caracter in s:
| |
| if caracter not in vizitat:
| |
| componenta = bfs(graf, caracter, vizitat)
| |
| componente.append(componenta)
| |
|
| |
| rezultat = []
| |
| for componenta in componente:
| |
| if len(componenta) == 1:
| |
| rezultat.append(componenta[0])
| |
| else:
| |
| sub_sir = ''.join(componenta)
| |
| for caracter in s:
| |
| if caracter in sub_sir:
| |
| sub_sir = sub_sir.replace(caracter, '')
| |
| sub_sir = caracter + sub_sir
| |
| rezultat.append(sub_sir)
| |
|
| |
| rearanjat = ''.join(rezultat)
| |
|
| |
| if sorted(rearanjat) != sorted(s):
| |
| return "Rearanjare imposibilă"
| |
| return rearanjat
| |
|
| |
| def main():
| |
| s, m, conexiuni = citeste_date()
| |
|
| |
| if s is None or m is None or conexiuni is None:
| |
| print("Datele de intrare nu corespund restricțiilor impuse.")
| |
| return
| |
|
| |
| rezultat = rearanjeaza_caractere(s, conexiuni)
| |
| print(rezultat)
| |
|
| |
| if __name__ == "__main__":
| |
| main()
| |
|
| |
| </syntaxhighlight>
| |
