10394

Sajid · Post by **Sajid** » Mon Mar 03, 2003 10:10 am

i got this WA. can any1 tell the some critical inputs?

saiqbal · Post by **saiqbal** » Sun Mar 09, 2003 5:34 pm

there is no critical input for this problem really bcoz u know all possible inputs!!

btw try the following input and output:

input:
1
10
100
1000
10000
100000

output:
(3, 5)
(107, 109)
(3821, 3823)
(79559, 79561)
(1260989, 1260991)
(18409199, 18409201)

hope it'll help

Sajid · Post by **Sajid** » Sun Mar 23, 2003 10:29 pm

thanx for help

but i m facing problem with the array size, as i m using Turbo C++ 3.0. and so i cant see the value for the all input. then, what can i do now? plz, help...

saiqbal · Post by **saiqbal** » Mon Mar 24, 2003 2:33 pm

you'd better use VC.
TC wud never support such large array required for this problem.

thanx
-sohel

Dominik Michniewski · Post by **Dominik Michniewski** » Mon Mar 24, 2003 2:49 pm

but you still can do it in this way:

create algorithm working with array i.e. 1000 elements and before sending solution create bigger array and send such solution. I did problems in this way in BC3.1 long time ago and it's work

other method is using less memory consuming algorithms

)

Dominik

Jalal · Post by **Jalal** » Fri Mar 28, 2003 5:43 pm

But it may show output or memory limit exit.
Wt u think about it Michniewski?
i tried with such technic in another prob but didnt worked

Eric · Post by **Eric** » Mon Apr 07, 2003 1:29 pm

I get TLE. Can anyone help me improve my algorithm?

Jalal · Post by **Jalal** » Mon Apr 07, 2003 2:50 pm

Change ur algorithm.
Use the algorithm(for twin prime) to reduce unwanted calculation.
WIthout it its not possible to pass TLE

Dominik Michniewski · Post by **Dominik Michniewski** » Mon Apr 07, 2003 2:57 pm

Jalal, I don't think so ....
If you run program under Windows / DOS you know how much memory you use ... Then If you increase limits, you know memory usage, i.e.

if your table has 1000 elements, and program use 100kB ram, then after change limit to 100000, than your program should use 10MB ram ....

And you know how is maximal limit for your arrays

Other way is counting memory self

Dominik

Eric · Post by **Eric** » Mon Apr 07, 2003 3:04 pm

But how can I improve it?
I need to check all the odd to see if they are prime, shouldn't me?
And the algorithm of checking prime is standard...
Can anyone give me some hints?

Jalal · Post by **Jalal** » Wed Apr 09, 2003 12:30 am

Thanx Michniewski!
u r right.........

eric!
try with the following one

for(m= 6 ; m < x; m+=6)
if(prime(m-1) && prime(m+1))
printf("%ld %ld\n", m-1, m+1);

Eric · Post by **Eric** » Wed Apr 09, 2003 5:41 am

Thanks.

But I only know little about C++ and I can hardly understand your code.

Eric · Post by **Eric** » Wed Apr 09, 2003 12:49 pm

Thanks, Jalal.
I change my algorithm and gradually get accepted.
Your post has given me some hint.

Max108 · Post by **Max108** » Tue Jun 17, 2003 12:23 am

Hi,

This is my code, it is very simple but it finishes calculationes within the alloted time so thats just fine for me but im getting WA and i dont know why!!!!

[cpp]
#include <fstream.h>
#include <math.h>

/*Returns one if the number is prime, else it returns zero*/
int isPrime(int n)
{
int root = sqrt(n);
for(int i=3; i<root; i+=2)
if(n % i == 0)
return 0;

return 1;
}

void main()
{

long i=0,j;
long calc[100000][2]={3,5};
char *table = new char[18409201];
//ifstream cin;
//cin.open("texto.txt"); //just for testing

/*This is the core of the algorithm*/
for( i=3; i<=4290; i+=2)
if(isPrime(i))
for(j=i+i-1; j<18409201; j+=i)
table[j] = 0;

/*We now store ALL the twin primes*/
for(j=4,i=1; j<=18409201; j+=6)
if(table[j]!=0 && table[j+2]!=0)
{
calc[0]=j+1;
calc[1]=j+3;
i++;
}

/*Get the input and give the output*/
while(cin>>i)
cout<<"("<<calc[i-1][0]<<", "<<calc[i-1][1]<<")"<<endl;

}

[/cpp]

Could some of you guys please help me, I tested it with all the inputs that I culd imagine. is it something about the sapce ASCII32? omg so confused

Max108 · Post by **Max108** » Tue Jun 17, 2003 12:32 am

can any of you guys tellme whats wrong with my code,
im getting WA

[cpp]

#include <fstream.h>
#include <math.h>

/*Returns one if the number is prime, else it returns zero*/
int isPrime(int n)
{
int root = sqrt(n);
for(int i=3; i<root; i+=2)
if(n % i == 0)
return 0;

return 1;
}

void main()
{

long i=0,j;
long calc[100000][2]={3,5};
char *table = new char[18409201];
//ifstream cin;
//cin.open("texto.txt"); //just for testing

/*This is the core of the algorithm*/
for( i=3; i<=4290; i+=2)
if(isPrime(i))
for(j=i+i-1; j<18409201; j+=i)
table[j] = 0;

/*We now store ALL the twin primes*/
for(j=4,i=1; j<=18409201; j+=6)
if(table[j]!=0 && table[j+2]!=0)
{
calc[0]=j+1;
calc[1]=j+3;
i++;
}

/*Get the input and give the output*/
while(cin>>i)
cout<<"("<<calc[i-1][0]<<", "<<calc[i-1][1]<<")"<<endl;

}
[/cpp]

OJ Board

10394 - Twin Primes

10394 Bad output or WA? PLZ help!

confused