11319 - Stupid Sequence

[wudanzy]

Haha,I got AC,too. I tried again,still used Newton Interpolation.But this time I used doubles instead of integers and check if the output is between 0 and 1000.

[emotional blind]

In second case of inputs, f(0)=2, which means a0 must be equals 2.
But output says a0=0. Why?
(I am sure that my observation is wrong, but i need your help to find out where is my mistake )

thanks

[emotional blind]

I got it
its not f0 its f1

[emotional blind]

I got a lot of Wrong Answer.
At first I execute gauss elimination for first 7 inputs.
and then check feasibility for 1500 inputs.

Here is my code.

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;


#ifdef _MSC_VER
	typedef __int64 i64; typedef unsigned __int64 u64;
	#define I64 "%I64d"
	#define U64 "%I64u"
#else
	typedef long long i64; typedef unsigned long long u64;
	#define I64 "%lld"
	#define U64 "%llu"
#endif

int gcd( int a, int b ) { return( b == 0 ? a : gcd( b, a % b ) ); }
u64 gcd( u64 a, u64 b ) { return( b == 0 ? a : gcd( b, a % b ) ); }

#define SIZE 100

int N;
int a[SIZE][SIZE], b[SIZE];
u64 res[SIZE];


void norm(){
	int i, j, k, G;	

	for(i=0;i<N;++i){
		G=b[i];
		for(j=0;j<N;j++)G=gcd(G,a[i][j]);
		if(G==0)continue;
		for(j=0;j<N;j++)a[i][j]/=G;b[i]/=G;
	}
}

void swaprow(int u, int v){
	int i, temp;
	for(i=0;i<N;++i){
		temp=a[u][i];
		a[u][i]=a[v][i];
		a[v][i]=temp;
	}
	temp=b[u];b[u]=b[v];b[v]=temp;
}

void show(){
	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			printf("\t%dx%d",a[i][j],j);
		}
		printf("\t= %.d\n",b[i]);
	}
}

//given that a00 != 0
void Gauss(){
	int i, j, k; 
	int u;
	for(i=0;i<N-1;++i){
		norm();
		for(k=i;k<N;++k)if(a[k][i]!=0)break;
		if(k==N)continue;
		else if(k>i)swaprow(i,k);

		for(j=i+1;j<N;++j){
			u=a[j][i];
			for(k=i;k<N;++k){
				a[j][k]*=a[i][i];
			}
			b[j]*=a[i][i];
			
			for(k=i;k<N;++k){
				a[j][k]-=u*a[i][k];
			}
			b[j]-=u*b[i];
		}
	}
}


u64 p[1501][8];
u64 num[1600];

void prep(void){
	int i, j, k;
	for(i=0;i<=1500;++i){
		for(j=0;j<=7;++j){
			if(j==0)p[i][j]=1;
			else if(i==0)p[i][j]=0;
			else p[i][j]=i*p[i][j-1];
		}
	}
}

bool ok(int k){
	int i;
	u64 u=num[k-1]-res[0], v, x;
	if((u%k)!=0 || u<0)return false;
	u=u/k;
	v=0;
	x=1;
	for(i=1;i<7;++i){
		v=v+res[i]*x;
		x*=k;
	}
	if(v==u)return true;
	else return false;
}

int main (void){

	int i, j, k;
	//freopen("11319.txt","r",stdin);
	prep();
	N=7;
	int T;scanf("%d",&T);
	while(T--){
		for(i=0;i<1500;++i)scanf("%d",&num[i]);
		for(i=0;i<7;++i)for(j=0;j<7;++j)a[i][j]=p[i+1][j];
		
		for(i=0;i<7;++i)b[i]=num[i];
		
		Gauss();
		norm();
		
		bool nosolution=false;
		if(a[N-1][N-1]==0)nosolution = true;

		if(b[N-1]%a[N-1][N-1])nosolution=true;
		res[N-1]=b[N-1]/a[N-1][N-1];

		for(i=N-2;i>=0;--i){
			res[i]=b[i];
			for(j=i+1;j<N;++j)res[i] -= res[j]*a[i][j];

			if(a[i][i]==0 || res[i]%a[i][i]!=0){
				nosolution=true;
				break;
			}
			res[i]/=a[i][i];
		}

		for(i=0;i<7;++i)if(res[i]<0 || res[i]>1000){nosolution=true;break;}

		if(nosolution==false){
			for(i=1;i<=1500;++i){
				if(!ok(i))break;
			}
			if(i<=1500){
				nosolution=true;
			}
		}
	
		if(nosolution==true){
			printf("This is a smart sequence!\n");
		}
		else{
			printf("%d",res[0]);
			for(i=1;i<N;++i)printf(" %d",res[i]);
			printf("\n");
		}
	}
	return 0;
}

ok method is used to feasibility checking. Is my ok method is okay? is there any problem in my gauss elimination method ( i implemented it for the first time)
and res[0] to res[6] stores value of a0 to a6 respectively.

[serur]

I did exactly what sunny suggested; the main problem with my solution was rounding. AC.