asort

Time limit: 0.1s
Memory limit: 16MB
Input: asort.in
Output: asort.out

Se consideră un număr natural par NN și șirul ordonat crescător XX format din primele NN numere naturale nenule: X1=1X_1=1, X2=2X_2=2, \dots, XN=NX_N=N.

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

  • dacă X1X_1 este număr impar, atunci se interschimbă X1X_1 cu X2X_2, X3X_3 cu X4X_4, \dots, XN1X_{N-1} cu XNX_N;
  • dacă X1X_1 este par atunci se interschimbă X2X_2 cu X3X_3, X4X_4 cu X5X_5, \dots, XN2X_{N-2} cu XN1X_{N-1}, iar XNX_N cu X1X_1.

Aplicând de RR ori regula AA șirului XX se transformă șirul dat într-un șir Asortat“A-sortat”.

Cunoscându-se numerele naturale NN, RR, KK și TT, scrieți un program care să determine:

  1. Numărul situat pe poziția KK în șirul Asortat“A-sortat” obținut prin aplicarea de RR ori a regulii A“A” șirului XX.
  2. Predecesorul și succesorul numărului TT în șirul Asortat“A-sortat”.

Date de intrare

Fişierul de intrare asort.in conține pe prima linie un număr natural PP; numărul P poate avea doar valoarea 11 sau valoarea 22. Pe a doua linie se află patru numere naturale NN, RR, KK și TT, în ordinea dată, separate prin câte un spațiu.

Date de ieșire

  • Dacă valoarea lui PP este 11, atunci se va rezolva numai cerința 11. În acest caz, fişierul asort.out va conţine pe prima linie un număr natural reprezentând numărul de pe poziția KK din șirul "Asortat""A-sortat".
  • Dacă valoarea lui PP este 22, atunci se va rezolva numai cerința 22. În acest caz, fişierul 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 TT.

Restricții și precizări

  • 6N1096 \leq N \leq 10^9, NN este par.
  • 1R1091 \leq R \leq 10^9.
  • 1K,TN1 \leq K, T \leq N
  • Dacă numărul TT este situat pe poziția 11 în șirul asortat, atunci predecesorul lui este numărului de pe poziția NN. Dacă numărul TT este situat pe poziția NN în șirul asortat, atunci succesorul lui este numărul de pe poziția 11.
  • Pentru rezolvarea corectă a cerinţei 11 se acordă 50%50\% din punctaj, iar pentru rezolvarea corectă a cerinţei 22 se acordă 50%50\% din punctaj.
  • Pentru teste în valoare de 1515 puncte din ambele cerinţe, în total fiind 3030 de puncte, N1000N \leq 1000 și R1000R \leq 1000.

Exemplul 1

asort.in

1
6 2 3 4 

asort.out

1

Explicație

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

  • Șirul XX inițial este 1 2 3 4 5 6.
  • După prima aplicare a regulii "A"A”, șirul este 2 1 4 3 6 5.
  • După a doua aplicare a regulii A“A”, șirul asortat este 5 4 1 6 3 2.
  • În șirul Asortat“A-sortat”, pe poziția K=3K=3 se află valoarea 1.

Exemplul 2

asort.in

2
6 2 3 4 

asort.out

5 1

Explicație

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

  • Șirul XX inițial este 1 2 3 4 5 6.
  • După prima aplicare a regulii "A"A”, șirul este 2 1 4 3 6 5.
  • După a doua aplicare a regulii A“A”, șirul asortat este 5 4 1 6 3 2.
  • În șirul Asortat“A-sortat”, predecesorul numărului T=4T=4 este 5, iar succesorul este 1.

Problem info

ID: 1084

Editor: stefanvilcescu

Author:

Source: ONI 2016 Baraj Juniori: Problema 1

Tags:

ONI 2016 Baraj Juniori

Log in or sign up to be able to send submissions!