## 524 - Prime Ring Problem

Moderator: Board moderators

laituan245
New poster
Posts: 1
Joined: Wed Jul 04, 2012 12:38 pm

### Re: Help me plz

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);
}
}
}

``````

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

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

For n=13 there shouldn't be any circles. Your Prime array should be larger than 17.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

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

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");
}
``````

samoel_stt
New poster
Posts: 8
Joined: Mon Jun 16, 2014 11:59 pm

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

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;
}
``````

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

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

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
``````
Check input and AC output for thousands of problems on uDebug!

samoel_stt
New poster
Posts: 8
Joined: Mon Jun 16, 2014 11:59 pm

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

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;
}
``````

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

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

Print a blank line between cases.
Check input and AC output for thousands of problems on uDebug!

samoel_stt
New poster
Posts: 8
Joined: Mon Jun 16, 2014 11:59 pm

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

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?

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

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

In the judge's input 0 < n <= 16
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

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

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;
}
``````

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

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

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``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

New poster
Posts: 1
Joined: Sun Aug 03, 2014 6:22 pm

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

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++;

}

}

}
``````

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

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

Post your full code that you'd actually submit. That won't compile without the imports.
Check input and AC output for thousands of problems on uDebug!

tahsinc
New poster
Posts: 1
Joined: Thu Jul 09, 2015 6:00 am

### Re: 524 - Prime Ring Problem

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;
}``````

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 524 - Prime Ring Problem

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
Check input and AC output for over 7,500 problems on uDebug!