1715 - Inversiuni: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor. == Cerința ==...
 
No edit summary
 
Line 1: Line 1:
Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor.
Ludwig are o permutare <code>p=(p[1],p[2],...,p[N])</code> a mulțimii <code>{1,2,..,N}</code> și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică <code>p[1]</code>, și îl așează pe masă. Al doilea număr, <code>p[2]</code>, îl pune fie în stânga lui <code>p[1]</code>, fie în dreapta lui <code>p[1]</code>. La fiecare pas, dacă s-au așezat pe masă deja numerele <code>p[1]</code>, <code>p[2]</code>, …, <code>p[i]</code>, atunci numărul <code>p[i+1]</code> este pus fie în stânga numerelor deja așezate, fie în dreapta lor.
== Cerința ==
 
= Cerința =
Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.
Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.
== Date de intrare ==
 
Fișierul de intrare inversiuniin.txt conține pe prima linie numărul natural N, iar pe linia a doua, separate prin câte un spațiu, numerele p[1], p[2], …, p[N].
= Date de intrare =
== Date de ieșire ==  
Fișierul de intrare <code>inversiuniIN.txt</code> conține pe prima linie numărul natural <code>N</code>, iar pe linia a doua, separate prin câte un spațiu, numerele <code>p[1]</code>, <code>p[2]</code>, …, <code>p[N]</code>.
Fișierul de ieșire inversiuniout.txt va conține un singur număr natural reprezentând numărul minim de inversiuni 1 ≤ N ≤ 200 000
 
== Restricții și precizări ==
= Date de ieșire =
*1 ≤ N ≤ 200 000
Fișierul de ieșire <code>inversiuniOUT.txt</code> va conține un singur număr natural reprezentând numărul minim de inversiuni care se pot obține. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
*O inversiune în permutare este o pereche de indici (i,j) cu i<j și p[i]>p[j]. De exemplu, permutarea p=(3,2,1,4) are ca inversiune perechea de indici (1,3) pentru că p[1]>p[3]; o altă inversiune este perechea de indici (2,3) pentru că p[2]>p[3].
 
== Exemplul 1 ==
= Restricții și precizări =
; inversiuniin.txt
 
: 4
* <code>1 ≤ N ≤ 200 000</code>
: 2 1 3 4
* O inversiune în permutare este o pereche de indici <code>(i,j)</code> cu <code>i<j</code> și <code>p[i]>p[j]</code>. De exemplu, permutarea <code>p=(3,2,1,4)</code> are ca inversiune perechea de indici <code>(1,3)</code> pentru că <code>p[1]>p[3]</code>; o altă inversiune este perechea de indici <code>(2,3)</code> pentru că <code>p[2]>p[3]</code>.  
; inversiuniout.txt
 
: 0
= Exemplul 1: =
<br>
<code>inversiuniIN.txt</code>
== Explicatie ==  
4
2 1 3 4
<code>inversiuniOUT.txt</code>
0
 
=== Explicație ===
Se așează elementele pe masă astfel:
Se așează elementele pe masă astfel:


*2
* <code>2</code>
*1 2 (1 este așezat la stânga)
* <code>1 2</code> (<code>1</code> este așezat la stânga)
*1 2 3 (3 este așezat la dreapta)
* <code>1 2 3</code> (<code>3</code> este așezat la dreapta)
*1 2 3 4 (4 este așezat la dreapta)
* <code>1 2 3 4</code> (<code>4</code> este așezat la dreapta)
 
Se obține permutarea identică, adică zero inversiuni.
Se obține permutarea identică, adică zero inversiuni.
== Exemplul 2 ==
; inversiuniin.txt
: 4
: 2 1 4 3
; inversiuniout.txt
: 1
<br>
== Explicatie ==
Se așează elementele pe masă astfel:


*2
== Exemplul 2: ==
*1 2 (1 este așezat la stânga)
<code>inversiuniIN.txt</code>
*1 2 4 (4 este așezat la dreapta)
0
*1 2 4 3 (3 este așezat la dreapta)
2 1 3 4
Se obține o permutare care are o inversiune.
<code>inversiuniOUT.txt</code>
Datele nu corespund restrictiilor impuse
 
== Rezolvare ==  
== Rezolvare ==  
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line="1">
#1715 - Inversiuni
import sys
def minim_inversiuni(N, permutare):
 
     if N < 1 or N > 200000:
def verifica_restrictii(n):
         print("Fals")
     if not (1 <= n <= 200000):
         exit()
         with open("inversiuniOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
         sys.exit()
 
def update(a, n, x):
    i = x
    while i <= n:
        a[i] += 1
        i += (i & -i)


     inversiuni = 0
def query(a, x):
     for i in range(N):
     s = 0
         inversiuni += abs(i + 1 - permutare[i])
     i = x
    while i > 0:
         s += a[i]
        i -= (i & -i)
    return s


     print(inversiuni)
def main():
     with open("inversiuniIN.txt", "r") as fin:
        n = int(fin.readline().strip())
        verifica_restrictii(n)
        a = [0] * (n + 1)
        cnt = 0
        perm = list(map(int, fin.readline().strip().split()))
        for i in range(1, n + 1):
            x = perm[i - 1]
            mici = query(a, x)
            mari = i - mici - 1
            if mici < mari:
                cnt += mici
            else:
                cnt += mari
            update(a, n, x)


# Citirea datelor de intrare
    with open("inversiuniOUT.txt", "w") as fout:
with open("inversiuniin.txt", "r") as f:
        fout.write(f"{cnt}\n")
    N = int(f.readline())
    permutare = list(map(int, f.readline().split()))


# Apelarea funcției și afișarea rezultatului
if __name__ == "__main__":
minim_inversiuni(N, permutare)
    main()


</syntaxhighlight>
</syntaxhighlight>

Latest revision as of 07:00, 18 May 2024

Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor.

Cerința[edit | edit source]

Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.

Date de intrare[edit | edit source]

Fișierul de intrare inversiuniIN.txt conține pe prima linie numărul natural N, iar pe linia a doua, separate prin câte un spațiu, numerele p[1], p[2], …, p[N].

Date de ieșire[edit | edit source]

Fișierul de ieșire inversiuniOUT.txt va conține un singur număr natural reprezentând numărul minim de inversiuni care se pot obține. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări[edit | edit source]

  • 1 ≤ N ≤ 200 000
  • O inversiune în permutare este o pereche de indici (i,j) cu i<j și p[i]>p[j]. De exemplu, permutarea p=(3,2,1,4) are ca inversiune perechea de indici (1,3) pentru că p[1]>p[3]; o altă inversiune este perechea de indici (2,3) pentru că p[2]>p[3].

Exemplul 1:[edit | edit source]

inversiuniIN.txt

4
2 1 3 4

inversiuniOUT.txt

0

Explicație[edit | edit source]

Se așează elementele pe masă astfel:

  • 2
  • 1 2 (1 este așezat la stânga)
  • 1 2 3 (3 este așezat la dreapta)
  • 1 2 3 4 (4 este așezat la dreapta)

Se obține permutarea identică, adică zero inversiuni.

Exemplul 2:[edit | edit source]

inversiuniIN.txt

0
2 1 3 4

inversiuniOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line="1"> import sys

def verifica_restrictii(n):

   if not (1 <= n <= 200000):
       with open("inversiuniOUT.txt", "w") as fout:
           fout.write("Datele nu corespund restrictiilor impuse\n")
       sys.exit()

def update(a, n, x):

   i = x
   while i <= n:
       a[i] += 1
       i += (i & -i)

def query(a, x):

   s = 0
   i = x
   while i > 0:
       s += a[i]
       i -= (i & -i)
   return s

def main():

   with open("inversiuniIN.txt", "r") as fin:
       n = int(fin.readline().strip())
       verifica_restrictii(n)
       a = [0] * (n + 1)
       cnt = 0
       perm = list(map(int, fin.readline().strip().split()))
       for i in range(1, n + 1):
           x = perm[i - 1]
           mici = query(a, x)
           mari = i - mici - 1
           if mici < mari:
               cnt += mici
           else:
               cnt += mari
           update(a, n, x)
   with open("inversiuniOUT.txt", "w") as fout:
       fout.write(f"{cnt}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>