Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_04_13 - Drzewo genealogiczne |
Ogłoszenie
Na potrzeby Bajtockiego Systemu Ewidencji (BSE), firma FRAKTAX zajmująca się tworzeniem programu, poszukuje dobrych programistów do współpracy. Jednym z kryteriów przyjęcia, jest zapoznanie się z problemem oraz dobra znajomość jakiegoś języka programowania. Inne wymagania to znajomość języka angielskiego, umiejętność pracy w zespole oraz poczucie humoru. Mile widziane doświadczenie w parzeniu kawy oraz w opowiadaniu dowcipów. A oto problem, jaki powinien rozwiązać kandydat.
Należy stworzyć drzewo genealogiczne pewnej rodziny zamieszkującej Bajtocję. Liczba potomków w danym pokoleniu dla kolejnych ojców (matek) jest definiowana według ciągu. Oznacza to, że pierwszy potomek ma a1 potomków, drugi a2 itd. Czynność tą powtarzamy cyklicznie. Tzn. jeśli są trzy wyrazy ciągu, to czwarty ojciec (matka) będzie miał (miała) a1 potomków itd. Dla każdego potomka podane są trzy informacje: numer pokolenia (liczymy od zera), numer potomka (liczymy od jeden) oraz jego imię (maksymalnie 10 znaków). Niestety nie wszystkich przodków można było odnaleźć, więc w to miejsce zamiast imienia wpisujemy znak zapytania. Może się zdarzyć także taka sytuacja, że dana informacja zostanie zaktualizowana, tzn., że imię dla danej osoby może zostać podmienione na inne. Napisz program, który rozwiąże problem i zacznij pracować w najlepiej płatnej firmie "FRAKTAX".
Wejście
W pierwszym wierszu liczba n określająca długość ciągu wyznaczającego liczbę potomków dla danego rodzica (n < 1000).
W drugim wierszu n liczb naturalnych zawierających się w przedziale [1..3].
W kolejnym wierszu jedna liczba p określająca liczbę osób, które będzie budowało drzewo genealogiczne (p < 100 001). Następnie p wierszy w postaci trzech informacji pokolenie, potomek, imię, gdzie 0 ≤ pokolenie ≤ 20, potomek to numer potomka w n-tym pokoleniu oraz imię to imię złożone z co najmniej 3 i maksymalnie 10 znaków.
Wyjście
Dla każdego wpisania danej osoby do drzewa genealogicznego należy wypisać wszystkich jego przodków odzielając ich "->" (patrz przykład). Jeśli po drodze jakieś imię nie zostało jeszcze wstawione to wypisujemy w tym miejscu znak "?".
Przykład
Wejście: 4 3 1 2 3 8 0 1 Bitek 1 3 Bajtek 2 6 Bibuszka 3 11 Bibitka 3 13 Bajtoslaw 3 1 Bibi 10 1236 Bitkos 0 1 Bibek Wyjście: Bitek Bitek->Bajtek Bitek->Bajtek->Bibuszka Bitek->Bajtek->?->Bibitka Bitek->Bajtek->Bibuszka->Bajtoslaw Bitek->?->?->Bibi Bitek->?->?->?->?->?->?->?->?->?->Bitkos Bibek
Dodane przez: | Marcin Kasprowicz |
Data dodania: | 2015-07-15 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |