Page 1 of 2
10326 - The Polynomial Equation
Posted: Sun Jul 14, 2002 5:38 pm
by Revenger
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]
10326 - Polynomail Equation - Why I got WA?
Posted: Thu Jul 18, 2002 12:58 am
by oker
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]
Posted: Thu Jul 18, 2002 4:36 am
by wyvmak
[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?
Thank you!
Posted: Thu Jul 18, 2002 7:22 am
by oker
Thank you for your help! I made so foolish mistake
I got AC now!
10326-----what's special about it
Posted: Sun Aug 11, 2002 6:45 pm
by sayeed
/*@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
Posted: Wed Nov 20, 2002 5:00 pm
by Bistromath
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]
Posted: Fri Dec 13, 2002 7:01 am
by yatsen
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
Posted: Sun Dec 29, 2002 5:30 pm
by Bistromath
Thanks for your help yatsen
But my program output is correct in the case 1 0
Really don't know where is the mistake
Posted: Sun Dec 29, 2002 8:48 pm
by ..
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
Posted: Tue Dec 31, 2002 12:15 am
by tat tvam asi
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
Posted: Tue Jan 07, 2003 8:12 pm
by supermin
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]
Posted: Wed Jan 08, 2003 8:13 am
by yatsen
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.
Posted: Wed Jan 08, 2003 12:49 pm
by supermin
hmm..I miss this.sorry.I got AC now.Thank you!!
Posted: Mon Jan 13, 2003 2:07 pm
by Bistromath
to tat tvam asi :
i used long long to store coefficients and now got AC
many thanks for ur help
Posted: Mon Apr 28, 2003 10:41 pm
by Dmytro Chernysh
Yes, but if
1
0
the output should be
x + 0 = 0 ?
or
x^1 + 0 =0
or
anything else?