406 - Prime Cuts

[mamun]

If the size of the center list exceeds the limits of the list of prime numbers between 1 and N, the list of prime numbers between 1 and N (inclusive) should be printed.

So now you got it?

[kolpobilashi]

thanx a lot, i was sooooo stupid!!! well i did the job well and now my ststus got a bit higher!!! i got PE!! but at this moment i don care abt this PE, just when i know i did SOLVE the problem that's enough 4 STUPID like me!!! thanks again.....

Tonima

[Staryin]

code:

Code: Select all

#include<iostream.h>
const int MAX=1000;
int list[1001];
int nlist[200];
int n,num;
int i,j,k;
int count;
int len;
void initial()                //Eratosthenes
{
	list[0]=1;
	for(i=1;i<=1000;i++)         
		list[i]=i;
	
	list[1]=0;
	i=2;
	
	while(i<1000)
	{
		k=2*i;
		while(k<=1000)        // FIRST:DELETE 2N+2,N=0 1 2 ... 1000
		{
			list[k]=0;
			k=k+i;
					
		}
		i=i+1;
		while(list[i]==0&&i<1000)
			i=i+1;
		
	}
	


j=1;	
for(i=0;i<=1000;i++)
		if(list[i]!=0)
			{
				nlist[j]=list[i];
				j=j+1;
			}
			
len=j;
//for(i=1;i<len;i++)
//	cout<<nlist[i]<<endl;			
			
//cout<<len<<endl;				
			
			
}


void solve()
{
	count=0;
	int pnum,pos;
	for(i=1;nlist[i]<=n&&count<168;i++) //168 is the number of prime number in the 1000
		count++;

	if(count/2<=num)
		{
			pnum=count;	
			pos=1;
		}
		
	if(count/2>num)
	{	
		if(count%2==0)
			{
				pnum=num*2;
				pos=count/2+1-num;
			}
		
		
		else 
			{
				pnum=num*2-1;	
				pos=count/2+1-(num-1);
			
			}
	}
	
	cout<<count<<" "<<pos<<" "<<pnum<<endl;
	
	cout<<n<<" "<<num<<": "; 	
	
	for(i=pos;pnum>1;i++,pnum--)
		cout<<nlist[i]<<" ";
		cout<<nlist[i]<<endl;
	cout<<endl;
	
}
void read()
{
	
	
	while(cin>>n>>num)
	{
		solve();	
		
	}
	
	
}
int main()
{
	
	initial();
	read();
	return 0;	
	
	
}

[plAnadecU]

Here I paste my code

Code: Select all

#include <iostream>
#include <vector>
using namespace std;

int main(){
	int N,C;
	while(cin >> N >> C){
		vector<char> T=vector<char>(N+1,3);
		// 1 -> primer
		// 2 -> no primer
		// 3 -> no calculat
		T[1]=1;
		T[2]=1;
		for(int i=3;i<=N;i++){
			bool primer = true;
			for(int j=2;j<i;j++){
				if(T[j]==1){
					if(i%j==0) primer=false;
				}
			}
			T[i]=(primer)?1:2;
		}
		int count=0;
		for(int i=1;i<=N;i++){
			if (T[i]==1){
				count++;
			}
		}	
		cout << N << " " << C << ":";
		int inici, fi, quans;
		if(count%2==0){
			quans=C*2;
			inici = count/2 - (quans/2);
			fi = count/2 + (quans/2)-1;
		}else{
			quans=C*2-1;
			inici = count/2  - (quans/2);
			fi = count/2 + (quans/2);
		}
		quans=0;
		for(int i=1;i<=N;i++){
			if (T[i]==1){
				if(quans>=inici && quans <=fi)
					cout << " " << i;
				
				quans++;
			}
		}
		cout << endl << endl;
	}
}

I think my code works fine. There is some problem with reading the input that makes it wait for new data. Anybody can help me please!!!

[yogeshgo05]

hi guys ... this is my code..

Code: Select all

deleted 

[Artikali]

tests:

Code: Select all

2 2
3 3

your output

Code: Select all

2 2: -858993460 1 2 -858993460 

3 3: -858993460 1 2 3 -858993460 

[yogeshgo05]

hi artikali..

i have made changes to my program ....

i.e

Code: Select all

if(r>count) to (r>=count)... but its still a wa i dont no why plz help...

people are not rewarded for participating but for winning....aliter

[chunyi81]

Check this thread:

http://online-judge.uva.es/board/viewto ... hlight=406

I posted some test data there. For the test data there, the correct output shown there has the blank lines missing. There should be a blank line after each line of output. Your code fails for some of the test data there.

For example:

Input:
99 25

Your code prints:
99 25: 2359184 4199819 4416752 4199302 2359184 4199352 0 1555528507 0 0 25 99 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

Check the problem description again:

If the size of the center list exceeds the limits of the list of prime numbers between 1 and N, the list of prime numbers between 1 and N (inclusive) should be printed.

[yogeshgo05]

hi ...
plZ help i m tired getting wa it seems to be working for all the possible o/p
i just dont no whether formating has something to do with.....

Code: Select all

deleted

[chunyi81]

It seems that you might have misunderstood the problem. Read the problem description again:

Your program will read in a number N; determine the list of prime numbers between 1 and N; and print the C*2 prime numbers from the center of the list if there are an even number of prime numbers or (C*2)-1 prime numbers from the center of the list if there are an odd number of prime numbers in the list.

You are checking r >= count where r is the C you read into your program.
The problem says if number of prime numbers between 1 and N (inclusive) is even, print C*2, and not C, which is what you are doing in your code. Similarly when the number of prime numbers between 1 and N(inclusive) is odd.

Delete away the check if s == 99 && r == 25.

Change r >= count to: ((r % 2 == 0) && (r*2 >= count)) || ((r % 2 == 1) && (r*2 - 1 >= count))

[yogeshgo05]

hi chunyi81...

thanks man for help i got it AC... ur realy great helper....u don't mind..
if i ask u why take pain of debugging other's codes ... plz ignore if i hav
asked something wrong... thanks any way...

yogesh......

[smilitude]

what is my fault here??
can you give me sample i\o, that dont works for my code??
i will be greatly helped!

Code: Select all

/*
 * 406 prime cuts
 * submission WA WA WA RF WA WA
 * coded at 24th march,2006 at 2:32pm
 *
 */

#include <stdio.h>

int primes[170];
int k=0;

int isprime(int n) {
    if(n<2) return 0;
    if(n==2) return 1;
    if(n%2==0) return 0;
    
    for(int i=3;i*i<=n;i+=2) {
        if(n%i==0) return 0;
    }
    return 1;
}

void build(){
    int i;
    
    primes[0]=1;
    primes[++k]=2;
    for(i=3;i<=1000;i+=2) {
        if(isprime(i)) {
            primes[++k]=i;
        }
    }
}

int search(int n) {
    int i;
    for(i=0;i<170;i++) {
        if(primes[i]>n) break;
    }
return i;
}
    
void print(int a,int b) {
    int i;
    for(i=a;i<=b;i++) {
        if(primes[i]) printf(" %d",primes[i]);
    }
    printf("\n\n");
}    
    
int main() {
    int num;
    int c;
    int limit;
    int start;
    int end;
    build();
    /*
    freopen("f:\\input.in","r",stdin);
    freopen("f:\\output.out","w",stdout);*/
    //printf("k--> %d\n",k);
    //scanf("%d",&k);
    while(scanf("%d %d",&num, &c)==2) {
        limit=search(num);
        //printf("limit --> %d\n",limit);
        //printf("primes 0 --> %d\n",primes[0]);
        if(limit%2==0) {
            start=limit/2-c;
            end=start+2*c-1;
        }else {
            start=limit/2-c+1;
            end=start+2*c-2;
        }
	    if(end>limit||start<0) {
            printf("%d %d:",num,c);
            print(0,limit-1);
        }else {
            printf("%d %d:",num,c);
            print(start,end);
        }
    }
return 0;
}
            
    

[Artikali]

intput
997 1
your output
997 1: 433 439
my output
997 1: 433

[Artikali]

i think only your search function return unfair number.

[smilitude]

I am so grateful to you articali !!
I got accepted! THANKS A LOTTTTTTTTT!!