Cod sursa(job #3311265)

Utilizator Lex._.Lex Guiman Lex._. Data 20 septembrie 2025 18:29:22
Problema Reguli Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
#define NMAX 500000
using namespace std;

ifstream in("reguli.in");
ofstream out("reguli.out");

long long x[NMAX], a[NMAX];
int pi[NMAX]; ///pi[i] = lungimea celui mai lung prefix care este si sufix al secventei formate din primele i valori ale sirului

int main()
{
    int n;
    in >> n;
    for(int i=0; i<n; i++)
    {
        in >> x[i];
        if(i>0)
            a[i]=x[i]-x[i-1]; ///valoarea care a fost adunata la x[i-1] pentru a obtine x[i]
    }
    ///observam ca cel mai scurt vector cerut este cea mai scurta subsecventa a vectorului a care este periodica
    ///vom calcula cel mai lung prefix al vectorului a care este si sufix
    int l_prefix=0;
    pi[1]=l_prefix;
    for(int i=2; i<n; i++)
    {
        while(l_prefix>0 && a[l_prefix+1]!=a[i])
        {
            l_prefix=pi[l_prefix-1];
        }
        if(a[l_prefix+1]==a[i])
            l_prefix++;

        pi[i]=l_prefix;
    }

    int l_min=n-1; ///lungimea minima a unui sir
    while(pi[l_min]!=0)
    {
        l_min=l_min-pi[l_min];
    }
    out << l_min << "\n";
    for(int i=1; i<=l_min; i++) ///afisam vectorul de lungime minima
    {
        out << a[i] << "\n";
    }

    return 0;
}