Cod sursa(job #2923683)

Utilizator lolismekAlex Jerpelea lolismek Data 17 septembrie 2022 20:20:13
Problema Reguli Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 5e5;
int v[N + 1], kmp[N + 1], f[N + 1];

void Kmp(int n){
	for(int i = 2; i <= n; i++){
		int l = kmp[i - 1];
		while(l >= 1 && v[l + 1] != v[i])
			l = kmp[l];
		if(v[l + 1] == v[i])
			kmp[i] = l + 1;
	}
}

int main(){

	int n, x0;
	fin >> n >> x0, n--;

	int sub = 0;
	for(int i = 1; i <= n; i++){
		fin >> v[i], v[i] -= x0;
		v[i] -= sub, sub += v[i];
	}

	Kmp(n);

	for(int i = 1; i <= n; i++)
		f[kmp[i]]++;

	for(int i = 1; i <= n; i++)
		if(f[i] >= n / i - 1){
			fout << i << '\n';
			for(int j = 1; j <= i; j++)
				fout << v[j] << '\n';
			return 0;
		}

	return 0;
}