406 - Prime Cuts

[rajib_sust]

rhsumon ,
some of case your code give wrong answer
your out put::

3 1
3 1: 2 -858993460

my AC output::

3 1
3 1: 2

cheek it carefully


Rajib, sust

[rhsumon]

Thanks Ragib
Silly Mistake.
Anyway r u in CSE if then which Semester
Mail Me
rhsumon@gmail.com
Thanks Again

[peterwen1990]

Can anyone tell me why I awalays get Time limit exceeded
Thanks

Code: Select all

#include <stdio.h>
int main()
{
int prime[200]={1},n,c,i,j,num=1,x;
while(scanf("%d %d",&n,&c)!=EOF)
{

   for(i=2;i<=n;i++)
   {
    for(j=2;j<=i;j++)
     if(i%j==0 && j!=i)
     {
      break;
     }
     else if(i%j==0 && j==i)
     {
      prime[num]=i;
      num++;
     }
   }
  printf("%d %d:",n,c);
  if(2*c>n)
  {
   for(x=0;x<num;x++)
     printf(" %d",prime[x]);
  }
  else if(2*c<n && (num)%2==1)
  {
     {
      for(x=((num/2)-(c/2-1)-1);x<(num/2+c+1)-1;x++)
      printf(" %d",prime[x]);
     }


  }
  else if(2*c<n && num%2==0)
  {
    {
     for(x=((num/2)-c);x<(num/2+c);x++)
      printf(" %d",prime[x]);
    }
  }
printf("\n\n");
num=1;



}


      return 0;
}

[lnr]

To peterwen1990

for loop upto n.
It is a slow process.
You can check upto sqrt(n).

Code: Select all

for(i=2;i<=n;i++)
   {
    for(j=2;j<=sqrt(i);j++)
     if(i%j==0 && j!=i)
     {
      break;
     }
     else if(i%j==0 && j==i)
     {
      prime[num]=i;
      num++;
     }
   }

May be this is the reason.
Precalcution for prime number with seive method will be faster.

[peterwen1990]

To peterwen1990


Thank you.That is my program problem.

[theharshest]

please help.. i am getting WA

Code: Select all

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
  int m,n,sz;
  int p;
  
  vector<bool> v;
  vector<int> vi;
  
  while(cin>>m>>n)
  {
    vi.clear();
    v.resize(m+1,0);
    p=sqrt(m);
    
    v[0]=0;
    v[1]=0;
    
    for(int i=2;i<=p;i++)
      if(!v[i])
        for(int j=i*i;j<=m;j+=i)
          v[j]=1;
    
    cout<<m<<" "<<n<<":";
    
    int sum=0;
                 
    for(int i=1;i<v.size();i++)   
    {
      if(!v[i])
      {
        vi.push_back(i);        
      }
    }
    
    sz=vi.size();
    
    if(vi.size()%2==0)
    {
     if(sz/2-n/2>=0)
     {
      for(int i=(sz/2)-n;i<(n+sz/2);i++)
      {  
        if(i==vi.size())
         break;
        
        cout<<" "<<vi[i];
      }
     }
     else
     {
       for(int i=0;i<vi.size();i++)
         cout<<" "<<vi[i];    
     }
    }
    else
    {
      if((sz/2)-(2*n-2)/2>=0)
      {
        for(int i=(sz/2)-(2*n-2)/2;i<=((2*n-2)/2+sz/2);i++)
        {
        if(i==vi.size())
         break;
         
        cout<<" "<<vi[i];
        }
      }
      else
      {
        for(int i=0;i<vi.size();i++)
         cout<<" "<<vi[i];     
      }
    }
    
    cout<<endl<<endl;
  }
}

[Toufique]

I am getting presentation error.But can't understand why.please help me out.

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

int main(void)
{
int a[1001];
int i,j,n,k,c,m,q,r;
while(scanf("%d%d",&n,&c)==2)
{
k=0;
a[0]=0;
a[1]=1;
for(i=2;i<=n;i++)
{
a=1;
}
for(i=2;i<=sqrt(n);i++)
{
if(a==0)
{
continue;
}
for(j=2;i*j<(n+1);j++)
{
a[i*j]=0;
}
}
for(i=0;i<=n;i++)
{
if(a==1)
{
k++;
}
}
if(k%2==0)
{
r=2*c;
}
else
{
r=2*c-1;
}
if(r>k)
{
printf(" %d %d: ",n,c);
for(i=1;i<=n;i++)
{
if(a==1)
{
printf("%d ",i);
}
}
printf("\n\n");
}
else
{
q=(k-r)/2;
m=0;
for(i=1;m<q;i++)
{
if(a==0)
{
continue;
}
else
{
a=0;
m++;
}
}
m=0;
for(i=n;m<q;i--)
{
if(a==0)
{
continue;
}
else
{
a=0;
m++;
}
}
printf(" %d %d: ",n,c);
for(i=1;i<=n;i++)
{
if(a==1)
{
printf("%d ",i);
}
}
printf("\n\n");
}
}
return 0;
}

[allenlam]

some test cases

Code: Select all

1 1
2 1
3 2
4 3
5 2
6 3
7 2
8 2
9 2
10 9
11 9
12 4
13 4
14 3
15 8
16 13
17 10
18 16
19 14
20 17
21 20
22 8
23 9
24 15
25 2
26 3
27 7
28 1
29 14
30 10
31 10
32 24
33 32
34 15
35 18
36 4
37 11
38 34
39 18
40 27
41 35
42 33
43 32
44 10
45 12
46 43
47 40
48 21
49 22
50 15

output

Code: Select all

1 1: 1

2 1: 1 2

3 2: 1 2 3

4 3: 1 2 3

5 2: 1 2 3 5

6 3: 1 2 3 5

7 2: 2 3 5

8 2: 2 3 5

9 2: 2 3 5

10 9: 1 2 3 5 7

11 9: 1 2 3 5 7 11

12 4: 1 2 3 5 7 11

13 4: 1 2 3 5 7 11 13

14 3: 2 3 5 7 11

15 8: 1 2 3 5 7 11 13

16 13: 1 2 3 5 7 11 13

17 10: 1 2 3 5 7 11 13 17

18 16: 1 2 3 5 7 11 13 17

19 14: 1 2 3 5 7 11 13 17 19

20 17: 1 2 3 5 7 11 13 17 19

21 20: 1 2 3 5 7 11 13 17 19

22 8: 1 2 3 5 7 11 13 17 19

23 9: 1 2 3 5 7 11 13 17 19 23

24 15: 1 2 3 5 7 11 13 17 19 23

25 2: 5 7 11 13

26 3: 3 5 7 11 13 17

27 7: 1 2 3 5 7 11 13 17 19 23

28 1: 7 11

29 14: 1 2 3 5 7 11 13 17 19 23 29

30 10: 1 2 3 5 7 11 13 17 19 23 29

31 10: 1 2 3 5 7 11 13 17 19 23 29 31

32 24: 1 2 3 5 7 11 13 17 19 23 29 31

33 32: 1 2 3 5 7 11 13 17 19 23 29 31

34 15: 1 2 3 5 7 11 13 17 19 23 29 31

35 18: 1 2 3 5 7 11 13 17 19 23 29 31

36 4: 3 5 7 11 13 17 19 23

37 11: 1 2 3 5 7 11 13 17 19 23 29 31 37

38 34: 1 2 3 5 7 11 13 17 19 23 29 31 37

39 18: 1 2 3 5 7 11 13 17 19 23 29 31 37

40 27: 1 2 3 5 7 11 13 17 19 23 29 31 37

41 35: 1 2 3 5 7 11 13 17 19 23 29 31 37 41

42 33: 1 2 3 5 7 11 13 17 19 23 29 31 37 41

43 32: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43

44 10: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43

45 12: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43

46 43: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43

47 40: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

48 21: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

49 22: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

50 15: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

[Azad Salam]

[quote="Toufique"]I am getting presentation error.But can't understand why.please help me out.
printf(" %d %d: ",n,c);
printf("%d ",i);
printf(" %d %d: ",n,c);
printf("%d ",i);


you are printing one extra space after the last prime number in each test case..
replace those lines with these...

printf(" %d %d:",n,c);
printf(" %d",i);
printf(" %d %d:",n,c);
printf(" %d",i);

I hope this will help...

[sazzadcsecu]

What's the wrong with this code? plz help me..........

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>

using namespace std;

//#define longlong long long
//#define longlong __int64
#define max 1002

bool prime[max];
//longlong pr[max];
long int np[max];

void sieve()
{
long int i,j;

for(i=2;i<max;i++)
{
prime=true;
}

for(i=2;i<max;i++)
{
if(prime)
for(j=i*2;j<max;j+=i)
prime[j]=false;
}
}

int Total(int n)
{
int i, total = 0,j=0;

np[j]=1;
j++;
total++;
for(i = 2; i<=n; i++)
{
if(prime)
{
np[j]=i;
total++;
j++;
}
}
return total;
}

int main()
{
//longlong j;
sieve();
long int n,c,i,j,s,t,x;
while(scanf("%d %d",&n,&c)!=EOF)
{
i=Total(n);

if(c*2>i)
{
printf("%ld %ld:",n,c);
for(j=0;j<i;j++)
printf(" %ld",np[j]);
}

else if(i%2==1)
{
j=(c*2)-1;
s=((i/2)-(j/2)+1);
t=((i/2)+(j/2)+1);
printf("%ld %ld:",n,c);

for(x=s;x<=t;x++)
{
printf(" %ld",np[x-1]);
}
}
else
{
j=c*2;
s=((i/2)-(j/2)+1);
t=((i/2)+(j/2));

printf("%ld %ld:",n,c);

for(x=s;x<=t;x++)
{
printf(" %ld",np[x-1]);
}
}
printf("\n\n");


}

return 0;
}

[shantanu18]

geting wa!!! why wa???

Code: Select all

#include <cstdio>
#include <iostream>
#define MAX 1001
#define sq 32
using namespace std;

int arr[MAX];
int v[MAX];
int prime[MAX];
void scive()
{
	arr[0]=1;
	for(int i=3;i<=sq;i+=2)
	{
		for(int j=2;i*j<MAX;j++)
			arr[i*j]=1;
	}
	v[0]=0;
	v[1]=1;
	v[2]=2;
	prime[0]=1;prime[1]=2;
	int Ind=3;
	for(int i=3,in=2;i<MAX;i+=2)
	{
		if(arr[i]!=1)
		{
			v[Ind]=v[Ind-1]+1;Ind++;
			v[Ind]=v[Ind-1];
			prime[in++]=i;
		}
		else
		{
			v[Ind]=v[Ind-1];
			Ind++;
			v[Ind]=v[Ind-1];
		}
		Ind++;
	}
}
int main()
{
	int n,c,mid;
	scive();
	while(scanf("%d%d",&n,&c)==2)
	{
		int start,end;
		if(v[n]%2==0)
		{
			mid=v[n]/2;
			start=v[n]/2-c+1;
			end=v[n]/2+c;
		}
		else
		{
			mid=(v[n]+1)/2;
			start=mid-(c-1);
			end=mid+c-1;
		}
		if(mid<c)start=1,end=v[n];
		printf("%d %d:",n,c);
		for(int i=start;i<=end;i++)
			cout<<" "<<prime[i-1];
		cout<<endl;
	}
	return 0;
}

[sazzadcsedu]

Have you noticed this --- >

Each line of output should be followed by a blank line.

Else then everything is ok . Just add a newline after each output.

[shantanu18]

still WA after change blank line. I tried also blank line after every case (cout<<endl<<endl) but both are WA! I am confused

Code: Select all

#include <cstdio>
#include <iostream>
#define MAX 1010
#define sq 32
using namespace std;

int arr[MAX];
int v[MAX];
int prime[MAX];
void scive()
{
	arr[0]=1;
	for(int i=3;i<=sq;i+=2)
	{
		for(int j=2;i*j<MAX;j++)
			arr[i*j]=1;
	}
	v[0]=0;
	v[1]=1;
	v[2]=2;
	prime[0]=1;prime[1]=2;
	int Ind=3;
	for(int i=3,in=2;i<MAX;i+=2)
	{
		if(arr[i]!=1)
		{
			v[Ind]=v[Ind-1]+1;Ind++;
			v[Ind]=v[Ind-1];
			prime[in++]=i;
		}
		else
		{
			v[Ind]=v[Ind-1];
			Ind++;
			v[Ind]=v[Ind-1];
		}
		Ind++;
	}
}
int main()
{
	int n,c,mid,ca=1;
	scive();
	while(scanf("%d%d",&n,&c)==2)
	{
		if(ca>1)cout<<endl; //blank line between testcase
		int start,end;
		if(v[n]%2==0)
		{
			mid=v[n]/2;
			start=v[n]/2-c+1;
			end=v[n]/2+c;
		}
		else
		{
			mid=(v[n]+1)/2;
			start=mid-(c-1);
			end=mid+c-1;
		}
		if(mid<(c-1))start=1,end=v[n];
		printf("%d %d:",n,c);
		for(int i=start;i<=end;i++)
			cout<<" "<<prime[i-1];
		cout<<endl;
                //cout<<endl; tried this also. but no luck
		ca++;
	}
	return 0;
}

[helloneo]

still WA after change blank line. I tried also blank line after every case (cout<<endl<<endl) but both are WA! I am confused

if(ca>1)cout<<endl; //blank line between testcase <----- remove this!!

and at the end of each case, try this..

cout<<endl;
cout<<endl;


Remove your code if you get AC

[shantanu18]

It was not only blank line problem also a logical problem. I got ac. Thanks everybody for helping me. (i can't edit my post so can not delete my code)