406 - Prime Cuts

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Arm.Turbo
New poster
Posts: 21
Joined: Wed Aug 11, 2004 1:20 pm

Post by Arm.Turbo » Tue Sep 14, 2004 7:52 am

At last AC. Thx to all =)

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

p-406

Post by Rony » Sat Sep 25, 2004 9:17 am

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



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 . :oops:

Thanks
Rony
Last edited by Rony on Sun Sep 26, 2004 10:43 am, edited 1 time in total.

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Sat Sep 25, 2004 10:14 am

your question is not clear!
if you ask about middle of an array

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:

Post by Rony » Sun Sep 26, 2004 10:48 am

A1 wrote:your question is not clear!
if you ask about middle of an array

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.
Please help me .

Thanks
Rony

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Sun Sep 26, 2004 5:06 pm

Ok Now I undersetand :wink:

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:

Post by Rony » Tue Sep 28, 2004 6:28 am

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 8)

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

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

Post by Ashkankhan » Wed Oct 13, 2004 10:26 am

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

Post by Ashkankhan » Wed Oct 13, 2004 10:30 am

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[84]);
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]

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Oct 13, 2004 10:44 am

... and which problem is this?

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

Post by Ashkankhan » Wed Oct 13, 2004 4:34 pm

dear sohel
406:D

User avatar
Sokar
New poster
Posts: 1
Joined: Tue Sep 07, 2004 9:45 pm

Post by Sokar » Fri Oct 15, 2004 4:29 am

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

Post by Piers Kennedy » Mon Oct 18, 2004 7:26 pm

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.

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Sun Oct 31, 2004 10:51 am

Very Small Problem :D
your code
[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 :lol: :-?

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

Post by Ashkankhan » Mon Nov 01, 2004 9:48 am

very very tnx A1.But I dint know why :roll:

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

406 TLE?? Need Help!!!

Post by frankhuhu » Sat Dec 04, 2004 4:45 pm

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

bool p[1000010];
int prime[1010];

void Eratosthenes()
{
int i,j;
p[0] = p[1] = 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[0]=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]

Post Reply

Return to “Volume 4 (400-499)”