Logika kombinatoryka algorytmika Tomal: Dwie grupy żołnierzy podczas ćwiczeń na poligonie mają się wyminąć na belce długiej równoważni. Pierwsza grupa wchodzi na równoważnię z lewej strony, a druga – z prawej. Żołnierze każdej grupy poruszają się jeden za drugim. Od momentu, gdy żołnierze idący na przedzie każdej z grup spotkają się, rozpoczyna się manewr mijania. Zakładamy, że manewr mijania jest wykonywany synchronicznie, sekunda po sekundzie, tj. w każdej sekundzie mijają się wszystkie pary sąsiednich żołnierzy, którzy idą z różnych stron. Przyjmijmy, że jest n żołnierzy w pierwszej grupie, a w drugiej grupie żołnierzy jest m. Na jakiej pozycji w szeregu (licząc od lewej) znajdzie się k−ty żołnierz pierwszej grupy (licząc od czoła grupy) po t sekundach od spotkania się grup żołnierzy i rozpoczęcia manewru mijania? Zakładamy, że po t sekundach manewr mijania jeszcze się nie skończył. Na przykład, jeśli trzech żołnierzy z grupy pierwszej oznaczymy C,B,A (A to żołnierz na przedzie), a czterech żołnierzy z drugiej grupy oznaczymy U,X,Y,Z (U to żołnierz na przedzie), to po trzech sekundach mijania się na równoważni szereg żołnierzy będzie następujący: U,C,X,B,Y,A,Z. Pierwszy żołnierz pierwszej grupy znajduje się na pozycji 6. Prosze o pomoc.

wredulus_pospolitus: więc tak, założenia; t < max{n,m} <−−− bo mijanka się nie zakończyła 1) jeżeli (n−k) > t to jego pozycja będzie (n−k+1), ponieważ nie zdążył się nikt z nim minąć, 2) jeżeli (n−k) ≤ t oraz t≥m to pozycja będzie (n−k+1) + m, ponieważ wszyscy 'm' żołnierzy minęło już naszego żołnierzyka 3) jeżeli (n−k) ≤ t < m to pozycja będzie (n−k+1) + (t−k+1), ponieważ dokładnie (k−1) czasu musiało upłynąć, aby pierwszy żołnierz z drugiej kolumny staną twarzą w twarz z naszym żołnierzykiem, więc pozostało jedynie (t − (k−1)) = (t−k + 1) czasu za roszady ... więc dokładnie tylko żołnierzy drugiej grupy minie naszego żołnierzyka.

Tomal: ale spojrz na przyklad w zadaniu, podstawiajac do tego t−k+1 nie zgadza się.

wredulus_pospolitus: (n−k+1) + (t−k+1) <−−−− całość podstawiasz: n = 3; k = 1; t = 3 więc masz: 3−1+1 + 3 − 1 + 1 = 6

Tomal: a tak, moje niedopatrzenie dziekuje bardzo zerknałbyś jeszcze do tego o Jacku i Placku i o zuchach?

wredulus_pospolitus: pierwszy nawias oznacza 'ilu żołnierzy z MOJEJ grupy mam za swoimi plecami' i jest on stały, nie zależy od 't' (dlatego jest dla każdego 't' ) drugi nawias reprezentuje to ile żołnierzy drugiej grupy zdąży mnie minąć nim upłynie czas

Tomal: rozumiem , sam doszedlem do tego (n−k+1 +(t−k+1) czylui w tym drugim nawiasie przy jedynce mialem zly znak, tak blisko krążyłem a tak daleko jednak... Zerkniesz do tamtych jesli mozesz?

wredulus_pospolitus: Toć Jacka i Placka zrobiłem (od niego zacząłem) ... przecież ja dokładnie takie nawiasy napisałem jak ty o 16:35 więc nie wiem o co chodzi ze znakiem 'przy jedynce'

Tomal: aaa fakt ja w swoim zapisie mialem n−k+1 +t−k−1 stad bład.

wredulus_pospolitus: błąd w warunkach mam ... pomyśl nad nimi przez chwilę samodzielnie

Tomal: gdzie ten blad?