106 - Fermat vs. Pythagoras

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Joel J. Hernandez
New poster
Posts: 8
Joined: Tue May 16, 2006 9:31 am
Location: Las Vegas, NV. USA.
Contact:

106 WA but it works for all cases....???WHY WA

Here is my code, if you test in your computer you will see that it gives the correct answer for every input, but the judge keeps replying WA....

What is wrong?????

Code: Select all

#include <iostream>
#include <cmath>
using namespace std;
struct triple
{
int x, y, z;
};
void q_sort(triple numbers[], int left, int right)
{
int l_hold, r_hold;
triple extra;
int pivot;
l_hold = left;
r_hold = right;
pivot = numbers[left].z;
extra.x=numbers[left].x;
extra.y=numbers[left].y;
extra.z=numbers[left].z;
while (left < right)
{
while ((numbers[right].z >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left].x = numbers[right].x;
numbers[left].y = numbers[right].y;
numbers[left].z = numbers[right].z;
left++;
}
while ((numbers[left].z <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right].x = numbers[left].x;
numbers[right].y = numbers[left].y;
numbers[right].z = numbers[left].z;
right--;
}
}
numbers[left].x = extra.x;
numbers[left].y = extra.y;
numbers[left].z = extra.z;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
void quickSort(triple numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
void main()
{
int i, j, k, a, b, c, ax1, bx1, cx1, c1, c2;
int n;
int temp;
triple t;
while(cin>>n)
{
c1=0; c2=0;
if(n<5)
{
cout<<c1<<" "<<n<<endl;
}
else
{
for(i=0; i<=n; i++)
{
temp[i]=0;
}
i=1; k=0;
t.x=3; t.y=4; t.z=5;
while(k<i)
{
a=t[k].x;
b=t[k].y;
c=t[k].z;
cx1=2*a-2*b+3*c;
bx1=2*a-b+2*c;
ax1=a-2*b+2*c;
if(cx1<=n)
{
t[i].x=ax1;
t[i].y=bx1;
t[i].z=cx1;
i++;
c1++;
}
cx1=2*a+2*b+3*c;
bx1=2*a+b+2*c;
ax1=a+2*b+2*c;
if(cx1<=n)
{
t[i].x=ax1;
t[i].y=bx1;
t[i].z=cx1;
i++;
c1++;
}
cx1=3*c+2*b-2*a;
bx1=b+2*c-2*a;
ax1=2*b+2*c-a;
if(cx1<=n)
{
t[i].x=ax1;
t[i].y=bx1;
t[i].z=cx1;
i++;
c1++;
}
k++;
}
quickSort(t, c1);
i=1;
while(t.z*i<=n)
{
for(j=0; j<=c1; j++)
{
if(t[j].z*i>n)
{
break;
}
temp[(t[j].z)*i]=(t[j].z)*i;
temp[(t[j].x)*i]=(t[j].x)*i;
temp[(t[j].y)*i]=(t[j].y)*i;
}
i++;
}
for(i=1; i<=n; i++)
{
if(temp[i]==0)
{
c2++;
}
}
cout<<c1+1<<" "<<c2<<endl;
}
}
}

The harder you work to find the solution, the more you learn in the process.

Joel J. Hernandez
New poster
Posts: 8
Joined: Tue May 16, 2006 9:31 am
Location: Las Vegas, NV. USA.
Contact:

106 FINALLY!!!!!!!!!!!!!

Ok thanks anyways guys.
I finally got ACC, I used dynamic memory and also my method for finding all triples is quite fast, like O(nlogn).

I submitted this program more than 30 times and always got WA or RE and it was because of the arrays thing, so be carefull.

Thank you.

I'm so happy!!!!!
The harder you work to find the solution, the more you learn in the process.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hi Joel,

I'm very glad for you that you got accepted, but in the process of getting there you created four new threads for a problem that has many threads already. Please conform to the forum rules, and only create a new thread if there is no existing thread for your problem, otherwise post in an existing thread.

lj

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm
most problems in UVA will show Time Limit Exceeded if they run for more than 10 seconds, so maybe you are misunderstanding the meaning of your result, it means that your program ran during 10.1 seconds, and as it didn't finish you got Time Limit Exceeded, the exact time your program solved the problem is unknown

klam
New poster
Posts: 5
Joined: Thu May 18, 2006 1:18 am
im just wondering, can't post like this one be removed? cause this is the kind of post that makes finding what you want heavy.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
It generates all relatively prime triples, not sure where that "some" part came from. Some numbers occur in more than one triple, but they are still relatively prime.

I just solved this, generating relatively prime triples is ok (my source is Ore's Number Theory and Its History), but counting unused numbers takes forever (5s+ with Java).

There seems to be a better way than to just count them every time, but I can't come up with it. I thought about marking them all, but then, for instance, 6 would be marked (because (3 4 5) -> (6 8 10)), but if n==6, it should be counted as unmarked.

Any suggestions?

nev4
New poster
Posts: 15
Joined: Sun Apr 30, 2006 10:19 am
Location: Lithuania
Hi,
i found 13 of them as N = 100, too.
10) 56 33 65
12) 16 63 65
15) 36 77 85
These don't belong, do they?
33 = 11 * 3; 65 = 5 * 13;
63 = 7 * 9;
77 = 11 * 7; 85 = 5 * 17;
what's wrong here?

nev4
New poster
Posts: 15
Joined: Sun Apr 30, 2006 10:19 am
Location: Lithuania
ah, the triple cant have the same dividers... It's hard to get right meaning.

rk
New poster
Posts: 6
Joined: Thu Jul 06, 2006 7:51 pm

RE in 106

i am getting Invalid memory reference in 106. the prob works fine on my pc. no idea abt the error, please help....

code is

Code: Select all

# include <iostream.h>
# include <stdio.h>
using namespace std;
int p(int x,int y)
{int a,b=(x<y?x:y);
for(a=2;a<=b;a++)
if(x%a==0 && y%a==0) return 0;
return 1;
}
int main()
{int x,y,n,a,b,c,d,*X;
while(scanf("%d",&n)>0)
{X=new int[n+1];for(a=0;a<n;a++) X[a]=0;
for(a=1,x=0,y=n;a<=n/2;a++) for(b=a+1;b<=n/2;b++)
{d=a*a+b*b;
if((a%2==0 || b%2==0) && p(a,b) && d<=n)
{x+=1;
if(!X[b*b-a*a-1]) {X[b*b-a*a-1]=1;y--;}
if(!X[2*a*b-1]) {X[2*a*b-1]=1;y--;}
if(!X[a*a+b*b-1]) {X[a*a+b*b-1]=1;y--;}
for(c=2;;c++)
if(d*c<=n)
{if(!X[c*b*b-c*a*a-1]) {X[c*b*b-c*a*a-1]=1;y--;}
if(!X[c*2*a*b-1]) {X[c*2*a*b-1]=1;y--;}
if(!X[c*a*a+c*b*b-1]) {X[c*a*a+c*b*b-1]=1;y--;}
}
else break;
}
}
cout<<x<<" "<<y<<"\n";delete []X;
}
return 0;
}
thnx

rk
New poster
Posts: 6
Joined: Thu Jul 06, 2006 7:51 pm
the idea used was

Any primitive Pythagorean triplet (m,n,p) is of the form
p=x*x+y*y
m=x*x-y*y
n=2*x*y
where x and y are co prime and at least one of x and y is even. Also all other Pythagorean triplets are simply obtained by taking multiples of these. These are well known results from number theory, and should be used to solve this problem.

nev4
New poster
Posts: 15
Joined: Sun Apr 30, 2006 10:19 am
Location: Lithuania
if u get RE u probably get outside of array bounds

hedgehog1204
New poster
Posts: 13
Joined: Sat Oct 04, 2003 12:03 am
Location: USA
Contact:
Try using less multidimensional arrays. Here is the example of my code in Python:

Code: Select all

def prime(i, j, k):
myMax = max([i, j, k])
for l in range(2, myMax):
if i%l==0 and j%l==0 and k%l==0:
return False
return True

file = open('input.txt')
for line in file:
nTriple = 0
n = int(line.strip())
triple = [0 for i in range(n+1)]
for i in range(1, n-1):
for j in range(i+1, n):
for k in range(j+1, n+1):
if i*i + j*j == k*k:
triple[i], triple[j], triple[k] = 1, 1, 1
if prime(i, j, k):
nTriple += 1
notPartOfTriples = 0
for i in range(1, n+1):
if triple[i] == 0:
notPartOfTriples += 1
print nTriple, notPartOfTriples
file.close()

Its slow but it works (with the problem statement examples that is lol)

ulgerang
New poster
Posts: 1
Joined: Sun Dec 10, 2006 3:46 am

#106 Time Limit Exceeded

I had "Time Limit Exceeded
I don't know what wrong is.

#include <stdio.h>
#include <math.h>

#define N 1000000
#define SQRT_N 1000

bool RP_map[SQRT_N+1][SQRT_N+1];
bool integers[N+1];

void fill_RP_map( )
{
int i,j;

for(i=0;i<=SQRT_N;i++)
{
RP_map=false;
RP_map=true;
}

for(i=0;i<=SQRT_N;i++)
for(j=2;j<i;j++)
RP_map[j]= RP_map[j][i%j];
}

int main()
{
unsigned long n;
unsigned long i,j,k;
unsigned long sqrt_n;
unsigned long n_prime;
unsigned long n_elements;
unsigned long sq_i,sq_j,x,y,z;

fill_RP_map();
while(scanf("%ld",&n))
{
for(i=1;i<=n;i++)
integers=0;

sqrt_n= sqrt(n);

n_prime=0;
n_elements=0;
for(i=1;i<=sqrt_n;i++)
for(j=1;j<i;j++)
{

sq_i=i*i;
sq_j=j*j;

z=sq_i+sq_j;

if(z > n )
break;

y=2*i*j;
x=sq_i-sq_j;

integers[x]=true;
integers[y]=true;
integers[z]=true;

if( (i+j)%2 && RP_map[j]==1)
{
n_prime++;

for(k=2; k*z <n;k++)
{
integers[x*k]=true;
integers[y*k]=true;
integers[z*k]=true;
}
}
}

for(i=1;i<=n;i++)
n_elements+=integers;

printf("%ld %ld\n",n_prime,n-n_elements);
}

return 0;
}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
you have to search first..
and don't open a new thread if one already exists

check this out

http://online-judge.uva.es/board/viewtopic.php?t=1429

ubernewb
New poster
Posts: 6
Joined: Mon May 01, 2006 8:26 pm

106 Fermat vs. Pythagoras WA, why?

I tried all the inputs I found on this board, and the output matches the correct output, but I'm still getting WA on this one. Some sample input/output here.
Input:

Code: Select all

10
100
1000
10000
100000
1000000
123
1234
12345
123456
Output:

Code: Select all

1 4
16 27
158 205
1593 1669
15919 14844
159139 133926
19 26
197 238
1963 2058
19644 18142
Any ideas? I can PM or post my source code if someone with ACC wants to see it.
Thanks