Page 2 of 2
Posted: Thu Aug 11, 2005 6:40 pm
by Cytoplasm
Brute force it.
Generate all the data then reject the wrong ones!
it DOES work
Posted: Sat Aug 13, 2005 1:52 am
by S M Adnan
Thanx Cytoplasm, the Brute force approach realy works. I got AC.
WHY WA?????
Posted: Tue Dec 19, 2006 7:43 pm
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.
Posted: Tue Dec 19, 2006 8:23 pm
by Jan
Check the I/O sets...
Input:
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.
129 PE
Posted: Mon Apr 23, 2007 12:39 am
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...
Posted: Mon Apr 23, 2007 3:12 pm
by Jan
Search the board first. Don't open a new thread if there is one already.
PE for 129
Posted: Wed Apr 25, 2007 11:11 am
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...
Posted: Wed Apr 25, 2007 7:37 pm
by Jan
Try the case...
Input:
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.
Posted: Thu Apr 26, 2007 4:18 pm
by kn
For input...
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]
Posted: Fri Apr 27, 2007 12:09 pm
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
OutputCode: 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?
Posted: Sat Apr 28, 2007 10:27 pm
by Jan
My accepted code returns same output.