Treść zadania
Autor: sonia16 Dodano: 10.3.2013 (13:11)
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
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ń
0 0
antekL1 11.3.2013 (11:08)
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 :)
Dodawanie komentarzy zablokowane - Zgłoś nadużycie
antekL1 11.3.2013 (11:26)
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.