Dowód wzoru, który podał Wojtek:

Załóżmy, że |A| >= |B|. Jeśli mamy monotoniczny przedział w A, to jasne, że trzeba pomiędzy niego wstawić co najmniej tyle elementów B, ile powiedział Wojtek, żeby go podzielić na odpowiednio krótkie przedziały.

Jeśli mamy rosnące trzy elementy w A: a1 < a2 < a3, to możemy je zawsze rozdzielić dowolnym elementem b, żeby było < > <. Jeśli b < a2, to robimy: a1 < a2 > b < a3. Jeśli b > a2, to robimy: a1 < b > a2 < a3.

Jeśli nam zostaną nadmiarowe elementy w B, to parujemy je z ostatnimi elementami w A, i robimy tak, żeby końcówka zawsze była na zmianę < > < > < > . Załóżmy na przykład, że mamy ciąg, który kończy się ... < a1 i teraz chcemy wstawić dwa dodatkowe elementy a2, b2 na koniec. Jeśli min(a2, b2) < a1, to robimy: < a1 > min(a2, b2) < max(a2, b2). Jeśli min(a2, b2) > a1, to robimy: < a2 > a1 < b2.

Potwierdzam

!= np

Mniej więcej 2s (i u mnie, i na sio).

Potwierdzam i dzięki za dobre testy. Czasy tragiczne (rzędu 40 sekund). Jak czasy u Was?

Potwierdzam

Przeszedłem, więc testy są mocne. Niestety, nie zdałem 3b..

Potwierdzam wszystkie testy.

Potwierdzam

Już i tak siedziała

Ja wyszedłem z założenia, że może komuś dzięki niemu psycha siądzie, więc to nie takie oczywiste ;)

Potwierdzam, dobry test, przydał mi się wczoraj.

Ale ja go nie zapostowałem bo https://shorturl.at/jyLPR :)

Zapraszam do porównania. Test jest jeden.
https://easyupload.io/ilhno5

Potwierdzam i serdecznie dziękuję za mocne testy

Potwierdzam