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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 406 - Prime Cuts WA

Post by brianfry713 »

Each line of output should be followed by a blank line, including the last one.
Don't print a space at the end of a line.
Check input and AC output for thousands of problems on uDebug!
akash_roy
New poster
Posts: 1
Joined: Fri Sep 13, 2013 12:47 am

Re: 406 - Prime Cuts Time Limit exceeded

Post by akash_roy »

please anyone help me everytime got time limit
#include<stdio.h>
int main()
{
int i,n,m,p,q,j,r,a[10000],b,c,k,o;
a[1]=1;
while(scanf("%d %d",&n,&m)==2)
{
k=2;
for(j=1; j<=n; j++)
{
r=j;
p=0;
q=r-2;
for(i=2; i<=r; i++)
{
if(r%i!=0)
p++;
}
if(p==q)
a[k++]=j;
}
k=k-1;
if(k%2==0)
o=m*2;
else
o=m*2-1;
if(o>=k)
{
printf("%d %d:",n,m);
for(j=1; j<=k; j++)
printf(" %d",a[j]);
}
else
{
b=k-o;
c=b/2;
printf("%d %d:",n,m);
for(j=c+1; j<=k-c; j++)
printf(" %d",a[j]);
}
printf("\n\n");
}
return 0;
}
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 406 - Prime Cuts Time Limit exceeded

Post by brianfry713 »

Use the sieve to precompute primes.
Check input and AC output for thousands of problems on uDebug!
nildorpon
New poster
Posts: 4
Joined: Sun Jul 21, 2013 4:13 pm

Re: 406 - Prime Cuts Time Limit exceeded

Post by nildorpon »

Why Wrong Answer????
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
boolean [] primes= primeList(1000);
while(scanner.hasNext()){
int n = scanner.nextInt();
int c = scanner.nextInt();
if((n >= 1) && (n <= 1000)) {
if((c>=1) && (c<=n) ){
System.out.println();
int counter = 0;
for(int i = 1; i<= n ;i++){
if (primes){
counter++;
}
}
int [] primeArray = new int[counter];
int tempCounter = 0;
for(int i = 1; i<= n ;i++){
if (primes){
primeArray[tempCounter] = i;
tempCounter++;
}
}
int printTerms = 0;
int startingPoint = 0;
System.out.print(n+" "+ c+":");
if(counter%2 == 0){
printTerms = (c*2);
if (printTerms> counter){
for(int i = 0; i< primeArray.length;i++){
System.out.print(" "+primeArray);
}
}else{
startingPoint = (counter - printTerms) /2;
for(int i = startingPoint; i<(startingPoint+printTerms);i++){
System.out.print(" "+primeArray);
}
}
}else{
printTerms = ((c*2)-1);
if(printTerms> counter){
for(int i = 0; i< primeArray.length;i++){
System.out.print(" "+primeArray);
}
}else{
startingPoint = (counter - printTerms) /2;
for(int i = startingPoint; i<(startingPoint+printTerms);i++){
System.out.print(" "+primeArray);
}
}
}
System.out.println();
}
}
}
}

private static boolean isPrime(long n) {
for (long i = 2; i <= (long)Math.sqrt((double)n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

private static boolean[] primeList(int n){
boolean [] primeList = new boolean[n+1];
for(int i = 1; i< primeList.length; i++){
primeList = false;
}
for(int i = 1; i<primeList.length;i++){
if(isPrime(i)){
primeList = true;
}
}
return primeList;
}
}
nildorpon
New poster
Posts: 4
Joined: Sun Jul 21, 2013 4:13 pm

Re: 406 - Prime Cuts WA

Post by nildorpon »

Why Wrong Answer???

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
boolean [] primes= primeList(1000);
while(scanner.hasNext()){
int n = scanner.nextInt();
int c = scanner.nextInt();
if((n >= 1) && (n <= 1000)) {
if((c>=1) && (c<=n) ){
System.out.println();
int counter = 0;
for(int i = 1; i<= n ;i++){
if (primes){
counter++;
}
}
int [] primeArray = new int[counter];
int tempCounter = 0;
for(int i = 1; i<= n ;i++){
if (primes){
primeArray[tempCounter] = i;
tempCounter++;
}
}
int printTerms = 0;
int startingPoint = 0;
System.out.print(n+" "+ c+":");
if(counter%2 == 0){
printTerms = (c*2);
if (printTerms> counter){
for(int i = 0; i< primeArray.length;i++){
System.out.print(" "+primeArray);
}
}else{
startingPoint = (counter - printTerms) /2;
for(int i = startingPoint; i<(startingPoint+printTerms);i++){
System.out.print(" "+primeArray);
}
}
}else{
printTerms = ((c*2)-1);
if(printTerms> counter){
for(int i = 0; i< primeArray.length;i++){
System.out.print(" "+primeArray);
}
}else{
startingPoint = (counter - printTerms) /2;
for(int i = startingPoint; i<(startingPoint+printTerms);i++){
System.out.print(" "+primeArray);
}
}
}
System.out.println();
}
}
}
}

private static boolean isPrime(long n) {
for (long i = 2; i <= (long)Math.sqrt((double)n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}

private static boolean[] primeList(int n){
boolean [] primeList = new boolean[n+1];
for(int i = 1; i< primeList.length; i++){
primeList = false;
}
for(int i = 1; i<primeList.length;i++){
if(isPrime(i)){
primeList = true;
}
}
return primeList;
}
}
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 406 - Prime Cuts WA

Post by brianfry713 »

Don't double post
Check input and AC output for thousands of problems on uDebug!
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 406 - Prime Cuts Time Limit exceeded

Post by brianfry713 »

Be careful, there is a case where C > N in the judge's input.
Input:

Code: Select all

18 20
AC output:

Code: Select all

18 20: 1 2 3 5 7 11 13 17

Check input and AC output for thousands of problems on uDebug!
B_sayem
New poster
Posts: 7
Joined: Wed Dec 11, 2013 7:57 pm

Re: 406 - Prime Cuts Time Limit exceeded

Post by B_sayem »

Can any one Help me why time limit exceeds

Code: Select all

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int n,c;
    while(cin>>n>>c)
    {
        int a[n],i=0,count=0;
        cout<<n<<" "<<c<<":";
        for(int j=1; j<=n; j++)
        {
            int check=0;
            for(int k=2; k<j; k++)
            {
                if(j%k==0)
                {
                    check=1;

                }
            }
            if(check==0)
            {
                a[i]=j;
                i++;
                count++;
            }
        }

        if(count%2==0)
        {
            c=c*2;
        }
        else
        {
            c=c*2-1;
        }
        if(c>count)
        {
            for(int i=0; i<count; i++)
            {
                cout<<" "<<a[i];
            }
            cout<<endl;

        }
        else
        {
            int t;
            t=(count-c)/2;
            for(int i=t;i<count-t;i++)
            {
                cout<<" "<<a[i];
            }
            cout<<endl;

        }

    }

    return 0;
}
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 406 - Prime Cuts Time Limit exceeded

Post by brianfry713 »

brianfry713 wrote:Use the sieve to precompute primes.
Check input and AC output for thousands of problems on uDebug!
tanim_ahsan
New poster
Posts: 1
Joined: Wed Feb 19, 2014 2:57 pm

I get WA again & again pls help... 406-prime cuts

Post by tanim_ahsan »

Code: Select all

thnx brianfry 
got accepted... :D 
Last edited by tanim_ahsan on Thu Feb 20, 2014 9:50 am, edited 1 time in total.
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: I get WA again & again pls help... 406-prime cuts

Post by brianfry713 »

997 1: 433
Check input and AC output for thousands of problems on uDebug!
MNT.95
New poster
Posts: 7
Joined: Thu Jan 23, 2014 5:40 pm

Re: 406 - Prime Cuts WA

Post by MNT.95 »

why I'm getting wrong answer?

Code: Select all

#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;

bool prime[1005];
vector<int>primeNum(170);

int sizePrimeNum;

void seive()
{
	memset(prime, true ,sizeof prime);
	prime[0] = 0;
	

	for(int i=2; i*i<1005;i++)
		if(prime[i])
			for(int j=i; i*j < 1005; j++)
				prime[i*j] = 0;

	sizePrimeNum =0;
	for(int i=1;i<1005;i++)
		if(prime[i])
			primeNum[sizePrimeNum++] = i;
	primeNum[sizePrimeNum] = 1013;

}

int main()
{
	int n;
	int c;

	seive();

	while(scanf("%d%d",&n,&c)!=EOF)
	{
		int cntr = 0;
		for(int i=0;primeNum[i]<=n;i++)
			cntr++;

		int startIndex;
		bool flag = false;

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

		if(cntr%2==0)
		{
			if(cntr<=c*2) flag = true;
			else
			{
				startIndex = (cntr/2 - (c*2)/2);
 
				for(int i=startIndex,j=1;j<=(c*2);j++)
					printf("%d ",primeNum[i++]);
				printf("\n");
			}
		}
		else
		{
			if(cntr<=((c*2)-1)) flag = true;
			else
			{
				int middle = cntr/2;
				startIndex = (middle - ((c*2)-1)/2);
 
				for(int i=startIndex,j=1;j<=(c*2)-1;j++)
					printf("%d ",primeNum[i++]);
				printf("\n");
			}
		}
		if(flag)
			for(int i=0;primeNum[i]<=n;i++)
					printf("%d ",primeNum[i]);
		printf("\n");
	}
	return 0;
}
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 406 - Prime Cuts WA

Post by brianfry713 »

Each line of output should be followed by a blank line
Check input and AC output for thousands of problems on uDebug!
MNT.95
New poster
Posts: 7
Joined: Thu Jan 23, 2014 5:40 pm

Re: 406 - Prime Cuts WA

Post by MNT.95 »

thanks.. that was helpful :)
Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 406 - Prime Cuts

Post by Shahidul.CSE »

thanks, lighted!! :D :D

Code: Select all

Accepted!
Last edited by Shahidul.CSE on Wed Sep 03, 2014 6:49 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Post Reply

Return to “Volume 4 (400-499)”