2048 - mixperm - Revision history

Raul: Pagină nouă: Se consideră două șiruri de numere naturale, ambele de lungime `n`, `a=(a[1],a[2],...,a[n])` și `b=(b[1],b[2],...,b[n])`. Se știe că elementele din cele două șiruri sunt numere naturale, nu neapărat distincte, din mulțimea `{1,2,…,n}`. Cu cele două șiruri se poate face următoarea operație: se aleg doi indici `i` și `j`, cu `1≤i≤j≤n`, apoi prin interschimbarea secvențelor
2024-01-31T15:59:06Z

Pagină nouă: Se consideră două șiruri de numere naturale, ambele de lungime <code>n</code>, <code>a=(a[1],a[2],...,a[n])</code> și <code>b=(b[1],b[2],...,b[n])</code>. Se știe că elementele din cele două șiruri sunt numere naturale, nu neapărat distincte, din mulțimea <code>{1,2,…,n}</code>. Cu cele două șiruri se poate face următoarea operație: se aleg doi indici <code>i</code> și <code>j</code>, cu <code>1≤i≤j≤n</code>, apoi prin interschimbarea secvențelor <code...

New page
Se consideră două șiruri de numere naturale, ambele de lungime <code>n</code>, <code>a=(a[1],a[2],...,a[n])</code> și <code>b=(b[1],b[2],...,b[n])</code>. Se știe că elementele din cele două șiruri sunt numere naturale, nu neapărat distincte, din mulțimea <code>{1,2,…,n}</code>. Cu cele două șiruri se poate face următoarea operație: se aleg doi indici <code>i</code> și <code>j</code>, cu <code>1≤i≤j≤n</code>, apoi prin interschimbarea secvențelor <code>a[i],a[i+1],...,a[j]</code> cu <code>b[i],b[i+1],...,b[j]</code> se obțin șirurile:

* <code>a[1], a[2], ...,a[i-1], b[i],b[i+1],…, b[j], a[j+1],a[j+2], …, a[n]</code> și
* <code>b[1], b[2], ...,b[i-1], a[i], a[i+1],…, a[j], b[j+1],b[j+2], …, b[n]</code>.

Dacă măcar unul din șirurile obținute este permutare a mulțimii <code>{1,2,...,n}</code>, atunci spunem că s-a obținut un ''mixperm''.

= Cerința =
Să se determine în câte moduri se poate obține un ''mixperm''.

= Date de intrare =
Fișierul de intrare <code>mixperm.in</code> conţine pe prima linie numărul natural n, pe linia a doua, separate prin câte un spațiu, numerele <code>a[1]</code>, <code>a[2]</code>, …, <code>a[n]</code>, iar pe linia a treia, separate prin câte un spațiu, numerele <code>b[1]</code>, <code>b[2]</code>, …, <code>b[n]</code>.

= Date de ieșire =
Fișierul de ieșire <code>mixperm.out</code> va conţine un singur număr natural reprezentând numărul de posibilități de a se obține un mixperm.

= Restricții și precizări =

* <code>1 ≤ n ≤ 10.000</code>

= Exemplu: =
<code>mixperm.in</code>
6
3 2 1 4 4 5
2 3 3 4 6 5
<code>mixperm.out</code>
8

=== Explicație ===
Se pot interschimba secvențele care au ca poziții de început și sfârșit <code>(1,3) (1,4) (3,3) (3,4) (4,6) (5,6) (4,5) (5,5)</code>.

De exemplu, la interschimbarea secvenţei date de intervalul <code>(3,4)</code> se obţin şirurile <code>(3,2,3,4,4,5)</code> şi <code>(2,3,1,4,6,5)</code>. Al doilea şir este o permutare.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

nmax = 10005
inFile = "mixperm.in"
outFile = "mixperm.out"

a = [0] * nmax
b = [0] * nmax
sta = [0] * nmax
dra = [0] * nmax
stb = [0] * nmax
drb = [0] * nmax
suma_st = [0] * nmax
sumb_st = [0] * nmax
suma_dr = [0] * nmax
sumb_dr = [0] * nmax
app_st = [0] * nmax
bpp_st = [0] * nmax
app_dr = [0] * nmax
bpp_dr = [0] * nmax

S = 0
sTotal = 0
sPP = 0

def Citire():
fin = open(inFile, 'r')
global n
n = int(fin.readline())
a[1:n+1] = map(int, fin.readline().split())
b[1:n+1] = map(int, fin.readline().split())
fin.close()

def Precalculare():
global S, sTotal, sPP
S = 0
sTotal = n * (n + 1) // 2
sPP = 1 * n * (n + 1) * (2 * n + 1) // 6
for i in range(1, n+1):
S = S ^ i
sta[i] = sta[i - 1] ^ a[i]
stb[i] = stb[i - 1] ^ b[i]
suma_st[i] = suma_st[i - 1] + a[i]
sumb_st[i] = sumb_st[i - 1] + b[i]
app_st[i] = app_st[i - 1] + a[i] * a[i]
bpp_st[i] = bpp_st[i - 1] + b[i] * b[i]
for i in range(n, 0, -1):
dra[i] = dra[i + 1] ^ a[i]
drb[i] = drb[i + 1] ^ b[i]
suma_dr[i] = suma_dr[i + 1] + a[i]
sumb_dr[i] = sumb_dr[i + 1] + b[i]
app_dr[i] = app_dr[i + 1] + a[i] * a[i]
bpp_dr[i] = bpp_dr[i + 1] + b[i] * b[i]

def Valid(j, i, aSum, bSum):
if ((S ^ sta[j - 1] ^ bSum ^ dra[i + 1]) == 0 and sTotal == suma_st[j-1] + suma_dr[i+1] + (sumb_st[i] - sumb_st[j - 1]) and sPP == app_st[j-1] + app_dr[i+1] + (bpp_st[i] - bpp_st[j - 1])):
return True
if ((S ^ stb[j - 1] ^ aSum ^ drb[i + 1]) == 0 and sTotal == sumb_st[j-1] + sumb_dr[i+1] + (suma_st[i] - suma_st[j - 1]) and sPP == bpp_st[j-1] + bpp_dr[i+1] + (app_st[i] - app_st[j - 1])):
return True
return False

def Rezolvare():
ans = 0
for i in range(1, n+1):
aSum = bSum = 0
for j in range(i, 0, -1):
aSum = aSum ^ a[j]
bSum = bSum ^ b[j]
if (Valid(j, i, aSum, bSum)):
ans += 1

fout = open(outFile, 'w')
fout.write(str(ans) + "\n")
fout.close()

if name == "main":
Citire()
Precalculare()
Rezolvare()
</syntaxhighlight>