Moderator: Board moderators

longer
New poster
Posts: 2
Joined: Thu Nov 06, 2003 9:44 am

### This is simply stupid

The problem setter should work hard on something, at least English.

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm

### 10524 -Matriz Reloaded WA :(

I've tried my code with all test inputs and outputs found in this board, but i still get WA.
What happens to this code? How can I get AC?

[c]#include <stdio.h>

# define MAX 100

int main()
{
float a[MAX][MAX],b[MAX][MAX],c[MAX][MAX];
float d,m;
int i,j,k,p,n=0;

while(scanf("%d",&n))
{
if(n==0) return(1);
if(n==1)
{
printf("Not possible\n");
p=0;
break;
}
p=1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%f",&a[j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
b[j]=1;
else
b[j]=0;
}
}
if(a[0][0]==0)
{
for(j=0;j<n;j++)
{
c[0][j]=a[1][j];
a[1][j]=a[0][j];
a[0][j]=c[0][j];
c[0][j]=b[1][j];
b[1][j]=b[0][j];
b[0][j]=c[0][j];
}
}

for(i=0;i<n;i++)
{
d=a;
if(d==0)
{
printf("Not possible\n");
p=0;
break;
}
for(j=0;j<n;j++)
{
a[j]=a[j]/d;
b[j]=b[j]/d;
}
for(k=0;k<n;k++)
{
if(k!=i)
{
m=a[k];
for(j=0;j<n;j++)
{
a[k][j]=a[k][j]-(a[i][j]*m);
b[k][j]=b[k][j]-(b[i][j]*m);
}
}
}
}

if(p)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%.6f",b[i][j]);
printf(" ");
}
printf("\n");
}
printf("\n");
}
else printf("\n");
}
}[/c]

Thanks!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I have 2 suggestions:

use doubles, and use an epsilon when checking if it's zero..

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm
what is an epsilon?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Something small and squiggly with no legs, for example 1e-12.

When doing floating point computations, it is good practice to use an epsilon in comparisons, since floating point operations are (almost) never exact. For instance, in order to check if two doubles a and b are equal, one should check if |a-b| < epsilon, rather than if a==b.

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm
Ok, i've tried with the epsilon and I still got WA. If I change the type from float to double, fails all. Even the sample tests are correct.

Here my sample inputs:

Code: Select all

``````2
1 2
2 1

2
1 2
2 1

4
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0

10
9.5013 6.1543 0.5789 0.1527 8.3812 1.9343 4.9655 7.2711 7.9482 1.3652
2.3114 7.9194 3.5287 7.4679 0.1964 6.8222 8.9977 3.0929 9.5684 0.1176
6.0684 9.2181 8.1317 4.4510 6.8128 3.0276 8.2163 8.3850 5.2259 8.9390
4.8598 7.3821 0.0986 9.3181 3.7948 5.4167 6.4491 5.6807 8.8014 1.9914
8.9130 1.7627 1.3889 4.6599 8.3180 1.5087 8.1797 3.7041 1.7296 2.9872
7.6210 4.0571 2.0277 4.1865 5.0281 6.9790 6.6023 7.0274 9.7975 6.6144
4.5647 9.3547 1.9872 8.4622 7.0947 3.7837 3.4197 5.4657 2.7145 2.8441
0.1850 9.1690 6.0379 5.2515 4.2889 8.6001 2.8973 4.4488 2.5233 4.6922
8.2141 4.1027 2.7219 2.0265 3.0462 8.5366 3.4119 6.9457 8.7574 0.6478
4.4470 8.9365 1.9881 6.7214 1.8965 5.9356 5.3408 6.2131 7.3731 9.8833

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1
5

0``````
Here my outputs for that samples:

Code: Select all

``````-0.333333 0.666667
0.666667 -0.333333

-0.333333 0.666667
0.666667 -0.333333

Not possible

-0.070885 0.190366 -0.064787 -0.466908 -0.007342 0.132556 0.393283 0.254180 0.106229 0.074244
0.106282 0.072758 -0.055644 -0.107017 0.006025 -0.143474 0.032887 0.017552 -0.003056 0.132946
-0.158503 0.248146 0.074397 -0.508077 -0.171241 0.390370 0.506519 -0.257355 0.004178 -0.179324
-0.158219 0.072117 0.018435 -0.126107 -0.073899 0.204099 0.305098 -0.170877 -0.001857 -0.091075
0.038540 0.060938 -0.058235 -0.168922 -0.065009 0.306328 0.203311 0.011262 -0.160097 -0.158063
0.026725 -0.086133 -0.081818 0.146694 0.111831 -0.137008 -0.228790 0.202612 0.059928 0.065387
0.111459 -0.174756 0.048315 0.512155 0.230113 -0.438042 -0.603086 0.271165 0.009040 0.107617
0.074352 -0.538201 0.230776 1.059829 0.164412 -0.692106 -0.874826 0.362629 0.179767 0.055162
-0.037257 0.248516 -0.040264 -0.435959 -0.229971 0.508425 0.460295 -0.241112 -0.128389 -0.153880
-0.027344 0.037008 -0.028874 -0.178656 -0.028273 0.168767 0.114784 -0.051992 -0.071996 0.058601

Not possible

Not possible``````
Any more idea?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Well,

Code: Select all

``````1
5
``````
Should definitely be possible, right? =)

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm
I've read on another thread that that case should be not possible.
I've tried with that case answering 0.200000, but still get WA.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Mine outputs 0.2, and I got AC..

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm
Ok, I've changed that.
But what's the matter then?

mrbrett
New poster
Posts: 6
Joined: Thu Mar 11, 2004 6:28 pm
Here is the status of my code now. With all the corrections suggested. But still get WA.

[c]#include <stdio.h>
#include <math.h>
#define MAX 100

int main()
{
double a[MAX][MAX],b[MAX][MAX],c[MAX][MAX];
double d,m;
int i,j,k,p,n=0;

while(scanf("%d",&n))
{
if(n==0) return(1);
p=1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%lf",&a[j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
b[j]=1;
else
b[j]=0;
}
}
if(a[0][0]==0)
{
for(j=0;j<n;j++)
{
c[0][j]=a[1][j];
a[1][j]=a[0][j];
a[0][j]=c[0][j];
c[0][j]=b[1][j];
b[1][j]=b[0][j];
b[0][j]=c[0][j];
}
}

for(i=0;i<n;i++)
{
d=a;
if(fabs(d)<10e-12)
{
printf("Not possible\n");
p=0;
break;
}
for(j=0;j<n;j++)
{
a[j]=a[j]/d;
b[j]=b[j]/d;
}
for(k=0;k<n;k++)
{
if(k!=i)
{
m=a[k];
for(j=0;j<n;j++)
{
a[k][j]=a[k][j]-(a[i][j]*m);
b[k][j]=b[k][j]-(b[i][j]*m);
}
}
}
}

if(p)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%.6lf",b[i][j]);
printf(" ");
}
printf("\n");
}
printf("\n");
}
else printf("\n");
}
}[/c]

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

### 10524

What does no pivoting mean?

I've seen some posts that say it means that the output for

Code: Select all

``````4
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
``````
is "Not possible", but I don't see why it should be, or even how to test for this case. Maybe its because I'm tired right now. but thats still annoying. If you can find the inverse, then you can find the with swapping rows, than you can also solve it with only row additions and multiplications.

Hmm, I'm going to try something. Let you know if I make it AC.