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] și
• b[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

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