Tartaki
Limit pamięci: 32 MB
We wsi Bajtowo wszystkie gospodarstwa są położone po jednej stronie
bardzo długiej drogi, gdyż po jej drugiej stronie znajduje się Bajtocki
Park Narodowy i tam gospodarstw budować nie wolno.
Wójt wsi postanowił wpłynąć pozytywnie na jej rozwój (a co za tym
idzie na zawartość swojego portfela) i przekształcić ją w potentata branży
meblowej.
Dlatego też wybudowano tyle samo tartaków co gospodarstw we wsi, wszystkie
oczywiście przy jedynej we wsi drodze.
Wójt postanowił, że każdy tartak będzie dostarczał drewno jednemu, ściśle
dla niego określonemu gospodarstwu, które będzie produkować z tego
drewna meble.
Wójt natrafił jednak na problem natury logistycznej - brakowało możliwości
transportu drewna, gdyż jedyna wiejska droga była zbyt ruchliwa i
niebezpieczna.
Dlatego też postanowił wybudować drogi, które będą łączyły tartaki z
gospodarstwami (jeden tartak ma być połaczony z jednym gospodarstwem).
Drogi te ze względów bezpieczeństwa nie mogą się przecinać; ponadto
mogą one przebiegać wyłącznie po jednej stronie głównej wiejskiej drogi,
nie mogą wkraczać na teren parku narodowego.
Ponieważ wójt ma problemy z takim połączeniem tartaków z gospodarstwami
w pary, aby dało się żądany układ dróg wytyczyć, poszukuje informatyka,
który mu w tym pomoże (a już wkrótce będzie go mógł sowicie wynagrodzić!).
Czy skusisz się i pomożesz wójtowi?
Zadanie
Napisz program który:
- wczyta ze standardowego wejścia położenia tartaków i gospodarstw
przy drodze,
- wyznaczy pewne przyporządkowanie tartaków gospodarstwom, w którym
da się poprowadzić żądany układ dróg,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita
(), oznaczająca liczbę gospodarstw we wsi.
Drugi wiersz zawiera jeden napis o długości , złożony wyłącznie
z liter g i t, oznaczający układ gospodarstw
i tartaków przy drodze.
Droga biegnie w kierunku wschód-zachód, układ gospodarstw i tartaków
podany jest w kierunku z zachodu na wschód, a park położony
jest na południe od drogi (patrz też rysunek przykładowy).
Wyjście
Jeśli szukane przyporządkowanie nie istnieje, Twój program powinien
wypisać na standardowe wyjście jedno słowo . W przeciwnym
razie powinien wypisać wierszy. Każdy z nich powinien zawierać
parę liczb całkowitych, oddzielonych
pojedynczym odstępem i oznaczających numer gospodarstwa i numer tartaku,
które powinny być połączone drogą.
Gospodarstwa numerujemy w kierunku z zachodu na wschód liczbami od do
(tartaki podobnie; gospodarstwa i tartaki mają oddzielną numerację).
Jeżeli istnieje więcej niż jedno poprawne przyporządkowanie, Twój program
powinien wypisać dowolne z nich.
Przykład
Dla danych wejściowych:
3
gtggtt
poprawną odpowiedzią jest:
2 1
1 3
3 2
Przykładowe połączenie gospodarstw (czarne kółka) i tartaków (białe kółka)
drogami.
Uwaga: Istnienie ,,odstępów'' między gospodarstwami i tartakami a główną drogą
służy tylko lepszemu zilustrowaniu sytuacji - w rzeczywistości gospodarstwa
i tartaki leżą tuż przy drodze i nie można prowadzić drogi między którymkolwiek
gospodarstwem czy tartakiem a główną drogą.
Autor zadania: Jakub Radoszewski.