524 - Prime Ring Problem

[laituan245]

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]

For n=13 there shouldn't be any circles. Your Prime array should be larger than 17.

[Mukit Chowdhury]

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]

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 visitados[MAX];
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};

void init_visitados(int visitados[MAX]){
    int i;
    visitados[0] = 1;
    for(i=1;i<MAX;i++)
        visitados[i] = 0;
}

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 (contador == numero){
        if ( primos[ soluciones[*nsols][contador-1] + soluciones[*nsols ][0] ] ){
            (*nsols)++;
            return 0;
        }
    }
    int i;
    for(i=2;i<=numero;i++){
        soluciones[*nsols][contador] = i;
        if (!visitados[i-1]){
            if ( primos[ soluciones[*nsols][contador] + soluciones[*nsols][contador-1] ] ){
                visitados[i-1] = 1;
                if ( llenar(soluciones,contador+1,numero,nsols) )
                    return 1;
                visitados[i-1] = 0;
                soluciones[*nsols][contador] = 0;
            }            
        }
    }
    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_visitados(visitados);
            init_soluciones(soluciones);
            ncasos++;
            llenar(soluciones,1,num,&nsols);
            printf("Case %d:\n",ncasos);
            imprime(soluciones,num,nsols);
        }
        nsols = 0;
    }
    return 0;
}

[brianfry713]

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

[samoel_stt]

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 visitados[MAX];
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]; 
}
void initV(int visitados[]){
    int i;
    visitados[0] = 1;
    for(i=1;i<MAX;i++)
        visitados[i]=0;
}
int llena(int circle[], int visitados[], int contador,int numero){
    int i;
    if ( contador == numero){
        if ( prim[circle[contador-1]][circle[0]] ){
            for(i=0;i<contador-1;i++)
                printf("%d ",circle[i]);
            printf("%d\n",circle[contador-1]);
            return 0;
        }
        return 0;
    }    
    for(i=2;i<=numero;i++){
        if ( !visitados[i] ){
            if (prim[i][circle[contador-1]] ){
                circle[contador] = i;
                visitados[i] = 1;
                if ( llena(circle,visitados,contador+1,numero) ){
                    return 1;
                }
                circle[contador] = 0;
                visitados[i] = 0;
            }
        }
    }
    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){
            initV(visitados);
            ncasos++;
            int circle[num];
            int i;circle[0] = 1;
            for(i=1;i<num;i++){
                circle[i] = 0;
            }
            printf("Case %d:\n",ncasos);
            llena(circle,visitados,1,num);
        }
    }    
    return 0;
}

[brianfry713]

Print a blank line between cases.

[samoel_stt]

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]

In the judge's input 0 < n <= 16

[just_yousef]

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]

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

[fahr_rad]

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]

Post your full code that you'd actually submit. That won't compile without the imports.

[tahsinc]

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]

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