F - TrhovníciČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Na medzinárodný čarodejnícky trh prišlo n obchodníkov. Každý obchodník vlastní jeden unikátny predmet a na trhu by ho chcel vymeniť za iný. Poznáme postupnosť a1,a2,...,an, ktorej hodnota ai znamená, že i-ty čarodejník by chcel získať predmet čarodejníka ai. Vieme, že o každý predmet má záujem práve jeden obchodník. Aby sa predišlo podvodom, dvaja obchodníci si medzi sebou vymieňajú tovar vždy z ruky do ruky, tj. povolené sú len výmeny medzi dvoma obchodníkmi. Naviac, každý obchodník smie v jeden deň spraviť maximálne jednu výmenu, no celkový počet výmen počas trhov nie je limitovaný. ÚlohaUrčte minimálny počet dní, ktoré musia trvať čarodejnícke trhy tak, aby každý obchodník získal požadovaný predmet. Váš program má tiež vypísať ľubovoľný plán výmen, ktorý realizuje takýto počet dní.VstupPrvý riadok vstupu obsahuje kladné celé číslo n, (1≤n≤5000). V druhom riadku je daná postupnosť čísel a1,a2,...,an. Hodnota ai znamená, že čarodejník i chce získať predmet, ktorý na začiatku vlastnil čarodejník ai.VýstupPrvý riadok výstupu určuje minimálny počet dní m. Ďalšie riadky výstupu určujú ľubovoľný rozvrh výmen obchodníkov. Tj. každý z nasledujúcich m riadkov určuje transakcie vykonané v jednom dni: prvé číslo riadku určuje celkový počet transakcií. Za ním vypíšte dvojice obchodníkov (oddelených znakom '-'), ktoré si v tomto dni vymenia svoj tovar.PríkladVstup:5 3 5 1 2 4 Výstup:2 2 1-3 2-5 1 2-4 |