10326 - The Polynomial Equation

Revenger · Post by **Revenger** » Sun Jul 14, 2002 5:38 pm

I submit this problem 22 times at contest, but always get WA

Please, help me!

[pascal]Program p10326;

Const MaxN = 50;
Eps = 1e-3;

Type TEqu = Array[0..MaxN]of Comp;

Var N,i,j,ok : Integer;
R : Array[1..MaxN]of Comp;
Ans : TEqu;

Procedure WriteEqu(E : TEqu);
Var i : Integer;
f : boolean;
begin
f:=true;
for i:=MaxN downto 1 do
if Abs(E)>eps then begin
if E<-eps then Write(' - ');
if (E>-eps)and(not f) then Write(' + ');
f:=false;
if Abs(Abs(E)-1)>eps then Write(Abs(E):0:0);
Write('x');
if i>1 then Write('^',i:0);
end;
if not f then begin
if E[0]<-eps then Write(' - ') else Write(' + ');
end else
if E[0]<-eps then Write('- ');
Writeln(Abs(E[0]):0:0,' = 0');
end;

Procedure AddTo(Var E : TEqu; A : Comp);
Var i : Integer;
F : TEqu;
begin
for i:=1 to MaxN do F:=E[i-1];
F[0]:=0;
for i:=0 to MaxN-1 do
if Abs(E)>eps then F:=F-E*A;
E:=F;
end;

begin
While Not Eof(InPut) do begin
Read(N);
for i:=1 to N do Read(R[i]);
if Eoln(InPut) then Readln;
for i:=1 to MaxN do Ans[i]:=0;
Ans[0]:=1;
for i:=1 to N do AddTo(Ans,R[i]);
WriteEqu(Ans);
end;
end.[/pascal]

oker · Post by **oker** » Thu Jul 18, 2002 12:58 am

Here's my code. I can't find the bugs.

Help me! Thank you!
[pascal]
program k326;

type
Tshi=array[0..50] of extended;

var
shi :array[1..50] of Tshi;
n,i :integer;
a :extended;

procedure Pmul(a,b:Tshi; var c:Tshi);

var
i,j :integer;

begin
fillchar(c,sizeof(c),0);
for i:=0 to n do if a<>0 then
for j:=0 to n do if (i+j<=n) and (b[j]<>0) then c[i+j]:=c[i+j]+a*b[j];
end;

procedure work;

var
ans :Tshi;
i :integer;

begin
ans:=shi[1];
for i:=2 to n do Pmul(ans,shi,ans);
write('x^',n,' ');
for i:=n-1 downto 2 do if ans<>0 then
if ans=1 then write('+ x^',i,' ')
else if ans>1 then write('+ ',ans:0:0,'x^',i,' ')
else if ans=-1 then write('- x^',i,' ')
else write('- ',-ans:0:0,'x^',i,' ');
if ans[1]>1 then write('+ ',ans[1]:0:0,'x ')
else if ans[1]=1 then write('+ x ')
else if ans[1]=-1 then write('- x ')
else if ans[1]<-1 then write('- ',-ans[1]:0:0,'x ');
if ans[0]>=0 then write('+ ',ans[0]:0:0,' ')
else write('- ',-ans[0]:0:0,' ');
writeln('= 0');
end;

begin
{ assign(input,'k326.in');
reset(input); }
while not eof(input) do begin
fillchar(shi,sizeof(shi),0);
readln(n);
for i:=1 to n do begin
read(a);
shi[i,1]:=1;
shi[i,0]:=-a;
end;
readln;
work;
end;
{ close(input); }
end.
[/pascal]

wyvmak · Post by **wyvmak** » Thu Jul 18, 2002 4:36 am

[pascal]procedure work;

var
ans :Tshi;
i :integer;

begin
ans:=shi[1];
for i:=2 to n do Pmul(ans,shi,ans);
write('x^',n,' ');
[/pascal]

if n=1, then you'll have "x^1", right?

oker · Post by **oker** » Thu Jul 18, 2002 7:22 am

Thank you for your help! I made so foolish mistake

I got AC now!

sayeed · Post by **sayeed** » Sun Aug 11, 2002 6:45 pm

/*@BEGIN_OF_SOURCE_CODE*/
#include<stdio.h>

int main()

{
int n,i,j,k,temp,flag;
long long Coeff[55],sum,root[55];
while(scanf("%d",&n)==1){
for(i = 0;i<n;i++) scanf("%lld",&root),Coeff = 0;
Coeff[0] = 1;
for(i =n-1;i>0;i--){
Coeff[0] *=root;
for(j=0;j<n;j++){
sum = 1;
for(k =n-i-1;k>=0;k--){
sum*=root[(j+k)%n];

}

Coeff += sum;
}
}

Coeff[n] = 1;
Coeff[0] *=root[0];
flag = 1;

for(i = n;i>=0;i--){

if(flag*Coeff==0 ) temp = 0;
else if(flag*Coeff == -1) temp = -1;
else if(flag*Coeff<-1) temp = -2;
else if(flag*Coeff == 1) temp = 1;
else if(flag*Coeff>1) temp = 2;

Coeff = (Coeff[i]<0)?-Coeff[i]:Coeff[i];

flag *=(-1);
if(i == n && i != 1) printf("x^%d ",i);
else if(i == n) printf("x ");
else if(temp == 0 && i == 0) printf("+ 0 ");
else if(temp == 0) continue;
else if(i == 0 && temp<0) printf("- %lld ",Coeff[i]);
else if(i == 0 && temp>0) printf("+ %lld ",Coeff[i]);
else if(temp == -1){
if(i == 1) printf("- x ");
else printf("- x^%d ",i);
}
else if(temp == -2){
if(i == 1) printf("- %lldx ",Coeff[i]);
else printf("- %lldx^%d ",Coeff[i],i);
}
else if(temp == 1){
if(i == 1) printf("+ x ");
else printf("+ x^%d ",i);

}
else if(temp == 2){
if(i == 1) printf("+ %lldx ",Coeff[i]);
else printf("+ %lldx^%d ",Coeff[i],i);
}
}
printf("= 0\n");
}

return 0;
}
/*@END_OF_SOURCE_CODE*/

********
what's the error?Pls help

Bistromath · Post by **Bistromath** » Wed Nov 20, 2002 5:00 pm

i have the same problem
N submissions and N WA (N>10)

thanks for any help

here is my code:

[cpp]
#include <stdio.h>

inline int Abs( int i )
{
return ( i > 0 ) ? i : -i ;
}

inline double Abs( double i )
{
return ( i > 0 ) ? i : -i ;
}

template <class CoefficientType, int MaxPower>
class CPolynome
{
public:
CPolynome()
{
Raz() ;
}

CPolynome( const CPolynome& p )
{
for ( int i = 0 ; i <= MaxPower ; ++i )
m_Coeff = p.m_Coeff ;
}

CPolynome( CoefficientType x2, CoefficientType x, CoefficientType cte )
{
Raz() ;
m_Coeff[0] = cte ;
m_Coeff[1] = x ;
m_Coeff[2] = x2 ;
}

CPolynome operator*( const CPolynome& p ) const
{
CPolynome result ;
unsigned short h1 = HighestCoefficient() ;
unsigned short h2 = p.HighestCoefficient() ;
for ( int i = 0 ; i <= h1 ; ++i )
for ( int j = 0 ; j <= h2 ; ++j )
result.m_Coeff[i+j] += m_Coeff * p.m_Coeff[j] ;
return result ;
}

void Print()
{
const unsigned short h = HighestCoefficient() ;
for ( int i = h ; i >= 0 ; --i )
{

if ( m_Coeff == 0 && i > 0 )
continue ;

// Signe
if ( i == h )
{
if ( m_Coeff<0 ) printf("- ") ;
}
else
{
printf(" %c ", ( m_Coeff<0 ) ? '-' : '+' ) ;
}

// Coefficient
if ( i > 0 )
{
if ( Abs( m_Coeff ) != 1 )
printf("%.0lf", Abs( m_Coeff ) ) ;
printf("x") ;
}
else
printf("%.0lf", Abs( m_Coeff ) ) ;

// Puissance
if ( i >= 2 )
printf("^%d", i ) ;

}
}
unsigned short HighestCoefficient() const
{
for ( int i = MaxPower ; i >= 0 ; --i )
if ( m_Coeff != 0 )
return i ;
return MaxPower ;
}
protected:
void Raz()
{
for ( int i = 0 ; i <= MaxPower ; ++i )
m_Coeff[i] = 0 ;
}
CoefficientType m_Coeff[MaxPower+1] ;
} ;

typedef CPolynome<double, 60> PolInt ;

int main()
{
int rootCount ;

while ( scanf("%d", &rootCount ) > 0 )
{
if ( rootCount > 0 )
{
PolInt product(0,0,1) ;
for ( int r = 0 ; r < rootCount ;++r )
{
int root ;
scanf("%d", &root ) ;
PolInt p( 0, 1, -root ) ;
product = product*p ;
}
product.Print() ;
printf(" = 0\n") ;
}
else
printf("0 = 0\n" ) ;
}

return 1 ;
}
[/cpp]

yatsen · Post by **yatsen** » Fri Dec 13, 2002 7:01 am

To Bistromath:

Do you try this input:
1
0

Your program output:
x + -0 = 0

But I think the correct answer is:
x + 0 = 0

Bistromath · Post by **Bistromath** » Sun Dec 29, 2002 5:30 pm

Thanks for your help yatsen
But my program output is correct in the case 1 0

Really don't know where is the mistake

.. · Post by .. » Sun Dec 29, 2002 8:48 pm

to Bistromath:

I am not sure if this is the key, but there is
"Again if the constant term is zero always use + 0." in the problem description. And for N = 0, my program will output

+ 0 = 0

tat tvam asi · Post by **tat tvam asi** » Tue Dec 31, 2002 12:15 am

helo bistromath
your code is too big
to me ... but there is a 10^15
bound on coefficients so why
don't you use long long int ?
bye

supermin · Post by **supermin** » Tue Jan 07, 2003 8:12 pm

I test it many times,but I still got WA. Could anyone find my bugs?
Thanks in advance.

Code: Select all

#include<stdio.h>

int main(void)
{
	int n,i,count; /* 1<=n<=50 */
	long long num[50];
	long long value[51];

	while(scanf("%d",&n)==1) {
		for(i=0;i<n;i++) {
			scanf("%lld",&num[i]);
			num[i]*=-1;
		}

		value[0]=num[0];
		value[1]=1;
		count=1;
		while(count<n){
			for(i=count;i>=1;i--) 
				value[i]=num[count]*value[i]+value[i-1];					
			value[count+1]=1;	
			value[0]*=num[count++];		
		}
		
		if(n!=1) printf("x^%d",n);
		else printf("x");
		for(i=n-1;i>0;i--) {
			if(i==1) {
				if(value[1]>0 && value[1]!=1) printf(" + %dx",value[1]);
				else if(value[1] <0 && value[1]!=-1) printf(" - %dx",-value[1]);
				else if(value[1]==1) printf(" + x");
				else if(value[1]==-1) printf(" - x");
				continue;
			}

			if(value[i]>0 && value[i]!=1) printf(" + %dx^%d",value[i],i);
			else if(value[i]<0 && value[i]!=-1) printf(" - %dx^%d",-value[i],i);
			else if(value[i]==1) printf(" + x^%d",i);
			else if(value[i]==-1) printf(" - x^%d",i);

		}
		if(value[0]>=0) printf(" + %d",value[0]);
		else if(value[0]<0) printf(" - %d",-value[0]);
		printf(" = 0\n");

	}

	return 0;
}

[c][/c]

yatsen · Post by **yatsen** » Wed Jan 08, 2003 8:13 am

To supermin:
Because the coeffecient may be as large as 10^15, you choose long long data type for value[]. That's right.
But when you use printf function, you use %d instead of using %lld.
That's wrong.

supermin · Post by **supermin** » Wed Jan 08, 2003 12:49 pm

hmm..I miss this.sorry.I got AC now.Thank you!!

Bistromath · Post by **Bistromath** » Mon Jan 13, 2003 2:07 pm

to tat tvam asi :

i used long long to store coefficients and now got AC

many thanks for ur help

Dmytro Chernysh · Post by **Dmytro Chernysh** » Mon Apr 28, 2003 10:41 pm

Yes, but if
1
0
the output should be
x + 0 = 0 ?
or
x^1 + 0 =0
or
anything else?

OJ Board

10326 - The Polynomial Equation

10326 - The Polynomial Equation

10326 - Polynomail Equation - Why I got WA?

Thank you!

10326-----what's special about it