Page 5 of 5

### Re: Help me plz

Posted: Wed Jul 04, 2012 12:40 pm
I don't know why but i keep getting WA.
I think i have checked all the cases (hopefully)
Can anyone help me please ?

Code: Select all

``````        #include <iostream>
#include<cstdio>
using namespace std;
static int n;
static int data [17];
static bool used[17];
static bool Prime[17];
void test (int k)
{
for (int i = 2; i <= n; i++)
if (used[i] == false && Prime [i+data[k-1]])
{
data[k] = i;
used[i] = true;
if (k == n)
{
if (Prime [data[k] + data[1]])
{
for(int i=1;i<n;i++)
printf("%d ",data[i]);
printf("%d\n",data[n]);

}

}
else
test (k+1);
used[i] = false;
}
}
int main ()
{
Prime[2] = true;
Prime[3] = true;
Prime[5] = true;
Prime[7] = true;
Prime[11] = true;
Prime[13] = true;
Prime[17] = true;
Prime[19] = true;
Prime[23] = true;
Prime[29] = true;
Prime[31] = true;
int c = 0;
while (cin >> n)
{
if (c != 0)
printf("\n");
c++;
printf("Case %d:\n",c);
if (n == 1)
cout << "1\n";
else
{
for (int i = 1; i <= 16; i++)
used[i] = false;
data[1] = 1;
used[1] = true;
test (2);
}
}
}

``````

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Thu Jul 05, 2012 4:03 am
For n=13 there shouldn't be any circles. Your Prime array should be larger than 17.

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Mon Oct 08, 2012 5:13 pm
Getting WA !!! But I can't understand why it is... Please help me someone to find the bug !!!!

Code: Select all

``````while(1)
{
printf("Accepted\n");
}
``````

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Wed Jun 18, 2014 2:12 am
I tried solving this problem using backtracking but i dont get the right answer for inputs greater than 6. For input 8 i get this:

Code: Select all

``````Case 1:
1 2 3 8 5 6 7 4
1 0 5 8 3 4 7 6
1 0 7 4 3 8 5 6
1 4 7 6 5 8 5 2
1 0 0 0 5 8 3 2
``````
HereĀ“s the code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define MAX 16
#define MAXSOL 100000

int soluciones[MAXSOL][MAX];
int primos[32]= {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1};

int i;
for(i=1;i<MAX;i++)
}

void init_soluciones(int soluciones[MAXSOL][MAX]){
int i,j;
for(i=0;i<MAXSOL;i++){
soluciones[i][0] = 1;
for(j=1;j<MAX;j++)
soluciones[i][j] = 0;
}
}

int llenar(int soluciones[MAXSOL][MAX],int contador, int numero, int *nsols){
if ( primos[ soluciones[*nsols][contador-1] + soluciones[*nsols ][0] ] ){
(*nsols)++;
return 0;
}
}
int i;
for(i=2;i<=numero;i++){
return 1;
}
}
}
return 0;
}
void imprime(int soluciones[MAXSOL][MAX], int tam,int numsols){
int i,j;
printf("%d\n",numsols);
for(i=0;i<numsols;i++){
printf("%d", soluciones[i][0]);
for(j=1;j<tam;j++)
printf(" %d",soluciones[i][j]);
printf("\n");
}
}
int main(void){
int ncasos = 0, nsols = 0, num;
for(;;){
if ( scanf("%d",&num) == EOF ) break;
if (num % 2 == 0 && 0<num && num <= 16){
init_soluciones(soluciones);
ncasos++;
llenar(soluciones,1,num,&nsols);
printf("Case %d:\n",ncasos);
imprime(soluciones,num,nsols);
}
nsols = 0;
}
return 0;
}
``````

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Wed Jun 18, 2014 11:27 pm
Correct output for input 8:

Code: Select all

``````Case 1:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
``````

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Sat Jun 21, 2014 11:03 pm
I have corrected some mistakes in my initial code, but I still get WA. What I'm missing?

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#define MAX 16
int primos[33]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0};
int prim[MAX][MAX];
void primInit(int prim[MAX][MAX] ){
int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
prim[i+1][j+1] = primos[i+j+2];
}
int i;
for(i=1;i<MAX;i++)
}
int i;
printf("%d ",circle[i]);
return 0;
}
return 0;
}
for(i=2;i<=numero;i++){
return 1;
}
}
}
}
return 0;
}
int main(void){
int num,ncasos = 0;
primInit(prim);
for(;;){
if ( scanf("%d",&num) == EOF) break;
if (num % 2 == 0 && 0<num && num<=MAX){
ncasos++;
int circle[num];
int i;circle[0] = 1;
for(i=1;i<num;i++){
circle[i] = 0;
}
printf("Case %d:\n",ncasos);
}
}
return 0;
}
``````

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Mon Jun 23, 2014 9:38 pm
Print a blank line between cases.

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Mon Jun 23, 2014 10:09 pm
Thanks for that, but i sent it again but got WA again. What happens when there is a negative number or greater than 16? Should I count them as a blank case?
Like this:

Code: Select all

``````Input:
-1
2
18
``````
should give:

Code: Select all

``````Case 1:

Case 2:
1 2

Case 3:

``````
or i just ignore that cases?

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Tue Jun 24, 2014 8:29 pm
In the judge's input 0 < n <= 16

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Sat Jul 26, 2014 3:39 am
Way WA ??

Code: Select all

``````#include <bits/stdc++.h>
using namespace std;

bool f[50];
char ch[200];
vector<int> arr[18];
int n;
void siv() {
f[0] = f[1] = 1;
for (int i = 2; i * i < 50; ++i) {
if (!f[i])
for (int j = i * i; j < 50; j += i)
f[j] = 1;
}
}
int sum;
void bktk(int x, int msk, int cnt, int sz) {
if (cnt == n - 1) {
if (!f[x + 1])
printf("%s %d\n", ch, x);
return;
}
for (int i = 0, ln = arr[x].size(), l = sz; i < ln; ++i) {
int y = arr[x][i];
if (y > n || (msk & (1 << y)))
continue;
if (sz)
ch[sz++] = ' ';
if (x > 9)
ch[sz++] = (x / 10) + '0';
ch[sz++] = (x % 10) + '0';
bktk(y, (msk | (1 << y)), cnt + 1, sz);
sz = l;
}
}

int main(int argc, char **argv) {
//freopen("a.in", "r", stdin);
siv();
for (int i = 1; i <= 16; ++i)
for (int j = 1; j <= 16; ++j)
if ((i != j) && !f[i + j])
arr[i].push_back(j);

int cas = 0;
while (scanf("%d", &n) > 0) {
if (cas)
puts("");
printf("Case %d:\n", ++cas);
sum = 0;
if (n == 1)
puts("1");
else
bktk(1, (1 << 1), 0, 0);
}
return 0;
}
``````

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Sat Jul 26, 2014 7:09 pm
Your program gives for n = 10. Part of output

Code: Select all

``````Case 1:
1 2 3 4 7 6 5 8 9 10
1 2 3 4 7 10 9 8 5 6
1 2 3 4 9 8 5 6 75 10
1 2 3 8 5 6 7 4 95 10
1 2 3 8 5 6 7 10 9 4
1 2 3 10 7 4 9 8 5 6
1 2 3 10 7 6 5 8 9 4
1 2 3 10 9 8 5 6 7 4
...
``````
Look at these lines

Code: Select all

``````1 2 3 4 9 8 5 6 75 10
1 2 3 8 5 6 7 4 95 10``````

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Sun Aug 03, 2014 6:31 pm
I am trying to solve this problem and I think my programm is rigth , but I still get WA. I am pretty sure that I forgot any whitespace or kind like that.
But I can't find the mistake.

Code: Select all

``````public class Main {
public  boolean [] primes = new boolean[33];
int[] array;
boolean[] used;
StringBuilder builder;
int counter = 0;

Main() {
primes[0] = false; primes[1]= false; primes[2]= true; primes[3] = true; primes[4] = false; primes[5] = true; primes[6] = false;
primes[7] = true; primes[8] = false; primes[9] = false; primes[10] = false; primes[11] = true; primes[12] = false;
primes[13] = true; primes[14] = false; primes[15] = false; primes[16] = false; primes[17]=true; primes[18]= false;
primes[19] = true; primes[20]=false; primes[21]=false; primes[22]= false; primes[23] = true; primes[24]=false; primes[25] = false;
primes[26] = false; primes[27] = false; primes[28] = false; primes[29] = true; primes[30] = false; primes[31] = true;
}
void calculate(int n, int count) {
builder = new StringBuilder();
this.array = new int[n];
used = new boolean[n+1];
used[1] = true;
this.array[0] = 1;

if (count != 1) {
System.out.println("\n");
}
System.out.print("Case " + count +":");

if (n % 2 == 0) {
calRec(1);

System.out.print(builder);
}

}

void calRec(int param) {

for (int i = 2; i <= array.length; i++) {
if (!used[i]) {

if (param < array.length) {
array[param]  = i;
// +++++++++++++++++ test +++++++++++++
boolean test = false;
// prime test
if (primes[array[param -1]+ array[param]]) {
if(param == array.length - 1) {
if (primes[array[0]+ array[param]]) {
test = true;
}
}
else {
test = true;
}
}
// next recursion or append if finished
if (test) {
if (param + 1 == array.length) {

builder.append("\n");
for (int a = 0 ; a < array.length; a++) {
builder.append(array[a]);
if (a != array.length - 1) {
builder.append(" ");
}
}
used[array[param-1]] = false;
return;
}
used[i] = true;
calRec(param +1);
}
array[param] = 0;

}
}
}
used[array[param-1]] = false;
array[param] = 0;

}

public static void main(String[] args) {

int count = 1;
Main test = new Main();
Scanner s = new Scanner(System.in);
while(s.hasNextInt()) {

int n = s.nextInt();

test.calculate(n,count);
count++;

}

}

}
``````

### Re: 524 - The Prime Ring Problem - Is backtracking the only

Posted: Tue Aug 05, 2014 12:17 am
Post your full code that you'd actually submit. That won't compile without the imports.

### Re: 524 - Prime Ring Problem

Posted: Thu Jul 09, 2015 6:05 am
I am getting WA over and over again. .I followed the all the Re post, check the counter number for this. Please, check my code and help me to find where I did the mistake. Here, is the code below:

Code: Select all

``````#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int N;
int A[100], used[100];
void Print()
{
for (int i = 0; i<N; i++)
{
cout<<A[i];
if(i!=N-1) cout<<' ';
}
cout<<endl;
}

bool isPrime(int n)
{
int sq = sqrt(n);
for( int k = 2; k<= sq; k++ )
{
if(n%k == 0) return false;
}
return true;
}
int counter = 0;
void Permutation(int p)
{
if(p == N)
{
if ( isPrime( A[0]+A[N-1] ) )
{
Print();
//counter++;
}
return;
}
for(int j= 1; j<=N; j++) if(used[j] == 0 && isPrime(j+A[p-1]))
{
A[p] = j;
used[j] = 1;
Permutation(p+1);
used[j] = 0;
}
}

int main()
{
int i = 0;
while(cin>>N)
{
memset(used, 0, sizeof(used));
memset(A, 0, sizeof(A));
i++;
cout<<"Case "<<i<<":"<<endl;
if( N>0 && N<=16 )
{
//counter = 0;
A[0] = 1;used[1] = 1;
Permutation(1);
//cout<<counter<<endl;
}
cout<<endl;
}
return 0;
}``````

### Re: 524 - Prime Ring Problem

Posted: Tue Jul 28, 2015 1:03 pm
tahsinc wrote:I am getting WA over and over again. .I followed the all the Re post, check the counter number for this. Please, check my code and help me to find where I did the mistake. Here, is the code below:
See

http://www.udebug.com/UVa/524