OJ Board

Posted: **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.

Posted: **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!!!!!

Posted: **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

Posted: **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

Posted: **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.

Posted: **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?

Posted: **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?

Posted: **Wed Aug 09, 2006 4:34 pm**

ah, the triple cant have the same dividers... It's hard to get right meaning.

Posted: **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

Posted: **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.

Posted: **Tue Aug 15, 2006 4:08 pm**

if u get RE u probably get outside of array bounds

Posted: **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)

Posted: **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;
}

Posted: **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

Posted: **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

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

OJ Board

106 - Fermat vs. Pythagoras

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

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

RE in 106

#106 Time Limit Exceeded

106 Fermat vs. Pythagoras WA, why?