Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_18_12 - Nocna zmiana |
Dostałeś zadanie przygotować grafik na nocne zmiany w fabryce. Nikt nie lubi pracować w nocy, więc żeby uniknąć wszelkich dyskusji przydzieliłeś pracowników na dyżury po kolei zgodnie z ich numerami pracowniczymi (od 1 do n). Dodatkowo masz do dyspozycji pewną liczbę pracowników kontraktowych, którzy mogą pracować w określone noce.
Przykładowy grafik na kolejne noce wygląda tak:
1 2 0 0 3
0 oznacza pracownika kontraktowego, pozostałe liczby - pracowników firmy.
W ostatniej chwile dostałeś informację, że pracownicy kontraktowi muszą przyjść w inne dni. Przygotowałeś drugi grafik zgodnie z nowymi wytycznymi:
0 1 2 0 3
Teraz musisz powiadomić pracowników firmy o zaistniałej zmianie. Musisz powiadomić tylko tych, dla których nastąpiła zmiana w grafiku. Dodatkowo dzwoniąc po kolei do każdego z nich musisz się upewnić, że kolejność dyżurów pracowników jest cały czas taka sama (pracownik z numerem 10 nie może znaleźć się przed pracownikiem z numerem 9 lub niższym, a także nie może się znaleźć za pracownikiem z numerem 11 i większym).
Na każdym etapie informowania pracowników, porządek dyżurów musi być zachowany!
W powyższym przykładzie należy poinformować o dwóch zmianach. Najpierw musisz poinformować pracownika z numerem 2 o zmianie z drugiego na trzeci dyżur (2 3). A następnie pracownika z numerem 1, że zamiast pojawić się na pierwszej zmianie, będzie pracował na drugiej (1, 2). Jeżeli najpierw powiadomimy pracownika z numerem 1, to otrzymamy nieprawidłowy grafik (2 1 0 0 3), dlatego taka kolejność jest nieprawidłowa.
Porządek dyżurów obowiązuje tylko pracowników firmy. Kolejność dyżurów pracowników kontraktowych nas nie interesuje.
Określ minimalną liczbę telefonów, jakie musisz wykonać oraz podaj kolejne zmiany, o których musisz poinformować pracowników.
Wejście
Na wejściu znajduje się liczba n - ilość dyżurów (n ≤ 2*105).
W kolejnych dwóch liniach znajduje się po n liczb ki (0 ≤ ki ≤ n) oznaczających numer pracownika, który będzie pracował na tej zmianie (ki = 0 dla pracownika kontraktowego, ki > 0 dla pracownika firmy).
Pierwsza linia zawiera początkowy grafik. Druga linia zawiera nowo otrzymany grafik. Oba wejściowe grafiki są prawidłowe i zawierają tyle samo dyżurów dla pracowników kontraktowych.
Numery pracowników przydzielonych do określonych dni są kolejnymi liczbami naturalnymi (zaczynając od 1). Jeżeli jest 10 dni w grafiku i 4-ech pracowników kontraktowych, to w grafiku pojawią się pracownicy o numerach: 1, 2, 3, 4, 5 i 6.
Wyjście
Na wyjściu należy wypisać ile najmniej zmian należy wykonać, żeby przekształcić pierwszy grafik w drugi.
Następnie należy podać kolejne zmiany między którymi dyżurami należy zamienić przydzielonych do nich pracowników, aby ostatecznie otrzymać nowy grafik.
Dyżury numerujemy wg ich kolejności na wejściu od 1 do n.
Uwaga! Podając kolejne rotacje wypisujemy pozycje w grafiku między którymi dokonujemy zamiany, a nie numery pracowników, którym zmieniamy dyżury. Każda poprawna kolejność zmian będzie zaakceptowana.
Przykład 1
Wejście:
5 1 2 0 0 3 0 1 2 0 3
Wyjście:
2 2 3 1 2
Przykład 2
Wejście:
10 1 2 3 0 0 0 4 5 6 7 0 0 1 2 3 4 5 6 7 0
Wyjście (jedno z wielu prawidłowych i akceptowalnych rozwiązań):
7 3 5 7 6 4 2 1 3 8 7 9 8 10 9
Dodane przez: | Grzegorz Spryszyński |
Data dodania: | 2023-12-30 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |