W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Dany jest szablon wyrażenia arytmetycznego zawierający cztery podstawowe działania, nawiasy oraz miejsca na liczby. Na przykład (x*x)/(x+x) jest szablonem.
Wartościowaniem nazwiemy takie wstawienie liczb rzeczywistych do szablonu, że wartość powstałego w ten sposób wyrażenia jest określona. Wstawiając w kolejne miejsca powyższego przykładu, uzyskujemy wyrażenie o wartości , natomiast wstawienie nie jest wartościowaniem.
Jeśli zbiory wartościowań szablonów i są takie same oraz dla każdego wartościowania wyrażenia powstałe z i mają takie same wartości oraz szablon powstaje przez dodawanie i/lub usuwanie nawiasów z szablonu , to mówimy, że szablony te są równoważne. Na przykład szablony (x*x)/(x+x) i x*x/(x+x) są równoważne. Szablony (x*x)/(x+x) i x*x/x+x nie są równoważne, bo wartościowanie daje wyrażenia o wartościach i . Szablony x-(x-x) i x-x+x nie są równoważne, bo nie można jednego sprowadzić do drugiego przez dodawanie i usuwanie nawiasów.
Zadanie polega na znalezieniu szablonu o minimalnej liczbie nawiasów, równoważnego danemu szablonowi.
Mnożenie i dzielenie mają ten sam priorytet, większy niż dodawanie i odejmowanie; zatem mnożenie i dzielenie jest wykonywane przed dodawaniem i odejmowaniem. Dodawanie i odejmowanie mają ten sam priorytet. Operacje o tym samym priorytecie są wykonywane od lewej do prawej.
W pierwszym wierszu wejścia znajduje się liczba oznaczająca liczbę wyrażeń. W kolejnych wierszach znajdują się niepuste, poprawne szablony składające się ze znaków +, -, *, /, (, ) i x (miejsca na liczby). Suma długości wszystkich wyrażeń jest nie większa niż .
Na wyjściu należy wypisać wierszy. W -tym wierszu należy wypisać szablon równoważny -temu szablonowi z wejścia, zawierający minimalną liczbę nawiasów.
Dla danych wejściowych:
2 x+(x+(x+x)-(x*x))/x (x*x)/((x*x))+(x)
poprawną odpowiedzią jest:
x+(x+x+x-x*x)/x x*x/(x*x)+x
Autor zadania: Tomasz Idziaszek.