Rezolvare PBinfo #1709

Se consideră un număr natural par N și șirul ordonat crescător X format din primele N numere naturale nenule:

X[1] = 1, X[2] = 2, …., X[N] = N.

Pozițiile numerelor din șir se pot modifica doar conform regulii A,după cum urmează:

• dacă X[1] este număr impar, atunci se interschimbă X[1] cu X[2], X[3] cu X[4], …, X[N-1] cu X[N];
• dacă X[1] este par atunci se interschimbă X[2] cu X[3], X[4] cu X[5], …, X[N-2] cu X[N-1], iar X[N] cu X[1].

Aplicând de R ori regula A șirului X se transformă șirul dat într-un șir “A sortat”.

Cerința

Cunoscându-se numerele naturale N, R, K și T, scrieți un program care să determine:
1) Numărul situat pe poziția K în șirul “ A sortat” obținut prin aplicarea de R ori a regulii “ A ” șirului X.
2) Predecesorul și succesorul numărului T în șirul “ A sortat” .

Date de intrare

Fişierul de intrare asort.in conține pe prima linie un număr natural P; numărul P poate avea doar valoarea 1 sau valoarea 2. A doua linie a fișierului asort.in conține în această ordine, patru numere naturale N, R, K și
T, separate prin câte un spațiu.

Date de ieșire

• Dacă valoarea lui P este 1, atunci se va rezolva numai cerința 1). În acest caz, fişierul de ieşire asort.out va conţine pe prima linie un număr natural reprezentând numărul de pe poziția K din șirul A sortat.
• Dacă valoarea lui P este 2, atunci se va rezolva numai cerința 2). În acest caz, fişierul de ieşire asort.out va conține pe prima linie două numere naturale, separate printr-un singur spațiu, reprezentând, în această ordine, predecesorul și succesorul numărului T.

Restricții și precizări

• 6 < N < 1 000 000 000
• 1 < R < 1 000 000 000
• 1 < K < N și 1 < T < N
• Dacă numărul T este situat pe poziția 1 în șirul asortat, atunci predecesorul lui este numărului de pe poziția N. Dacă numărul T este situat pe poziția N în șirul asortat, atunci succesorul lui este numărul de pe poziția 1.
• Pentru rezolvarea corectă a cerinţei 1 se acordă 50% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 50% din punctaj.
• Pentru teste în valoare de 15 puncte, N ≤ 1000 și R ≤ 1000

Exemplu:

asort.in

1
6 2 3 4 

asort.out

1

Explicație

Se rezolvă cerința 1. N=6, R=2, K=3 și T=4
X[1] X[2] X[3] X[4] X[5] X[6]

Șirul X inițial 1 2 3 4 5 6

Șirul după prima aplicare a regulii “ A” 2 1 4 3 6 5
Șirul asortat, obținut după a doua aplicare a regulii “A” 5 4 1 6 3 2
În șirul “asortat”, pe poziția K=3 se află valoarea 1 care se va scrie pe prima linie a fișierului asort.out.

Exemplu:

asort.in

2
6 2 3 4 

asort.out

5 1

Explicație

Se rezolvă cerința 2. N=6, R=2, K=3 și T=4

Șirul X inițial 1 2 3 4 5 6

Șirul după prima aplicare a regulii “A” 2 1 4 3 6 5
Șirul asortat, obținut după a doua aplicare a regulii “A” 5 4 1 6 3 2
În șirul “asortat”, predecesorul numărului T=4 este 5, iar succesorul este 1. Numerele 5 și 1 se vor scrie pe prima linie a fișierului asort.out, în această ordine.