Runda 20 [Hard] - Bokserzy
17.05.2011 - Damian Rusak
Zadanie tygodnia runda 20; kategoria Hard Limit czasowy: 5s; Limit pamięciowy: 128MB BokserzyNadchodzi czas wielkich mistrzostw jednej z niezliczonych federacji bokserskich. Ta federacja szczyci się tym, że walki na jej mistrzostwach są absolutnie uczciwe - nikt nie sprzedaje walk, liczą się tylko umiejętności. Perfekcja i niezawodność zawodników doprowadziła jednak do tego, że wyniki każdej walki są do przewidzenia - każdemu zawodnikowi można przypisać pewną liczbę - obrazującą poziom jego umiejętności. Jeśli w walce mierzą się dwaj zawodnicy, zwycięża zawsze ten, któremu przypisana liczba jest większa. W przypadku równych poziomów walka kończy się remisem. Widzowie jednak nie znają zawodników dobrze i ich poziom jest dla nich tajemnicą. Zachodzą w głowę, jakie mogłyby być wyniki spotkań. Pytają Ciebie (znanego promotora) o możliwe osiągi pewnych bokserów. Bokserom przydzielono przed mistrzostwami numery od do . Pytania są postaci : "Gdyby zawodnik walczył z każdym z zawodników z przedziału od do (włącznie) to z iloma by wygrał, a z iloma zremisował?". Aby zwiększyć zainteresowanie mistrzostwami pomóż im szybko poznać odpowiedź! Wejście: Pierwsza linia wejścia zawiera jedną liczbę - liczbę zawodników (). W kolejnej linii znajduje się liczb całkowitych , , ... , - liczb obrazujących umiejętności kolejnych zawodników. (). W kolejnej linii znajduje się liczba - liczba zapytań. (). W kolejnych liniach znajdują się trójki liczb , - oznaczających, że pytamy o wynik walki zawodnika o numerze ze wszystkimi zawodnikami z przedziału . (). Wyjście: Dla każdego kolejnego zapytania na wyjściu powinny znaleźć się dwie liczby całkowite - odpowiednio liczba zawodników z zadanego przedziału z którymi wygrałby zawodnik oraz liczba zawodników z którymi zremisowałby. Oczywiście nie należy wliczać do odpowiedzi (trudnego do wyobrażenia) pojedynku zawodnika samego ze sobą, o ile należy on do przedziału z zapytania. Przykład: Wejście: 6 3 5 2 4 4 4 3 2 4 6 6 3 6 3 1 2 Wyjście: 3 0 1 2 0 0 Wyjaśnienie: W pierwszym zapytaniu zawodnik ma poziom umiejętności , zatem zwycięża ze wszystkim zawodnikami z przedziału , nie remisując z nikim. W drugim zapytaniu zawodnik nie walczy z samym sobą, ale zwycięża z zawodnikiem nr i remisuje z zawodnikami i . W trzecim zapytaniu zawodnik nr przegrywa z oboma zawodnikami z zadanego przedziału.
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto. |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com