Pagini recente » Cod sursa (job #2425521) | Cod sursa (job #1824303) | Cod sursa (job #1892632) | Cod sursa (job #970034) | Cod sursa (job #881418)
Cod sursa(job #881418)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("reguli.in");
ofstream g("reguli.out");
#define nmax 500005
#define ll long long
int n;
ll a[nmax];
int pi[nmax];
void citeste(){
f >> n;
ll x0, x; f >> x0;
for(int i=1; i<n; ++i){
f >> x;
a[i] = x - x0;
x0 = x;
}
}
void prefix(){
pi[1] = 0;
for(int i=2, q=0; i<n; ++i){
while(q > 0 && a[q+1] != a[i]) q = pi[q];
if (a[q+1] == a[i]) ++q;
pi[i] = q;
}
}
void rezolva(){
// acum am vectorul cu ratii trebuie sa determin cel mai mic ciclu
// avand in vedere ca pot avea si cicluri gen 1 2 2 1 2 2 incerc o solutie gen
// imi calculez fct prefix de la kmp pe sirul asta; dupa ce o calculez raspunsul o sa fie cel mai mare pi[i] dupa ultimul pi[i] = 0;
// adica dac ao sa am ceva gen pi[] : 0 0 1 2 0 1 2 3 raspunsul va fi 3 + (poz ultimulului 0 - 3)
prefix(); int ul = 0; int Rez = 0;
for(int i=1; i<n; ++i){
if (pi[i] == 0){
Rez = 0; ul = i;
continue;
}
Rez = max(Rez, pi[i]);
}
Rez += (ul - Rez);
//cout << Rez << "\n";
g << Rez << "\n";
for(int i=1; i<=Rez; ++i){
//cout << a[i] << "\n";
g << a[i] << "\n";
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}