1709 - Asort

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 input.txt 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 output.txt 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 output.txt 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

Exemplul 1

input.txt

1

6 2 3 4

output.txt:

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 output.txt

Exemplul 2

input.txt:

2

6 2 3 4

output.txt:

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 output.txt, în această ordine.

Exemplul 3

input.txt

1

99999999999999 2 3 4

Output:

Constrangeri neindeplinite

Rezolvare

<syntaxhighlight lang="python3" line="1"> def ver(n,r):

   if not(6<=n<=1000000000):
       print("Constrangeri neindeplinite")
       exit()
   if not(1<=r<=1000000000):
       print("Constrangeri neindeplinite")
       exit()

def numar_poz(k):

   global n, r
   nrc = 0
   if r == 0:
       return k
   if r % 2 != 0:
       if k % 2 != 0:
           nrc = (r + k) % n
       else:
           nrc = (n + k - r) % n
   else:
       if k % 2 == 0:
           nrc = (r + k) % n
       else:
           nrc = (n + k - r) % n
   if nrc == 0:
       nrc = n
   return nrc

def main():

   global n, r, t
   with open("input.txt", "r") as input_file, open("output.txt", "w") as output_file:
       p = int(input_file.readline())
       n, r, k, t = map(int, input_file.readline().split())
       ver(n,r)
       r = r % n
       if p == 1:
           output_file.write(str(numar_poz(k)) + '\n')
       else:
           pozt = (n + t - r) % n if t % 2 == 0 else (t + r) % n
           if pozt == 0:
               pozt = n
           if pozt == 1:
               poz_pred, poz_succ = n, 2
           elif pozt == n:
               poz_pred, poz_succ = n - 1, 1
           else:
               poz_pred, poz_succ = pozt - 1, pozt + 1
           pred = numar_poz(poz_pred)
           succ = numar_poz(poz_succ)
           output_file.write(str(pred) + " " + str(succ) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>