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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema mixperm:

#include <fstream>
#include <iostream>
#define nmax 10005
#define inFile  "mixperm.in"
#define outFile "mixperm.out"

using namespace std;

int a[nmax], b[nmax], n;
int sta[nmax], dra[nmax], stb[nmax], drb[nmax];
int suma_st[nmax], sumb_st[nmax], suma_dr[nmax], sumb_dr[nmax];
long long app_st[nmax], bpp_st[nmax], app_dr[nmax], bpp_dr[nmax];
int S, sTotal;
long long sPP;

void Citire()
{
    int i;
    ifstream fin(inFile);
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    for (i = 1; i <= n; i++)
        fin >> b[i];
    fin.close();
}

void Precalculare()
{
    int i;
    S = 0;
    sTotal = n * (n + 1) / 2;
    sPP = 1LL * n * (n + 1) * (2 * n + 1) / 6;
    for (i = 1; i <= n; i++)
    {
        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 = n; i >= 1; i--)
    {
        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];
    }
}

inline bool Valid(int j, int i, int aSum, int bSum)
{
    if ((S ^ sta[j - 1] ^ bSum ^ dra[i + 1]) == 0 &&
        sTotal==suma_st[j-1] + suma_dr[i+1]+(sumb_st[i] - sumb_st[j - 1]) &&
        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 &&
        sTotal==sumb_st[j-1] + sumb_dr[i+1]+(suma_st[i] - suma_st[j - 1]) &&
        sPP==bpp_st[j-1] + bpp_dr[i+1]+(app_st[i] - app_st[j - 1]))
            return true;
    return false;
}

void Rezolvare()
{
    int ans, i, j, aSum, bSum;
    ans = 0;
    for (i = 1; i <= n; i++)
    {
        aSum = bSum = 0;
        for (j = i; j >= 1; j--)
        {
            aSum = aSum ^ a[j];
            bSum = bSum ^ b[j];
            if (Valid(j, i, aSum, bSum))
            {
                ans++;
                ///cout << j << " " << i << "\n";
            }
        }
    }

    ofstream fout(outFile);
    fout << ans << "\n";
    fout.close();
}

int main()
{
    Citire();
    Precalculare();
    Rezolvare();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2048 mixperm

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2048 mixperm de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2048 mixperm