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]
cuX[2]
,X[3]
cuX[4]
, …,X[N-1]
cuX[N]
; - dacă
X[1]
este par atunci se interschimbăX[2]
cuX[3]
,X[4]
cuX[5]
, …,X[N-2]
cuX[N-1]
, iarX[N]
cuX[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
este1
, atunci se va rezolva numai cerința 1). În acest caz, fişierul de ieşireasort.out
va conţine pe prima linie un număr natural reprezentând numărul de pe pozițiaK
din șirulA
sortat. - Dacă valoarea lui
P
este2
, atunci se va rezolva numai cerința 2). În acest caz, fişierul de ieşireasort.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ăruluiT
.
Restricții și precizări
6 < N < 1 000 000 000
1 < R < 1 000 000 000
1 < K < N
și1 < T < N
- Dacă numărul
T
este situat pe poziția1
în șirul asortat, atunci predecesorul lui este numărului de pe pozițiaN
. Dacă numărulT
este situat pe pozițiaN
în șirul asortat, atunci succesorul lui este numărul de pe poziția1
. - 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
șiR ≤ 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.