129 - Krypton Factor

[Cytoplasm]

Brute force it.

Generate all the data then reject the wrong ones!

it DOES work

[S M Adnan]

Thanx Cytoplasm, the Brute force approach realy works. I got AC.

[ranban282]

I'm trying to solve problem 129 using C++, and i'm geting WA.
Can anyone tell me whats wrong?

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
using namespace std;

int ispossible(vector<char> v,char a)
{
	int size=1;
	for(int start=v.size()-1;start>=0;start-=2,size++)
	{
		vector<int> tv1(size),tv2(size);
		for(int j=start;j<start+size;j++)
		{
			tv1[j-start]=v[j];
			
		}
		for(int j=start+size;j<v.size();j++)
		{
			tv2[j-(start+size)]=v[j];
		}
		tv2[size-1]=a;
		if(tv1==tv2)
			return 0;
	}
	return 1;
}
int gen(int limit,vector<char> v,int level,vector<char> & soln,int n,int & sum)
{	
	if(limit==sum)
	{
		for(int i=0;i<4 && i<v.size();i++)
				printf("%c",v[i]);
		for(int i=1;i<=v.size()/4 && i<16;i++)
		{
			printf(" ");
			for(int j=0;j<4&& i*4+j <v.size();j++)
				printf("%c",v[i*4+j]);
		}
		printf("\n");
		if(limit>64)
		{
				for(int i=0;i<4 && i<v.size();i++)
					printf("%c",v[i]);
			for(int i=16;i<=v.size()/4;i++)
			{
				printf(" ");
				for(int j=0;j<4&& i*4+j <v.size();j++)
					printf("%c",v[i*4+j]);
			}
			printf("\n");
		}
		printf("%d\n",level);
		return 1;

	}


	for(int i=0;i<n;i++)
	{
		if(ispossible(v,i+'A'))
		{
			v.push_back(i+'A');
			sum++;
			int p=gen(limit,v,level+1,soln,n,sum);
			if(p==1)
				return 1;
			v.pop_back();
		}
	}
}

int main()
{
	int m,n;
	while(1)
	{
		cin>>m>>n;
		if(m==0 && n==0)
			break;
		vector<char> v,soln;
		int sum=0;
		gen(m,v,0,soln,n,sum);

	}	
	
	return 0;
}

Some test data would help me a lot.

[Jan]

Check the I/O sets...

Input:

Code: Select all

71 13
0 0

Output:

Code: Select all

ABAC ABAD ABAC ABAE ABAC ABAD ABAC ABAF ABAC ABAD ABAC ABAE ABAC ABAD ABAC ABAG
ABAC ABA
71

Hope these help.

[kn]

I tried for 1x times, still got PE
please help me...

#include <stdio.h>
#include <stdio.h>
#define MAX_LENGTH 1000 /* MAX LENGTH OF SEQ */

int L;
int n;
int index=0;

int counter=0;

char seq[MAX_LENGTH+1];

void recursion();
void printseq();

main(){
int i;
while(scanf("%d", &n)!=EOF){
scanf("%d", &L);

if(n==0 && L==0) break;

counter = 0;
index = 0;
seq[0] = '\0';

recursion();
printf("\n");
}
return;
}

void recursion(){
int i, j, k;
int OK;

if(counter==n) return;

for(i=0; i<L; i++){

if(counter==n) return;

OK=1;

seq[index] = 'A'+i;
seq[index+1] = '\0';

index++;

for(j=1; j<=index/2; j++){
if(counter==n) return;
/* CHECKING */
if(!strncmp(seq+index-j, seq+index-j-j, j)){
OK=0;
break;
}
}

if(OK){
counter++;
if(counter==n){
printseq();
printf("\n", seq);
printf("%d", index);
return;
}

recursion();
}
index--;
}
return;
}

void printseq(){
int i;
int leng = strlen(seq);
for(i=1; i<=leng; i++){
printf("%c", seq[i-1]);
if(i && !(i%4)){
if(!(i%64))
printf("\n");
else
printf(" ");
}
}
}


Also, I'd like to ask
what exactly the format of the output looks like?
Please help kindly help me to remove the bug...

[Jan]

Search the board first. Don't open a new thread if there is one already.

[kn]

Sorry for opening new threads...

I tried for 1x times, still got PE
please help me...
here's my piece of code

#include <stdio.h>
#include <stdio.h>
#define MAX_LENGTH 1000 /* MAX LENGTH OF SEQ */

int L;
int n;
int index=0;

int counter=0;

char seq[MAX_LENGTH+1];

void recursion();
void printseq();

main(){
int i;
while(scanf("%d", &n)!=EOF){
scanf("%d", &L);

if(n==0 && L==0) break;

counter = 0;
index = 0;
seq[0] = '\0';

recursion();
printf("\n");
}
return;
}

void recursion(){
int i, j, k;
int OK;

if(counter==n) return;

for(i=0; i<L; i++){

if(counter==n) return;

OK=1;

seq[index] = 'A'+i;
seq[index+1] = '\0';

index++;

for(j=1; j<=index/2; j++){
if(counter==n) return;
/* CHECKING */
if(!strncmp(seq+index-j, seq+index-j-j, j)){
OK=0;
break;
}
}

if(OK){
counter++;
if(counter==n){
printseq();
printf("\n", seq);
printf("%d", index);
return;
}

recursion();
}
index--;
}
return;
}

void printseq(){
int i;
int leng = strlen(seq);
for(i=1; i<=leng; i++){
printf("%c", seq[i-1]);
if(i && !(i%4)){
if(!(i%64))
printf("\n");
else
printf(" ");
}
}
}


I'd like to ask what exactly the format of the output looks like?
Please help kindly help me to remove the presentation error...

[Jan]

Try the case...

Input:

Code: Select all

69 3
0 0

Output:

Code: Select all

ABAC ABCA CBAB CABA CABC ACBA CABA CBAB CABA CABC ACBA BCAB ACBA BCAC BACA BACB
64

Hope it helps.

PS : Next time use code tags to post your code. And after getting accepted you should remove your code.

[kn]

For input...

Code: Select all

69 3
72 3
0 0

Which outputs are correct?

Code: Select all

ABAC ABCA CBAB CABA CABC ACBA CABA CBAB CABA CABC ACBA BCAB ACBA BCAC BACA BACB[*nospace]\n
64\n
ABAC ABCA CBAB CABA CABC ACBA CABA CBAB CABA CABC ACBA BCAB ACBA BCAC BACA BACB[*nospace]\n
ABC\n
67

Code: Select all

ABAC ABCA CBAB CABA CABC ACBA CABA CBAB CABA CABC ACBA BCAB ACBA BCAC BACA BACB[*nospace]\n
64\n
ABAC ABCA CBAB CABA CABC ACBA CABA CBAB CABA CABC ACBA BCAB ACBA BCAC BACA BACB[*nospace]\n
ABC\n
67\n

Or both are incorrect?
I'm totally confused by the format....[/code]

[S.H.Bouwhuis]

I have the same problem with Presentation Error.

I tried with and without a trailing end-of-line after the last solution, but still get PE.

Input

Code: Select all

7 3
30 3
71 13 
69 3
0 0

Output

Code: Select all

ABAC ABA
7
ABAC ABCA CBAB CABA CABC ACBA CABA
28
ABAC ABAD ABAC ABAE ABAC ABAD ABAC ABAF ABAC ABAD ABAC ABAE ABAC ABAD ABAC ABAG
ABAC ABA
71
ABAC ABCA CBAB CABA CABC ACBA CABA CBAB CABA CABC ACBA BCAB ACBA BCAC BACA BACB
64

Are there any other problems someone can see?

[Jan]

My accepted code returns same output.