Treść zadania

sonia16

Richard Feynman był naprawdę niezwykle fascynującym człowiekiem - otrzymał nagrodę Nobla w dziedzinie fizyki, rozszyfrowywał hieroglify Majów, grał sambę na bębnach podczas karnawału w Rio, rozkręcał też imprezę w studenckim klubie Hybrydy (oczywiście grając na perkusji i ucząc polskich studentów samby). Zajmował się również biologią, w ramach swoich biologicznych eksperymentów przeprowadził szereg bardziej i mniej poważnych badań na mrówkach :-)

My co prawda z fizyki jesteśmy raczej przeciętni, grać na perkusji nie umiemy zupełnie, a hieroglifów nie widzieliśmy na oczy lecz nic nie stoi na przeszkodzie żebyśmy poeksperymentowali z mrówkami! Nasz eksperyment zakłada, że weźmiemy garść mrówek i umieścimy je w jednowymiarowej przestrzeni. W przestrzeni tej będą się znajdowały co najmniej dwa otwory - na początku i końcu odcinka na jakim umieściliśmy owady. Oczywiście mrówki jako stworzenia pracowite nie znoszą stagnacji - od razu po umieszczeniu na placu eksperymentu zaczynają się poruszać ze stałą prędkością równą 1 polu na kolejkę. Chodzą chaotycznie w prawo lub lewo odbijając się od siebie w nieskończenie krótkim czasie. Pierwszą rzeczą jaką zaobserwowaliśmy jest to, że gdy mrówki wpadają na siebie, błyskawicznie zawracają i zaczynają iść w drugą stronę dopóki nie trafią na kolejną mrówkę idącą w przeciwnym kierunku lub nie wpadną do dołka. Oczywiście chcielibyśmy poprosić Cię o niewielką pomoc - napisz program, który na podstawie współrzędnych początkowych mrówek oraz dołków a także kierunku w jakim porusza się każda z mrówek w momencie 0 obliczy ile owadów wpadnie do danego dołka oraz po ilu kolejkach wpadnie ostatnia z nich (dla każdego z dołków). W momencie początkowym żadna z mrówek nie znajduje się w dołku, dwie mrówki nie mogą również znajdować się w tym samym punkcie. Oprócz tego żadne dwa dołki nie mogą być w bezpośrednim sąsiedztwie.

Wejście
W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 10) określająca liczbę zestawów danych.

W pierwszej linii każdego zestawu danych znajduje się liczba p (2 ≤ p ≤ 1000) określająca liczbę dołków, po której wypisane są współrzędne każdego z dołków. Dołki o najniższej i najwyższej współrzędnej określają rozmiar pola (1 ≤ współrzędna dołka ≤ 2 × 109). W drugiej linii każdego zestawu znajduje się liczba n (0 ≤ n ≤ 300000) określająca ile mrówek w chwili 0 przemieszcza się w prawo. Po liczbie n wypisanych jest n liczb – są to współrzędne każdej z mrówek idących w prawo w chwili startu. W kolejnej linii analogicznie opisane są mrówki idące w lewo. Współrzędne dołków oraz mrówek podane są w kolejności rosnącej.

Wyjście
Dla każdego zestawu danych należy w osobnej linii wypisać ile mrówek wpadnie do danego dołka i po jakim czasie do tego dołka wpadnie ostatnia z nich. Wyniki dla poszczególnych dołków wypisujemy zgodnie z kolejnością na wejściu.

Przykład
Wejście:

1
3
1 8 17
6
2 3 5 11 12 13
5
4 6 7 9 10

Wyjście:

3 6
5 6
3 6

PODAJ DWA PRZYKLADY DAM NAJ

Zadanie jest zamknięte. Autor zadania wybrał już najlepsze rozwiązanie lub straciło ono ważność.

Rozwiązania

  • antekL1

    Przykład 1.
    Wejście:
    1
    3
    1 5 7
    2
    2 6
    1
    4

    Symulacja ( d, D - dołek, o - puste pole, > mrówka w prawo, < - mrówka w lewo)
    1 2 3 4 5 6 7
    d > o < d > d (chwila 0)
    d < o > d o D (mrówka wpadła do dołka na pozycji 7, mrówki odbiły się na polu 3)
    D o o o D o D (dwie mrówki wpadły do dołków na pozycjach 1 i 5)

    Wyjście
    1 2 (1 mrówka wpadła do dołka w pozycji 1 w chwili 2)
    1 2 (1 mrówka wpadła do dołka w pozycji 5 w chwili 2)
    1 1 (1 mrówka wpadła do dołka w pozycji 7 w chwili 1)
    =======================

    Przykład 2.
    Wejście:
    1
    2
    1 9
    1
    4
    1
    8

    Symulacja ( d, D - dołek, o - puste pole, > mrówka w prawo, < - mrówka w lewo)
    1 2 3 4 5 6 7 8 9
    d o o > o o o < d (chwila 0)
    d o o o > o < o d (chwila 1)
    d o o o < o > o d (chwila 2, mrówki zderzyły się na pozycji 6)
    d o o < o o o > d (chwila 3)
    d o < o o o o o D (chwila 4, mrówka zdołowana w drugim dołku)
    d < o o o o o o d (chwila 5)
    D o o o o o o o d (chwila 6, mrówka zdołowana w pierwszym dołku)

    Wyjście
    1 6 (1 mrówka wpadła do lewego dołka w chwili 6)
    1 4 (1 mrówka wpadła do prawego dołka w chwili 4)
    =======================

    Programu pisać mi się nie chciało, ale fajnie by wyglądał na ekranie :)

    • UWAGA:
      Przyjąłem takie założenie w symulacji, bo zadanie tego nie precyzuje)
      ( d, D - dołek, o - puste pole, > mrówka w prawo, < - mrówka w lewo)
      a)
      Jeśli mrówki w poprzednim kroku były w pozycji oddalonej o 1 dołek:
      o o o > o < o o o (przed)
      to w obecnej chwili zrobiłyby krok w przód, zderzyły się na środkowej pozycji i znajdują się w pozycjach oddalonych o 1 dołek, bo w jednym punkcie może być tylko jedna mrówka.
      o o o < o > o o o (po)
      b)
      Jeżeli mrówki w poprzednim kroku były tuż obok siebie:
      o o o > < o o o
      to w chwili obecnej zderzyłyby się i przeszłyby przez siebie, ale nie mogą, więc od razu robią krok wstecz.
      o o < o o > o o
      Jednak lepszym rozwiązaniem byłoby po prostu odwrócenie ruchu mrówek, czyli:
      o o o < > o o o
      bo poprzednie rozwiązanie może prowadzić do konfliktów przy dużym zagęszczeniu mrówek. Z drugiej strony mrówki nie wykonują wtedy żadnego kroku.

      Nie wykorzystuję zresztą w przykładach tej sytuacji.

Podobne materiały

Przydatność 50% Ein Komponist - Richard Strauss

Richard Strauss wurde am 11. Juni 1864 in Mnchen geboren. Sein Vater Franz Strauss war erster Hornist am Hoforchester Mnchen, seine Mutter Josephine stammte aus der Bierbrauer-Dynastie Pschorr, eine reichste Familie in Mnchen. Als er 4 Jahre war,begann er einen Unterricht des Spiels auf dem Klavier.Zwei Jahre spater fing auf den Geigen zu komponieren an. Nach er Ludwigs-Gymnasium in Monachium...

Przydatność 65% Papkin - postać niezwykle zabawna

Uważam, że Papkin jest postacią zabawną. Z całą pewnością mogę stwierdzić, iż spełnia on w „Zemście” rolę szczególną. Czytelnik od razu dostrzega, że jest postacią najmniej serio, najbardziej przerysowaną. Choć od jego osoby nigdy nie zaczynają się żadne działania, to jest kluczową postacią w prawie wszystkich dramatycznych momentach. Kolejnym argumentem, który...

Przydatność 100% 12 Wartości - Linda, Richard Eyre.

12 WARTOŚCI – Linda, Richard Eyre Trzeba uczyć wartości, w jaki sposób? – odpowiedź daje szkoła amerykańska: Eyrowie Eyrowie twierdzą, że zaraz po jedzeniu, ubieraniu, nauczanie wartości jest najważniejszą powinnością rodziców wobec dzieci, bo wartości nadają życiu sens. Udzie z różnych kultur i religii wg. Eyrów okazywali się zgodni w chęci uczenia dzieci...

Przydatność 50% To była naprawde śmieszna przygoda - opowiadanie

Ferie zimowe to czas kiedy mozna poznac wielu ludzi i przezyc mnóstwo niezapomnianych przygód. Taka wlasnie niezapomnianą przygode przezylem w ubiegłym roku roku. Wraz z przyjaciólmi wyjechalismy w góry. Nasze schronisko znajdowalo sie w małej miejscowości 40 km od Zakopanego. Było tam bardzo malowniczo. Na poczatku naszego pobytu wszystko bylo spokojnie, dopóki jeden z mieszkanców...

Przydatność 80% Współczesna młodzież - jaka jest naprawde

Wydaje mi się, że współczesnej młodzieży brakuje zapału do robienia rzeczy naprawdę ważnych i wartościowych. Bardzo szybko gubią tę właściwą drogę po której powinni iść. Obserwując swoich rówieśników uważam, że większość z nich nie potrafi odnaleźć w sobie czegoś co pozwoliło by im myśleć o sobie jako o osobach wartościowych. Szukają łatwego zarobku nie...

0 odpowiada - 0 ogląda - 1 rozwiązań

Dodaj zadanie

Zobacz więcej opcji