406 - Prime Cuts
Moderator: Board moderators
-
- New poster
- Posts: 8
- Joined: Tue Jul 23, 2002 9:15 am
INPUT NEEDED FOR 406
Hi,
I have solve the problem and it is valid for the given inputs. Can anyone give me some inputs with outputs.
Bye
I have solve the problem and it is valid for the given inputs. Can anyone give me some inputs with outputs.
Bye
HEY WANT TO GET SOL.TRY ON http://www.uvexam.zzn.com from 1st September
WA!! problem 406 Prime Cuts
Code: Select all
#include<iostream.h>
#include<math.h>
#include<vector>
using namespace std;
short N,C,i,j,count,midindex,temp;
void main(void)
{
vector <short> primelist;
primelist.push_back(1);
primelist.push_back(2);
primelist.push_back(3);
for (i=4;i<1001;i++) /* make a list of prime number at range 1 to 200 (include 1) */
{
for (j=2;j<=sqrt(i);j++)
{
if (i % j == 0)
break;
}
temp = sqrt(i) + 1;
if (j == temp)
primelist.push_back(i);
}
while(cin>>N>>C)
{
cout<<N<<" "<<C<<":";
count = 0;
for (i=0;primelist[i]<=N;i++) /* calculate the list length of prime number */
count++;
if (count % 2 == 0) /* if list length is even */
{
midindex = count / 2; /* set the middle index of the list */
count = C * 2;
if (midindex-count/2 < 0)
i = 0;
else
i = midindex-count/2;
for (i=i;i<midindex+count/2;i++)
{
if ((i == primelist.size())||(primelist[i] > N))
break;
cout<<" "<<primelist[i];
}
}
else /* if list length is odd */
{
midindex = count / 2; /* set the middle index of the list */
count = C * 2 - 1;
if (midindex-(count-1)/2 < 0)
i = 0;
else
i = midindex-(count-1)/2;
for (i=i;i<=midindex+(count-1)/2;i++)
{
if ((i == primelist.size())||(primelist[i] > N))
break;
cout<<" "<<primelist[i];
}
}
cout<<endl<<endl;
}
}
Please Help me..Thanks!!
Input:
- 1 1
4 4
1000 1
1233 43
234 23
434 944
- 1 1: 1
4 4: 1 2 3
1000 1: 433
1233 43: 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
234 23: 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 1
57 163 167 173 179 181 191 193 197 199 211 223
434 944: 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 14
9 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 31
3 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433
-
- Learning poster
- Posts: 68
- Joined: Fri Oct 26, 2001 2:00 am
- Location: Dhaka, Bangladesh
- Contact:
problem 406
hey, i get WA on problem 406, but i think its all ok in my code and the sample input also give correct output. here is my code. plz help me. thanx .
[cpp]
/*@BEGIN_OF_SOURCE_CODE*/
#include<stdio.h>
#include<string.h>
#include<math.h>
void main()
{
int a, b[1500], c, x, z, y, i, j, k, start = 0;
while((scanf("%d %d", &x, &c)) == 2)
{
if(start)
printf("\n");
memset(b, 0, sizeof(b));
start = 1;
i = 0;
for(y = 1; y <= x; y++)
{
z = 1;
for(a = 2;a <= sqrt(y);a++)
if(!(y%a))
z = 0;
if(z)
{
b = y;
i++;
}
}
printf("%d %d:", x, c);
if( c >= i)
for(a = 0; a < i; a++)
printf(" %d", b[a]);
else
{
if(!(i%2))
{
j = i/2 - 1;
k = i/2;
j -= c-1;
k += c-1;
for(a = j; a <= k; a++)
printf(" %d", b[a]);
}
else
{
j = (i-1)/2;
i = j - (c-1);
k = j + (c-1);
for(a = i; a <= k; a++)
printf(" %d", b[a]);
}
}
printf("\n");
}
}
/*@END_OF_SOURCE_CODE*/
[/cpp]
[cpp]
/*@BEGIN_OF_SOURCE_CODE*/
#include<stdio.h>
#include<string.h>
#include<math.h>
void main()
{
int a, b[1500], c, x, z, y, i, j, k, start = 0;
while((scanf("%d %d", &x, &c)) == 2)
{
if(start)
printf("\n");
memset(b, 0, sizeof(b));
start = 1;
i = 0;
for(y = 1; y <= x; y++)
{
z = 1;
for(a = 2;a <= sqrt(y);a++)
if(!(y%a))
z = 0;
if(z)
{
b = y;
i++;
}
}
printf("%d %d:", x, c);
if( c >= i)
for(a = 0; a < i; a++)
printf(" %d", b[a]);
else
{
if(!(i%2))
{
j = i/2 - 1;
k = i/2;
j -= c-1;
k += c-1;
for(a = j; a <= k; a++)
printf(" %d", b[a]);
}
else
{
j = (i-1)/2;
i = j - (c-1);
k = j + (c-1);
for(a = i; a <= k; a++)
printf(" %d", b[a]);
}
}
printf("\n");
}
}
/*@END_OF_SOURCE_CODE*/
[/cpp]
406 - Prime Cuts
The problem description has a small error. Under the input description for the value of C it is stated that 1<=C<=N. That is not true for all the sample input used to judge correctness. An assert to that effect will generate a SIGABRT indicating the assertion failed
Tatsu
Tatsu
406 - Wrong Answer
What's wrong?
Please help.
[cpp]
#include <stdio.h>
int main()
{
int tab[1001], c, n, n2, count, count2, c1, c2;
while(scanf("%d %d", &n, &c) == 2)
{
count = 0;
for(int tmp = 1; tmp <= n; tmp += 2) tab[tmp] = 1;
tab[2] = 1;
for(int tmp = 2; tmp <= n; tmp++)
for(int tmp2 = tmp*2; tmp2 <= n; tmp2 += tmp)
tab[tmp2] = 0;
for(int tmp = 1; tmp <= n; tmp++)
if(tab[tmp] == 1) count++;
count2 = count;
if(count%2 == 0) { c1 = count/2-c+1; c2 = count/2+c; }
else { c1 = count/2+1-c+1; c2 = count/2+1+c-1; }
int ct = 0;
for(int tmp = 1; tmp <= n; tmp++)
if(tab[tmp] == 1)
{
if(ct < c1) ct++;
if(ct >= c1 && ct <= c2) { printf("%d ", tmp); ct++; }
}
printf("\n\n");
}
return 0;
} [/cpp]
Please help.
[cpp]
#include <stdio.h>
int main()
{
int tab[1001], c, n, n2, count, count2, c1, c2;
while(scanf("%d %d", &n, &c) == 2)
{
count = 0;
for(int tmp = 1; tmp <= n; tmp += 2) tab[tmp] = 1;
tab[2] = 1;
for(int tmp = 2; tmp <= n; tmp++)
for(int tmp2 = tmp*2; tmp2 <= n; tmp2 += tmp)
tab[tmp2] = 0;
for(int tmp = 1; tmp <= n; tmp++)
if(tab[tmp] == 1) count++;
count2 = count;
if(count%2 == 0) { c1 = count/2-c+1; c2 = count/2+c; }
else { c1 = count/2+1-c+1; c2 = count/2+1+c-1; }
int ct = 0;
for(int tmp = 1; tmp <= n; tmp++)
if(tab[tmp] == 1)
{
if(ct < c1) ct++;
if(ct >= c1 && ct <= c2) { printf("%d ", tmp); ct++; }
}
printf("\n\n");
}
return 0;
} [/cpp]
hello, globi....
for this problem the I/O format like this:
you must print your input again in your output.
for this problem the I/O format like this:
Code: Select all
a b
a b: result
406 -WA - What is happening? PLEEEEAAAASSSSEEEEE!!!!
Can anyone give me some inputs with outputs? The suggestions on this site are ok for my algorithm but, judge give me WA!!! Why?
[c]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int eh_primo(int num)
{
int qd=2,i;
double raiz;
raiz = sqrt(num);
for (i=2;i<=raiz;i++)
{
if ((num%i) == 0)
return(0);
}
return(1);
}
void main(void)
{
int n=0, i=0, j=0, cont=0, c=0, pos1=0, pos2=0, print=0;
int A[1000], centro=0, ini=0, fim=0;
while ((scanf("%d %d",&n, &c)) == 2)
{
cont = 0;
centro = 0;
ini = 0;
fim = 0;
print = 0;
for (i=1;i<=n;i++)
{
if (eh_primo(i))
{
A[cont] = i;
cont++;
}
}
printf("%d %d: ",n,c);
if (c == 1)
{
print = cont/2;
printf("%d",A[print]);
}
else if ((cont%2)==0)
{
centro = (cont/2);
ini = centro - c;
fim = centro + c -1;
if (ini < 0){ini = 0; fim = cont-1;}
for (print=ini; print<=fim; print++)
printf("%d ", A[print]);
}
else
{
centro = cont/2;
ini = centro - c + 1;
fim = centro + c - 1;
if (ini < 0){ini = 0; fim = cont-1;}
for (print=ini; print<=fim; print++)
printf("%d ", A[print]);
}
printf("\n");
}
}
try to pre calculate the prime numbers . than check the boundary and print the proper primes . this is what i did and got ac. To generate the prime u can use sieve or any other suitable algorithm . This will be much easier and faster than calculating while taking input .
for sample input :
output:
hope u ll get ac
Best regards
Riyad
for sample input :
Code: Select all
21 2
18 2
523 40
18 18
100 7
1000 25
1000 12
523 40
12 10
21 3
99 25
100 100
723 12
Code: Select all
21 2 : 5 7 11
18 2 : 3 5 7 11
523 40 : 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
18 18 : 1 2 3 5 7 11 13 17
100 7 : 13 17 19 23 29 31 37 41 43 47 53 59 61 67
1000 25 : 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
1000 12 : 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
523 40 : 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
12 10 : 1 2 3 5 7 11
21 3 : 3 5 7 11 13
99 25 : 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
100 100 : 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
723 12 : 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379
hope u ll get ac
Best regards
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
WA 406 PLEASE HELP ME
[cpp]
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int maxnum;
int constant;
int prime_array[500];
int index;
int square_root;
bool ifprime;
int primenum;
int printnum;
int print_index;
int i;
prime_array[0] = 1;
prime_array[1] = 2;
while(!cin.eof())
{
primenum = 2;
cin >> maxnum >> constant;
if ( maxnum < 1 || maxnum > 1000)
continue;
if ( constant < 1)
continue;
for(i = 3 ; i <= maxnum ; i++)
{
index = 1;
square_root = sqrt(i);
ifprime = true;
while(prime_array[index] <= square_root)
{
if ( ( i % prime_array[index] ) == 0)
{
ifprime = false ;
break;
}
index++;
}
if (ifprime)
{
primenum++;
prime_array[primenum - 1] = i;
}
}
if (maxnum == 1)
cout << maxnum << " " << constant << ": 1" << endl;
else if (maxnum == 2)
cout << maxnum << " " << constant << ": 1 2" << endl;
else
{
cout << maxnum << " " << constant << ":" ;
if (primenum % 2) //odd
printnum = ( constant * 2 ) - 1;
else //even
printnum = constant * 2;
if (primenum <= printnum)
{
for(i = 0 ; i < primenum ; i++)
{
cout << " " << prime_array ;
}
cout << endl;
}
else
{
print_index = ( primenum - printnum ) / 2;
for(i = print_index ; i < ( printnum + print_index ) ; i++)
cout << " " << prime_array ;
cout << endl;
}
}
}
return 0;
}
WHY I GOT WA ???????
PLEASE HELP ME.. ... [/cpp]
Thanks for replay!
I know this!! But this error isn't happen with my tests!!!
I think that exist a kind of test that cause this error. Do you know?
Please, this is my code.
C:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>
typedef struct{
int n;
int c;
} Entrada;
int eh_primo(int num)
{
int qd=2,i;
double raiz;
raiz = (int)sqrt(num);
for (i=2;i<=raiz;i++)
{
if ((num%i) == 0)
return(0);
}
return(1);
}
void main(void)
{
int n=0, i=0, j=0, cont=0, c=0, print=0, a=0, b=0;
int A[200], centro=0, ini=0, fim=0, qtd=0;
Entrada *ent;
ent = malloc(100*sizeof(int));
while (scanf("%d %d",&a, &b) == 2)
{
ent[qtd].n = a;
ent[qtd].c = b;
qtd++;
}
for (j=0; j<qtd; j++)
{
n = ent[j].n;
c = ent[j].c;
cont = 0;
centro = 0;
ini = 0;
fim = 0;
print = 0;
for (i=1;i<=n;i++)
{
if (eh_primo(i))
{
A[cont] = i;
cont++;
}
}
printf("\n%d %d:",n,c);
if (c == 1)
{
print = cont/2;
printf(" %d",A[print]);
}
else if ((cont%2)==0)
{
centro = (cont/2);
ini = centro - c;
fim = centro + c -1;
if (ini < 0){ini = 0; fim = cont-1;}
for (print=ini; print<=fim; print++)
printf(" %d", A[print]);
}
else
{
centro = cont/2;
ini = centro - c + 1;
fim = centro + c - 1;
if (ini < 0){ini = 0; fim = cont-1;}
for (print=ini; print<=fim; print++)
printf(" %d", A[print]);
}
printf("\n");
}
free(ent);
}
I know this!! But this error isn't happen with my tests!!!
I think that exist a kind of test that cause this error. Do you know?
Please, this is my code.
C:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>
typedef struct{
int n;
int c;
} Entrada;
int eh_primo(int num)
{
int qd=2,i;
double raiz;
raiz = (int)sqrt(num);
for (i=2;i<=raiz;i++)
{
if ((num%i) == 0)
return(0);
}
return(1);
}
void main(void)
{
int n=0, i=0, j=0, cont=0, c=0, print=0, a=0, b=0;
int A[200], centro=0, ini=0, fim=0, qtd=0;
Entrada *ent;
ent = malloc(100*sizeof(int));
while (scanf("%d %d",&a, &b) == 2)
{
ent[qtd].n = a;
ent[qtd].c = b;
qtd++;
}
for (j=0; j<qtd; j++)
{
n = ent[j].n;
c = ent[j].c;
cont = 0;
centro = 0;
ini = 0;
fim = 0;
print = 0;
for (i=1;i<=n;i++)
{
if (eh_primo(i))
{
A[cont] = i;
cont++;
}
}
printf("\n%d %d:",n,c);
if (c == 1)
{
print = cont/2;
printf(" %d",A[print]);
}
else if ((cont%2)==0)
{
centro = (cont/2);
ini = centro - c;
fim = centro + c -1;
if (ini < 0){ini = 0; fim = cont-1;}
for (print=ini; print<=fim; print++)
printf(" %d", A[print]);
}
else
{
centro = cont/2;
ini = centro - c + 1;
fim = centro + c - 1;
if (ini < 0){ini = 0; fim = cont-1;}
for (print=ini; print<=fim; print++)
printf(" %d", A[print]);
}
printf("\n");
}
free(ent);
}