10871 - Primed Subsequence
Moderator: Board moderators
-
- Learning poster
- Posts: 77
- Joined: Fri Dec 17, 2004 11:06 am
- Location: East West University, Dhaka, Bangladesh
- Contact:
Posting my code that gives correct ans for the bijon's given input.
If anyone can find my mistake then I will be very much grateful to him. This problem is making me crazy. Plz help me. Anyway, thanks in advance.
Code: Select all
#include<stdio.h>
#include<math.h>
#define max 10011
#define pmax 20000010
char prime[pmax];
int bank[max+100];
int isPrime(long);
void siv()
{
long i,j,k;
prime[0]='x';
prime[1]='x';
for(i=3;i<=(int)sqrt(pmax);i=i+2)
{
if(prime[j]!='x')
{
k=i;
j=k+2*k;
while(j<=pmax-5)
{
prime[j]='x';
j=j+2*k;
}
}
}
}
int isPrime(long a)
{
if(a==2)
return 1;
if(a%2!=0)
if(prime[a]!='x')
return 1;
return 0;
}
int main()
{
int N,n,i,j,sum,s,e;
siv();
//freopen("F:\\input.in","r",stdin);
//freopen("C:\\output.out","w",stdout);
scanf("%d",&N);
while(N--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&bank[i]);
s=0;
e=10011;
for(i=0;i<n;i++)
{
sum=0;
for(j=i;j<n;j++)
{
sum=sum+bank[j];
if(isPrime(sum) && i!=j)
{
if(j-i<e-s)
{
s=i;
e=j;
}
}
}
}
if(e!=10011)
{
printf("Shortest primed subsequence is length %d:",e-s+1);
for(i=s;i<=e;i++)
printf(" %d",bank[i]);
printf("\n");
}
else
{
printf("This sequence is anti-primed.\n");
}
}
return 0;
}
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/
http://groups.yahoo.com/group/acm_solver/
-
- Learning poster
- Posts: 77
- Joined: Fri Dec 17, 2004 11:06 am
- Location: East West University, Dhaka, Bangladesh
- Contact:
Do you mean "300000000" or "30000000" ?bijon wrote:the number will be at best 9999*10000 .
so how do you check prime if the number will be greater then 300000000?
I got to know from a previous post on this problem that the number will not be too large. That's why I took such a small upper limit. Would you please tell me the upper limit for my SIV ?
Thanks.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/
http://groups.yahoo.com/group/acm_solver/
Re: 10871 - Primed Subsequence
Weak test!!!!
For such test:
1
10000 10000 100000.....10000
My program should get MLE! But it got AC!
For such test:
1
10000 10000 100000.....10000
My program should get MLE! But it got AC!