Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Ismert tudósunk, Miloš aki ezen a területen a legképzettebb, a világméretű járvány miatt azt a feladatot kapta, hogy analizálja laboratóriumában a vírus génszerkezetét. Ha munkája eredményes lesz, az biztosítja majd a gyógyszer kifejlesztését, és így a vírus legyőzését.
A vírus génszerkezetét (\(G\)) ábrázolhatjuk számjegyek permutációjával, ahol a számjegyek \(1\)-től \(N\)-ig mennek, vagyis egy olyan számsorozattal, amely elemei \(1\)-től \(N\)-ig vehetnek fel értéket, hossza \(N\), és minden számjegy csak egyszer fordul elő benne.
Hogy Miloš elvégezhesse az analízist, a génszerkezet rendezett kell hogy legyen. A génszerkezet rendezéséhez Miloš egy nagyon különleges gépet használ. Ez a gép lehetővé teszi, hogy kiemelje a sorozat egy szakaszát, és megfordítsa azt. Pontosabban kiválaszthat két, \(l\) és \(r\) indexet úgy, hogy érvényes legyen \(l\leq r\), és megfordítsa az \(l\)-től \(r\) pozícióig húzódó részsorozatot a sorozatban (felcserélje a következő elemeket: \(G_l\) és \(G_r\), \(G_{l+1}\)és \(G_{r-1}\), \(\ldots\) ).
Miloš azt is tudja, hogy a gének rendkívül érzékenyek, és azok megsérülnek, ha a gépet ugyanarra a génre többször alkalmazza. Miloš a gépet számtalanszor használhatja, de az indexek által definiált intervallumok nem ismétlődhetnek.
Milošnak még nincs elég tapasztalata a gép használatában, ezért a ti segítségeteket kéri. Mondjátok meg ti, lehetséges-e a génszerkezet rendezése anélkül, hogy a gének megsérülnének! Ha a génszerkezet rendezése lehetséges, Milošnak szüksége van műveletek sorrendjére is, amellyel a rendezés megvalósítható. Ezenkívül azt is tudjuk, hogy a gép lassú, a gyógyszer kifejlesztése pedig nem várhat, a műveletek sorrendje a lehető legrövidebb kell hogy legyen (ha több azonos hosszúságú műveleti sorrend létezik, kiíratni bármelyiket).
A szabványos bemenet első sorában az \(N\) szám, a génszerkezet hossza található. A szabványos bement második sorában a \(G\) számsorozat, vagyis a génszerkezet áll.
Amennyiben a génszerkezet rendezése lehetséges, a szabványos kimenet első sorában kiíratni a “Svet je spasen” szöveget. A szabványos kimenet második sorában kiíratni a \(K\) számot a legrövidebb műveleti sorrend műveleteinek számát. A következő \(K\) sor mindegyikében két \(l_i\) és \(r_i\)számot, amely indexeket Milošnak az \(i\)-edik művelet alkalmával ki kell választania.
Amennyiben a génszerkezet rendezése nem lehetséges, a szabványos kimenet első és egyetlen sorában kiíratni a “Nema spasa” szöveget.
8
2 1 4 3 5 6 7 8Svet je spasen
2
1 2
3 48
1 6 7 3 2 5 4 8Nema spasaA tesztpéldák 5 alfeladatra oszthatók: