Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_18_12 - Nocna zmiana

Fabryka

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 ≤ kin) 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łowego50000B
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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.