2048 - mixperm
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 a[i],a[i+1],...,a[j]
cu b[i],b[i+1],...,b[j]
se obțin șirurile:
a[1], a[2], ...,a[i-1], b[i],b[i+1],…, b[j], a[j+1],a[j+2], …, a[n]
șib[1], b[2], ...,b[i-1], a[i], a[i+1],…, a[j], b[j+1],b[j+2], …, b[n]
.
Dacă măcar unul din șirurile obținute este permutare a mulțimii {1,2,...,n}
, 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 mixperm.in
conţine pe prima linie numărul natural n, pe linia a doua, separate prin câte un spațiu, numerele a[1]
, a[2]
, …, a[n]
, iar pe linia a treia, separate prin câte un spațiu, numerele b[1]
, b[2]
, …, b[n]
.
Date de ieșire
Fișierul de ieșire mixperm.out
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
1 ≤ n ≤ 10.000
Exemplu:
mixperm.in
6 3 2 1 4 4 5 2 3 3 4 6 5
mixperm.out
8
Explicație
Se pot interschimba secvențele care au ca poziții de început și sfârșit (1,3) (1,4) (3,3) (3,4) (4,6) (5,6) (4,5) (5,5)
.
De exemplu, la interschimbarea secvenţei date de intervalul (3,4)
se obţin şirurile (3,2,3,4,4,5)
şi (2,3,1,4,6,5)
. Al doilea şir este o permutare.
Încărcare soluție
Lipește codul aici
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()