Cod sursa(job #1537670)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 27 noiembrie 2015 19:07:51
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <cstdio>
#define maxl 500005

using namespace std;

long long n,x[maxl],a[maxl],res=0,prefix[maxl];
/**
La ora de matematica, Gigel invata despre siruri. Pentru a intelege mai bine cum functioneaza acestea, el incearca mai intai sa construiasca niste siruri speciale pe baza anumitor criterii, siruri ce au ca termeni numai numere intregi. O regula a pentru un sir x este un vector (a1, a2, ... aK). Pe baza primului element al sirului, x0, si al vectorului a, sirul x este unic determinat prin relatia de recurenta:

xi = xi-1 + ai mod K, daca i mod K este diferit de 0, sau
xi = xi-1 + aK, daca i mod K este 0

Prin A mod B se intelege restul impartirii lui numarului A la B.

Gigel noteaza intr-un carnet primele N elemente ale sirului x, x0, x1, ... xN-1, sir obtinut conform procedeului de mai sus. Bineinteles, dupa un timp, dupa ce Gigel uita regula pe care a folosit-o pentru a obtine sirul de pe carnet, apar intrebarile. Care este cel mai scurt vector a ( ca numar de elemente ), conform caruia se pot obtine primele N elemente ale sirului x?
Date de intrare

Fisierul de intrare este reguli.in. Pe prima linie a acestui fisier se afla N. Urmatoarele N linii contin cate un numar intreg, pe linia i+1 aflandu-se valoarea elementului xi-1.
Date de iesire

Pe prima linie a fisierului reguli.out se afla K, lungimea minima a unui vector (a1, a2, ... ak) ce poate genera primele N elemente ale sirului x. Urmeaza K linii ce descriu vectorul determinat, pe linia i+1 aflandu-se ai.
Restrictii

    5 ≤ N ≤ 500 000
    Primele N numere din sirul x se incadreaza intotdeauna in intregi cu semn pe 64 de biti

*/
void create_a();

int main(){
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    scanf("%lld",&n);
    int i;
    for(i=0;i<n;i++)scanf("%lld",&x[i]);
    /*create_a();
    printf("%lld\n",res);
    for(i=1;i<res;i++)printf("%lld\n",a[i%res]);
    printf("%lld\n",a[res]);*/
    printf("%d\n",n);
    for(i=0;i<n;i++)printf("%d\n",x[i]);
    return 0;
}
void create_a(){
   int i,k=0;
   prefix[1]=0;
   for(i=1;i<n;i++)a[i]=x[i]-x[i-1];
   for(i=2;i<n;i++){
      while(k && a[k+1]!=a[i])k=prefix[k];
      if(a[k+1]==a[i])k++;
      prefix[i]=k;
      if(prefix[i]==1)res=i-1;
   }

}