Oros Ioana Diana at 07:00, 18 May 2024

2024-05-18T07:00:33Z

Oros Ioana Diana: 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 ==...

2024-01-08T23:27:40Z

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 ==...

New page

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 ==
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 ieșire ==
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 ==
*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 ==
; inversiuniin.txt
: 4
: 2 1 3 4
; inversiuniout.txt
: 0
<br>
== Explicatie ==
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 ==
; inversiuniin.txt
: 4
: 2 1 4 3
; inversiuniout.txt
: 1
<br>
== Explicatie ==
Se așează elementele pe masă astfel:

*2
*1 2 (1 este așezat la stânga)
*1 2 4 (4 este așezat la dreapta)
*1 2 4 3 (3 este așezat la dreapta)
Se obține o permutare care are o inversiune.
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1715 - Inversiuni
def minim_inversiuni(N, permutare):
if N < 1 or N > 200000:
print("Fals")
exit()

inversiuni = 0
for i in range(N):
inversiuni += abs(i + 1 - permutare[i])

print(inversiuni)

# Citirea datelor de intrare
with open("inversiuniin.txt", "r") as f:
N = int(f.readline())
permutare = list(map(int, f.readline().split()))

# Apelarea funcției și afișarea rezultatului
minim_inversiuni(N, permutare)

</syntaxhighlight>

1715 - Inversiuni - Revision history

Oros Ioana Diana at 07:00, 18 May 2024