## 406 - Prime Cuts

Moderator: Board moderators

Arm.Turbo
New poster
Posts: 21
Joined: Wed Aug 11, 2004 1:20 pm
At last AC. Thx to all =)

Rony
New poster
Posts: 16
Joined: Wed Jun 30, 2004 6:46 am
Location: Dhaka
Contact:

### p-406

Hi,
Anyone can give me algorithm to find the middle and print the list .

Hi,
A1, I think you have'nt understand my question . For prime cuts problem I want to know the algo to find out the mid point and print the result because i have tried so many times but failed . There is a condition if list is
even then print C*2 number of prime numbers else (C*2)-1 from the middle . The given algo (By you ) will not solve this problem.
Please help me . Thanks
Rony
Last edited by Rony on Sun Sep 26, 2004 10:43 am, edited 1 time in total.

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

then :

Code: Select all

``````int lenthofarray; //some how  you know it

float halfofarray;
int halfofarrayint;

halfofarray=lenthofarray/2.0;
halfofarrayint= halfofarray; //one kind of type casting

if(halfofarrayint == halfofarray) // then two middle
print -- array[halfofarrayint] and array[halfofarrayint+1];

else
print --array[halfofarrayint];``````
if you talk about prime cut then you have to do little more Rony
New poster
Posts: 16
Joined: Wed Jun 30, 2004 6:46 am
Location: Dhaka
Contact:
A1 wrote:your question is not clear!

then :

Code: Select all

``````int lenthofarray; //some how  you know it

float halfofarray;
int halfofarrayint;

halfofarray=lenthofarray/2.0;
halfofarrayint= halfofarray; //one kind of type casting

if(halfofarrayint == halfofarray) // then two middle
print -- array[halfofarrayint] and array[halfofarrayint+1];

else
print --array[halfofarrayint];``````
if you talk about prime cut then you have to do little more Hi,
A1, I think you have'nt understand my question . For prime cuts problem I want to know the algo to find out the mid point and print the result because i have tried so many times but failed . There is a condition if list is
even then print C*2 number of prime numbers else (C*2)-1 from the middle . The given algo (By you ) will not solve this problem.

Thanks
Rony

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Ok Now I undersetand Code: Select all

``````intger leanthofarray;

input: C;

if C*2>=leanthofarray
print every element of array.
else
{
if(leanthofarry is even)
{
start=(leanthofarry-(C*2))/2;
For i=(0+start) To i<(leanthofarray-start)
print array[i];
}
else
{
start=(leanthofarray-((C*2)-1))/2;
For i=(0+start) To i<(leanthofarray-start)
print array[i];
}
}``````
I think it will work Rony
New poster
Posts: 16
Joined: Wed Jun 30, 2004 6:46 am
Location: Dhaka
Contact:
Hi,
Thanks a lot . I have got Acc with PE at last. You have done a lot for
me. Your algorithm is so easy which is very good . Carry on.
Who are u? Post some things about you and your UVA ID thats why
I can see your score. Again many many Thanks.

Regards
Rony Ashkankhan
New poster
Posts: 12
Joined: Wed Oct 13, 2004 10:14 am
Location: Teh
Contact:

### Is there any bodu here??????????

I delete it:D
Last edited by Ashkankhan on Mon Nov 01, 2004 9:50 am, edited 1 time in total.

Ashkankhan
New poster
Posts: 12
Joined: Wed Oct 13, 2004 10:14 am
Location: Teh
Contact:

### Gods of algo helppppppppp

help me WA [cpp]
#include <stdio.h>

int main()
{
int a[]={1,2,3,5,7,11,13,17,19,23,29,31,37,
41,43,47,53,59,61,67,71,73,79,83,89,97,
101,103,107,109,113,127,131,137,139,149,
151,157,163,167,173,179,181,191,193,197,
199,211,223,227,229,233,239,241,251,257,
263,269,271,277,281,283,293,307,311,313,
317,331,337,347,349,353,359,367,373,379,
383,389,397,401,409,419,421,431,433,439,
443,449,457,461,463,467,479,487,491,499,503,509,521,523,
541,547,557,563,569,571,577,587,593,599,601,607,613,617,
619,631,641,643,647,653,659,661,673,677,683,691,701,709,
719,727,733,739,743,751,757,761,769,773,787,797,809,811,
821,823,827,829,839,853,857,859,863,877,881,883,887,907,
911,919,929,937,941,947,953,967,971,977,983,991,997};
//printf("%d",a);
int n,c,i=0,t;
while(scanf("%d %d",&n,&c) != EOF)
{
if(c!=0)
{
// if(n<=1000 && n>=1 && c<=n && c>=1 )
// {
i=0;
while(a<=n)
{
i++;
}
//printf("%d\n",i);
printf("%d %d:",n,c);
if(i%2==0)
{
t=(i-2*c)/2;
if(2*c-1>i)
{
for(int j=0;j<i;j++)
printf(" %d",a[j]);
}
else
for(int y=t;y<=t+(2*c-1);y++)
{
printf(" %d",a[y]);
}
}
else
{
t=(i-2*c-1)/2;
if(2*c>i)
{
for(int p=0;p<i;p++)
printf(" %d",a[p]);
}
else
for(int e=t+1;e<=t+(2*c-1);e++)
{
printf(" %d",a[e]);
}
}
printf("\n\n");
}
// }
}
return 0;
}

[/cpp]

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
... and which problem is this?

Ashkankhan
New poster
Posts: 12
Joined: Wed Oct 13, 2004 10:14 am
Location: Teh
Contact:
dear sohel
406:D

Sokar
New poster
Posts: 1
Joined: Tue Sep 07, 2004 9:45 pm
Ashkankhan wrote:help me WA One problem I see with your solutions is it will not work for input that is larger than 997. Almost certainly the range of input will be more than 997?

Piers Kennedy
New poster
Posts: 3
Joined: Thu Apr 22, 2004 8:12 pm

### 406 input causing WA

Dear Ashkankhan,

My approach was very similar to yours. My code passed all the tests in the 406 threads but I still got WA. Sokar's suggestion is not why you are still getting WA (there is no input above 1000). For some reason for this problem you need to read all the input (and store) then print the output. As soon as I tried this I got AC.

Hope this helps.

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Very Small Problem [c]i=0;
while(a<=n)
{
i++;
}
//printf("%d\n",i);
[/c]
Change it like this :
[c]i=0;
while(a<=n && a>0) //don't know why!!!!!!!
{
i++;
}
//printf("%d\n",i);
[/c]
you will get a nice AC  Ashkankhan
New poster
Posts: 12
Joined: Wed Oct 13, 2004 10:14 am
Location: Teh
Contact:
very very tnx A1.But I dint know why frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

### 406 TLE?? Need Help!!!

[cpp]
I think it's a simple question,but it's TLE,Why?
Here is my code.
#include <iostream.h>

bool p;
int prime;

void Eratosthenes()
{
int i,j;
p = p = 0;
for (i=2; i<=1000000; i++) p=true;
for (i=2; i<=1000;)
{
for (j=i+i; j<=1000000; j+=i) p[j]=false;
for (i++; !p; i++);
}
}

void get_prime_table()
{
Eratosthenes();
prime=1;
int i,j;
for (i=2,j=1;i<=1010;i++)
if (p==true) prime[j++]=i;
}

void solve(int n,int c)
{
get_prime_table();
int length,times;
int i;
for (i=0;prime<=n;i++);
length=i;
if (length%2==0) times=c*2;
else times=c*2-1;
if (times>length)
{
for (i=0;i<length-1;i++)
cout<<prime<<' ';
cout<<prime[length-1]<<endl;
}
else
{
if (length%2!=0)
{
for (i=(length-times+1)/2;i<(length+times-1)/2;i++)
cout<<prime<<' ';
cout<<prime[(length+times-1)/2]<<endl;
}
if (length%2==0)
{
for (i=(length-times)/2;i<(length+times-2)/2;i++)
cout<<prime<<' ';
cout<<prime[(length+times-2)/2]<<endl;
}
}
}

int main()
{
int N,C;
while (cin>>N>>C)
{
cout<<N<<' '<<C<<": ";
solve(N,C);
cout<<endl;
}
return 0;
}[/cpp]