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

Post Reply
mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Tue Jan 17, 2006 10:22 pm

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
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi » Wed Jan 18, 2006 6:16 am

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

Tonima
Sanjana

Staryin
New poster
Posts: 12
Joined: Fri Dec 16, 2005 4:22 pm
Location: shanghai/china
Contact:

406 WHY WA!!HELP ME!!

Post by Staryin » Fri Feb 10, 2006 5:29 am

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
New poster
Posts: 2
Joined: Tue Mar 07, 2006 12:27 am

406 TLE

Post by plAnadecU » Tue Mar 07, 2006 12:34 am

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
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm

406 wa --- why

Post by yogeshgo05 » Fri Mar 10, 2006 4:57 pm

hi guys ... this is my code..

Code: Select all


deleted 
Last edited by yogeshgo05 on Wed Mar 15, 2006 2:10 pm, edited 1 time in total.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali » Fri Mar 10, 2006 11:17 pm

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
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm

Post by yogeshgo05 » Sat Mar 11, 2006 3:03 am

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sat Mar 11, 2006 5:03 am

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
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm

Post by yogeshgo05 » Mon Mar 13, 2006 6:15 pm

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
Last edited by yogeshgo05 on Wed Mar 15, 2006 2:11 pm, edited 1 time in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Tue Mar 14, 2006 11:00 am

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
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm

Post by yogeshgo05 » Tue Mar 14, 2006 7:03 pm

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

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

406 prime cuts! WA!

Post by smilitude » Sun Apr 09, 2006 5:08 am

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;
}
            
    
fahim
#include <smile.h>

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali » Sun Apr 09, 2006 11:56 pm

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

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali » Sun Apr 09, 2006 11:59 pm

i think only your search function return unfair number.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Tue Apr 11, 2006 4:27 am

I am so grateful to you articali !!
I got accepted! THANKS A LOTTTTTTTTT!!
fahim
#include <smile.h>

Post Reply

Return to “Volume 4 (400-499)”