Editing 1709 - Asort

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

<code>X[1] = 1</code>, <code>X[2] = 2</code>, …., <code>X[N] = N</code>.

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

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

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

= Cerința =
Cunoscându-se numerele naturale <code>N</code>, <code>R</code>, <code>K</code> și <code>T</code>, scrieți un program care să determine:

1) Numărul situat pe poziția <code>K</code> în șirul “ <code>A</code> sortat” obținut prin aplicarea de <code>R</code> ori a regulii “ <code>A</code> ” șirului <code>X</code>.

2) Predecesorul și succesorul numărului <code>T</code> în șirul “ <code>A</code> sortat” .

= Date de intrare =
Fişierul de intrare <code>input.txt</code> conține pe prima linie un număr natural <code>P</code>; numărul <code>P</code> poate avea doar valoarea <code>1</code> sau valoarea <code>2</code>. A doua linie a fișierului <code>asort.in</code> conține în această ordine, patru numere naturale <code>N</code>, <code>R</code>, <code>K</code> și

T, separate prin câte un spațiu.

= Date de ieșire =

* Dacă valoarea lui <code>P</code> este <code>1</code>, atunci se va rezolva numai cerința 1). În acest caz, fişierul de ieşire <code>output.txt</code> va conţine pe prima linie un număr natural reprezentând numărul de pe poziția <code>K</code> din șirul <code>A</code> sortat.
* Dacă valoarea lui <code>P</code> este <code>2</code>, atunci se va rezolva numai cerința 2). În acest caz, fişierul de ieşire <code>output.txt</code> 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 <code>T</code>.

= Restricții și precizări =

* <code>6 < N < 1 000 000 000</code>
* <code>1 < R < 1 000 000 000</code>

== Exemplul 1 ==
input.txt

1

6 2 3 4

output.txt:

1

Explicație:

Se rezolvă cerința 1. <code>N=6</code>, <code>R=2</code>, <code>K=3</code> și <code>T=4</code>

<code>X[1] X[2] X[3] X[4] X[5] X[6]</code>

Șirul <code>X</code> inițial <code>1 2 3 4 5 6</code>

Șirul după prima aplicare a regulii “ <code>A</code>” <code>2 1 4 3 6 5</code>

Șirul asortat, obținut după a doua aplicare a regulii “A” <code>5 4 1 6 3 2</code>

În șirul “asortat”, pe poziția <code>K=3</code> se află valoarea 1 care se va scrie pe prima linie a fișierului <code>output.txt</code>

== Exemplul 2 ==
input.txt:

2

6 2 3 4

output.txt:

5 1

Explicație:

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

Șirul <code>X</code> inițial <code>1 2 3 4 5 6</code>

Șirul după prima aplicare a regulii “A” <code>2 1 4 3 6 5</code>

Șirul asortat, obținut după a doua aplicare a regulii “A” <code>5 4 1 6 3 2</code>

În șirul “asortat”, predecesorul numărului <code>T=4</code> este <code>5</code>, iar succesorul este <code>1</code>. Numerele <code>5</code> și <code>1</code> se vor scrie pe prima linie a fișierului <code>output.txt</code>, î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>