129 - Krypton Factor

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Cytoplasm
New poster
Posts: 13
Joined: Tue Jun 14, 2005 6:33 pm
Location: Paris, France

Post by Cytoplasm »

Brute force it.

Generate all the data then reject the wrong ones!

it DOES work
S M Adnan
New poster
Posts: 4
Joined: Wed Aug 10, 2005 10:43 pm
Location: Dhaka, Bangladesh
Contact:

Post by S M Adnan »

Thanx Cytoplasm, the Brute force approach realy works. I got AC.
Hul Hul
ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

WHY WA?????

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage
kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

129 PE

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage
kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

PE for 129

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage
kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

Post by 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
New poster
Posts: 13
Joined: Fri Apr 27, 2007 12:03 pm
Location: The Netherlands

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

My accepted code returns same output.
Ami ekhono shopno dekhi...
HomePage
Post Reply

Return to “Volume 1 (100-199)”