Page 5 of 5
Re: Help me plz
Posted: Wed Jul 04, 2012 12:40 pm
by 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);
}
}
}
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Thu Jul 05, 2012 4:03 am
by brianfry713
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
by 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");
}
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Wed Jun 18, 2014 2:12 am
by 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;
}
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Wed Jun 18, 2014 11:27 pm
by 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
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Sat Jun 21, 2014 11:03 pm
by 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;
}
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Mon Jun 23, 2014 9:38 pm
by brianfry713
Print a blank line between cases.
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Mon Jun 23, 2014 10:09 pm
by 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:
should give:
or i just ignore that cases?
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Tue Jun 24, 2014 8:29 pm
by brianfry713
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
by 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;
}
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Sat Jul 26, 2014 7:09 pm
by 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
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Sun Aug 03, 2014 6:31 pm
by 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++;
}
}
}
Re: 524 - The Prime Ring Problem - Is backtracking the only
Posted: Tue Aug 05, 2014 12:17 am
by brianfry713
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
by 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;
}
Re: 524 - Prime Ring Problem
Posted: Tue Jul 28, 2015 1:03 pm
by uDebug
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