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

Post by Joel J. Hernandez » Wed May 17, 2006 11:58 pm

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[750000];
    triple t[250000]; 
    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[0].x=3; t[0].y=4; t[0].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[0].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; 
        } 
    }
}

Thanks in advance.
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!!!!!!!!!!!!!

Post by Joel J. Hernandez » Thu May 18, 2006 1:55 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu May 18, 2006 9:09 am

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

Post by fernando » Thu May 18, 2006 8:11 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

Post by klam » Fri May 19, 2006 12:37 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
Location: Calgary, Canada

Post by Darko » Wed Jul 26, 2006 1:32 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

Post by nev4 » Wed Aug 09, 2006 4:20 pm

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

Post by nev4 » Wed Aug 09, 2006 4:34 pm

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

Post by rk » Tue Aug 15, 2006 7:40 am

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

Post by rk » Tue Aug 15, 2006 7:41 am

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

Post by nev4 » Tue Aug 15, 2006 4:08 pm

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:

Post by hedgehog1204 » Mon Aug 21, 2006 8:54 am

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

Post by ulgerang » Sun Dec 10, 2006 3:56 am

I had "Time Limit Exceeded
I don't know what wrong is.
please , give me advice.



#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[0]=false;
RP_map[1]=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

Post by helloneo » Sun Dec 10, 2006 5:38 am

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?

Post by ubernewb » Mon Aug 06, 2007 8:12 pm

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

Post Reply

Return to “Volume 1 (100-199)”