Domácí kolo

H: Vesmírný řetěz

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Na oběžné dráze Ma-stry se v kruhu vyskytuje N vesmírných výzkumných stanic Mezinárodní Futuristické Flotily. Každá ze stanic provádí nějaký experiment, jehož výsledky chce v kontejneru poslat další stanici (ne nutně jiné). Každá stanice obdrží výsledky jednoho experimentu a zároveň odešle výsledky jednoho experimentu. Podle nařízení generála Káji je však zakázáno mít na jedné stanici více kontejnerů s experimenty (co kdyby se nějak ovlivnily?). Proto se veškeré přesuny musí konat výměnou kontejnerů mezi dvěma sousedními stanicemi. Protože jsou takové přesuny časově a finančně náročné, chceme najít co nejmenší počet výměn tak, aby se každý experiment dostal ke svému příjemci.

Tvar vstupu

Na prvním řádku souboru je číslo T – počet testovacích vstupů.
Na prvním řádku každého testu je číslo N – počet vesmírných stanic.
Na dalším řádku následuje N celých čísel v rozsahu 1N. Každé číslo se tam vyskytuje právě jednou. Pokud je na i-té pozici (číslované od 1) číslo ai, znamená to, že stanice na pozici i má na začátku kontejner určený pro stanici na pozici ai.
Sousedí spolu vždy dvojice i a i+1 a také dvojice 1 a N (první a poslední).

Tvar výstupu

Pro každý testovací vstup vypište číslo K – minimální počet potřebných výměn. Na dalších K řádcích popište libovolné optimální řešení, tedy posloupnost výměn. Každá výměna bude na samostatném řádku a skládá se ze dvou čísel A a B, které vyjadřují pozice dvou sousedících stanic (očíslovaných 1N), které konají tuto výměnu.

Lehká verze

  • T ≤ 10
  • N ≤ 15

Těžká verze

  • T ≤ 10
  • N ≤ 1000

Ukázkový vstup

3
5
5 2 3 4 1
5
2 3 4 5 1
5
5 4 3 2 1

Ukázkový výstup

1
1 5
4
4 5
3 4
2 3
1 2
4
5 1
2 3
3 4
2 3

Vysvětlení ukázkového vstupu a výstupu

V prvním vstupu platí, že jediné experimenty na chybných místech jsou 1 a 5, které mají prohozené stanice. Naštěstí jsou hned vedle sebe, protože stanice jsou rozmístěny v kruhu. Takže stačí, aby si stanice číslo 1 a 5 prohodily své kontejnery.

Ve druhém vstupu jsou všechny kontejnery posunuté o jedno místo směrem doleva. Jedno z možných řešení je posouvání kontejneru 1 postupně z pozice 5 na pozici 1.

Ve třetím vstupu můžeme kontejnery 5 a 1 doručit stejně jako v prvním případě. Na výměnu 4 a 2 ale musíme trojce na chvíli vzít její kontejner.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)