Programozó versenyek

Informatikai versenyfeladatok, 2014/2015/1

2014. szeptember 16. 16:00 – 2014. december 21. 20:00

A következő permutáció

Egy halmaz permutációja alatt egy olyan sorozatot értünk, amely a halmaz minden elemét pontosan egyszer tartalmazza. A ⟨4, 2, 5, 1, 3⟩ például az {1, 2, 3, 4, 5} halmaznak egy permutációja, mint ahogy a ⟨4, 2, 1, 3, 5⟩ is.

Legyen n egy pozitív egész szám, legyen továbbá S = ⟨x1x2, …, xn⟩ és T = ⟨y1y2, …, yn⟩ az {1, 2, …, n} halmaz permutációi. Ekkor azt mondjuk, hogy S < T (S „kisebb, mint” T), ha létezik olyan k (1 ≤ k ≤ n), amelyre xk < yk és xi = yi minden olyan i esetén, amelyre 1 ≤ i < k. Más szóval S < T azt jelenti, hogy az első olyan pozícióban, ahol S és T eltérnek egymástól, S-ben található a kisebb értékű elem.

Például

⟨4, 2, 1, 3, 5⟩ < ⟨4, 2, 5, 1, 3⟩

teljesül, mert az első olyan pozícióban, ahol a két sorozat eltér egymástól (ez a harmadik pozíció), a bal oldali permutációban kisebb érték (1) szerepel, mint a jobb oldaliban (5).

Nyilvánvaló, hogy a fenti definíció alapján kilistázhatjuk az {1, 2, …, n} halmaz összes permutációját rendezetten, a legkisebbtől (⟨1, 2, …, n⟩) a legnagyobbig (⟨nn – 1, n – 2, …, 1⟩).

Példaként álljon itt az {1, 2, 3, 4} halmaz összes permutációja rendezve, a legkisebbtől a legnagyobbig:

⟨1, 2, 3, 4⟩, ⟨1, 2, 4, 3⟩, ⟨1, 3, 2, 4⟩, ⟨1, 3, 4, 2⟩, ⟨1, 4, 2, 3⟩, ⟨1, 4, 3, 2⟩, ⟨2, 1, 3, 4⟩, ⟨2, 1, 4, 3⟩, ⟨2, 3, 1, 4⟩, ⟨2, 3, 4, 1⟩, ⟨2, 4, 1, 3⟩, ⟨2, 4, 3, 1⟩, ⟨3, 1, 2, 4⟩, ⟨3, 1, 4, 2⟩, ⟨3, 2, 1, 4⟩, ⟨3, 2, 4, 1⟩, ⟨3, 4, 1, 2⟩, ⟨3, 4, 2, 1⟩, ⟨4, 1, 2, 3⟩, ⟨4, 1, 3, 2⟩, ⟨4, 2, 1, 3⟩, ⟨4, 2, 3, 1⟩, ⟨4, 3, 1, 2⟩, ⟨4, 3, 2, 1⟩

Írj programot, amely egy adott n egész szám és az {1, 2, …, n} halmaz egy adott S permutációja estén kiszámítja a legkisebb olyan T permutációt, amelyre S < T!

Segítség: Legyen S = ⟨x1x2, …, xn⟩, és tegyük fel, hogy xj < xj+1 > xj+2 > xj+3 > … > xn. (Más szóval tegyük fel, hogy j az utolsó olyan pozíció S-ben, ahol az elem kisebb a következő elemnél.) Ekkor a legkisebb olyan T permutáció, amely nagyobb, mint S, ⟨x1x2, …, xj–1xk, …⟩ alakú, ahol xk a legkisebb olyan eleme az {xj+1xj+2, …, xn} halmaznak, amely nagyobb, mint xj.

A bemenet specifikációja

Az első sor egy m > 0 számot, a bemenet további részében megadott permutációk számát tartalmazza. A következő 2m sorban szerepelnek a permutációk, mindegyik két sorban: az első egy n pozitív egész számot tartalmaz, a második pedig magát a permutációt (azaz egy olyan sorozatot, amely az {1, 2, …, n} halmaz minden elemét pontosan egyszer tartalmazza). A permutációk elemeit egy-egy szóköz választja el egymástól. Feltételezheted, hogy egyik megadott permutáció sem lesz a lehetséges legnagyobb. (Ez azt jelenti, hogy egyik sem lesz ⟨nn – 1, …, 1⟩ alakú.) Feltételezheted továbbá, hogy n ≤ 30.

A kimenet specifikációja

A bemeneten megadott minden S permutációra három sort kell a kimenetre írni: az elsőnek S-et kell tartalmaznia, a másodiknak a legkisebb olyan permutációt, amely nagyobb, mint S, a harmadiknak pedig üresnek kell lennie.

Példa bemenet

  1. 3
  2. 4
  3. 2 4 1 3
  4. 6
  5. 5 2 6 4 3 1
  6. 14
  7. 4 14 12 10 3 13 6 7 11 9 8 5 2 1
letöltés szöveges állományként

A példa bemenethez tartozó kimenet

  1. 2 4 1 3
  2. 2 4 3 1
  3. 5 2 6 4 3 1
  4. 5 3 1 2 4 6
  5. 4 14 12 10 3 13 6 7 11 9 8 5 2 1
  6. 4 14 12 10 3 13 6 8 1 2 5 7 9 11
letöltés szöveges állományként
Debreceni Egyetem, Informatikai Kar, v. 2024.09.30.