10950 - Bad Code

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

Moderator: Board moderators

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

10950 - Bad Code

Post by TISARKER » Sun Oct 30, 2005 5:55 am

I am getting wrong answer . :cry:
I checked all possible case as my ability.
Please give me some input and output for which my program give wrong output.

Code: Select all

Remove After Accepted.
Last edited by TISARKER on Sun Oct 30, 2005 10:45 pm, edited 1 time in total.
Mr. Arithmetic logic Unit

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Sun Oct 30, 2005 6:14 am

I got WA too

but I think I can support some

Code: Select all

1
a 0
000
0
I think the output should be

Code: Select all

Case #1
aaa
hope it help
Last edited by polone on Sun Oct 30, 2005 9:09 am, edited 2 times in total.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sun Oct 30, 2005 7:55 am

hi
my output is
aaa
Last edited by SRX on Sun Oct 30, 2005 1:54 pm, edited 1 time in total.
studying @ ntu csie

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Oct 30, 2005 8:15 am

You can try the following input...

Input:

Code: Select all

3
a 0
b 01
c 10
00110001
0
Output:

Code: Select all

Case #1
abcab
Hope it works.
Ami ekhono shopno dekhi...
HomePage

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Sun Oct 30, 2005 9:10 am

Sorry I misunderstanding the problem...

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Sun Oct 30, 2005 9:47 am

deleted:)
Last edited by polone on Sun Oct 30, 2005 4:35 pm, edited 1 time in total.

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Sun Oct 30, 2005 2:52 pm

I'm sorry, but I don't think the above sample input is valid, since the problem clearly states that
every character is replaced by a unique positive integer value
So "a 0" is not a valid replacement, therefore the input is not valid. I'm not sure if there can be an input like "a 0001", but my AC problem wouldn't work very well with these inputs. If you want, you can try this test case (altought I'm not sure it's a very good one):

[edit] LittleJoey is correct, the output I had posted was not legal. Sorry! I created a new one (hope this one is ok) [/edit]

Input

Code: Select all

10
a 1
b 5
c 3
d 9
e 2
f 7
g 4
h 8
i 10
j 59
3151013951010101029529531395951259953951235995125910319535192391
Output

Code: Select all

Case #1
cabaacdbaaaaedbedbcacdbdbaebddbcdbaecbddbaebdacadbcbadecda
cabaacdbaaaaedbedbcacdbdbaebddbcdbaecbddbaebdicadbcbadecda
cabaacdbaaaaedbedbcacdbdbaebddbcdbaecbddbaejacadbcbadecda
cabaacdbaaaaedbedbcacdbdbaebddbcdbaecbddbaejicadbcbadecda
cabaacdbaaaaedbedbcacdbdbaebddbcdbaecjdbaebdacadbcbadecda
cabaacdbaaaaedbedbcacdbdbaebddbcdbaecjdbaebdicadbcbadecda
cabaacdbaaaaedbedbcacdbdbaebddbcdbaecjdbaejacadbcbadecda
cabaacdbaaaaedbedbcacdbdbaebddbcdbaecjdbaejicadbcbadecda
cabaacdbaaaaedbedbcacdbdbaejdbcdbaecbddbaebdacadbcbadecda
cabaacdbaaaaedbedbcacdbdbaejdbcdbaecbddbaebdicadbcbadecda
cabaacdbaaaaedbedbcacdbdbaejdbcdbaecbddbaejacadbcbadecda
cabaacdbaaaaedbedbcacdbdbaejdbcdbaecbddbaejicadbcbadecda
cabaacdbaaaaedbedbcacdbdbaejdbcdbaecjdbaebdacadbcbadecda
cabaacdbaaaaedbedbcacdbdbaejdbcdbaecjdbaebdicadbcbadecda
cabaacdbaaaaedbedbcacdbdbaejdbcdbaecjdbaejacadbcbadecda
cabaacdbaaaaedbedbcacdbdbaejdbcdbaecjdbaejicadbcbadecda
cabaacdbaaaaedbedbcacdjbaebddbcdbaecbddbaebdacadbcbadecda
cabaacdbaaaaedbedbcacdjbaebddbcdbaecbddbaebdicadbcbadecda
cabaacdbaaaaedbedbcacdjbaebddbcdbaecbddbaejacadbcbadecda
cabaacdbaaaaedbedbcacdjbaebddbcdbaecbddbaejicadbcbadecda
cabaacdbaaaaedbedbcacdjbaebddbcdbaecjdbaebdacadbcbadecda
cabaacdbaaaaedbedbcacdjbaebddbcdbaecjdbaebdicadbcbadecda
cabaacdbaaaaedbedbcacdjbaebddbcdbaecjdbaejacadbcbadecda
cabaacdbaaaaedbedbcacdjbaebddbcdbaecjdbaejicadbcbadecda
cabaacdbaaaaedbedbcacdjbaejdbcdbaecbddbaebdacadbcbadecda
cabaacdbaaaaedbedbcacdjbaejdbcdbaecbddbaebdicadbcbadecda
cabaacdbaaaaedbedbcacdjbaejdbcdbaecbddbaejacadbcbadecda
cabaacdbaaaaedbedbcacdjbaejdbcdbaecbddbaejicadbcbadecda
cabaacdbaaaaedbedbcacdjbaejdbcdbaecjdbaebdacadbcbadecda
cabaacdbaaaaedbedbcacdjbaejdbcdbaecjdbaebdicadbcbadecda
cabaacdbaaaaedbedbcacdjbaejdbcdbaecjdbaejacadbcbadecda
cabaacdbaaaaedbedbcacdjbaejdbcdbaecjdbaejicadbcbadecda
cabaacdbaaaiedbedbcacdbdbaebddbcdbaecbddbaebdacadbcbadecda
cabaacdbaaaiedbedbcacdbdbaebddbcdbaecbddbaebdicadbcbadecda
cabaacdbaaaiedbedbcacdbdbaebddbcdbaecbddbaejacadbcbadecda
cabaacdbaaaiedbedbcacdbdbaebddbcdbaecbddbaejicadbcbadecda
cabaacdbaaaiedbedbcacdbdbaebddbcdbaecjdbaebdacadbcbadecda
cabaacdbaaaiedbedbcacdbdbaebddbcdbaecjdbaebdicadbcbadecda
cabaacdbaaaiedbedbcacdbdbaebddbcdbaecjdbaejacadbcbadecda
cabaacdbaaaiedbedbcacdbdbaebddbcdbaecjdbaejicadbcbadecda
cabaacdbaaaiedbedbcacdbdbaejdbcdbaecbddbaebdacadbcbadecda
cabaacdbaaaiedbedbcacdbdbaejdbcdbaecbddbaebdicadbcbadecda
cabaacdbaaaiedbedbcacdbdbaejdbcdbaecbddbaejacadbcbadecda
cabaacdbaaaiedbedbcacdbdbaejdbcdbaecbddbaejicadbcbadecda
cabaacdbaaaiedbedbcacdbdbaejdbcdbaecjdbaebdacadbcbadecda
cabaacdbaaaiedbedbcacdbdbaejdbcdbaecjdbaebdicadbcbadecda
cabaacdbaaaiedbedbcacdbdbaejdbcdbaecjdbaejacadbcbadecda
cabaacdbaaaiedbedbcacdbdbaejdbcdbaecjdbaejicadbcbadecda
cabaacdbaaaiedbedbcacdjbaebddbcdbaecbddbaebdacadbcbadecda
cabaacdbaaaiedbedbcacdjbaebddbcdbaecbddbaebdicadbcbadecda
cabaacdbaaaiedbedbcacdjbaebddbcdbaecbddbaejacadbcbadecda
cabaacdbaaaiedbedbcacdjbaebddbcdbaecbddbaejicadbcbadecda
cabaacdbaaaiedbedbcacdjbaebddbcdbaecjdbaebdacadbcbadecda
cabaacdbaaaiedbedbcacdjbaebddbcdbaecjdbaebdicadbcbadecda
cabaacdbaaaiedbedbcacdjbaebddbcdbaecjdbaejacadbcbadecda
cabaacdbaaaiedbedbcacdjbaebddbcdbaecjdbaejicadbcbadecda
cabaacdbaaaiedbedbcacdjbaejdbcdbaecbddbaebdacadbcbadecda
cabaacdbaaaiedbedbcacdjbaejdbcdbaecbddbaebdicadbcbadecda
cabaacdbaaaiedbedbcacdjbaejdbcdbaecbddbaejacadbcbadecda
cabaacdbaaaiedbedbcacdjbaejdbcdbaecbddbaejicadbcbadecda
cabaacdbaaaiedbedbcacdjbaejdbcdbaecjdbaebdacadbcbadecda
cabaacdbaaaiedbedbcacdjbaejdbcdbaecjdbaebdicadbcbadecda
cabaacdbaaaiedbedbcacdjbaejdbcdbaecjdbaejacadbcbadecda
cabaacdbaaaiedbedbcacdjbaejdbcdbaecjdbaejicadbcbadecda
cabaacdbaaiaedbedbcacdbdbaebddbcdbaecbddbaebdacadbcbadecda
cabaacdbaaiaedbedbcacdbdbaebddbcdbaecbddbaebdicadbcbadecda
cabaacdbaaiaedbedbcacdbdbaebddbcdbaecbddbaejacadbcbadecda
cabaacdbaaiaedbedbcacdbdbaebddbcdbaecbddbaejicadbcbadecda
cabaacdbaaiaedbedbcacdbdbaebddbcdbaecjdbaebdacadbcbadecda
cabaacdbaaiaedbedbcacdbdbaebddbcdbaecjdbaebdicadbcbadecda
cabaacdbaaiaedbedbcacdbdbaebddbcdbaecjdbaejacadbcbadecda
cabaacdbaaiaedbedbcacdbdbaebddbcdbaecjdbaejicadbcbadecda
cabaacdbaaiaedbedbcacdbdbaejdbcdbaecbddbaebdacadbcbadecda
cabaacdbaaiaedbedbcacdbdbaejdbcdbaecbddbaebdicadbcbadecda
cabaacdbaaiaedbedbcacdbdbaejdbcdbaecbddbaejacadbcbadecda
cabaacdbaaiaedbedbcacdbdbaejdbcdbaecbddbaejicadbcbadecda
cabaacdbaaiaedbedbcacdbdbaejdbcdbaecjdbaebdacadbcbadecda
cabaacdbaaiaedbedbcacdbdbaejdbcdbaecjdbaebdicadbcbadecda
cabaacdbaaiaedbedbcacdbdbaejdbcdbaecjdbaejacadbcbadecda
cabaacdbaaiaedbedbcacdbdbaejdbcdbaecjdbaejicadbcbadecda
cabaacdbaaiaedbedbcacdjbaebddbcdbaecbddbaebdacadbcbadecda
cabaacdbaaiaedbedbcacdjbaebddbcdbaecbddbaebdicadbcbadecda
cabaacdbaaiaedbedbcacdjbaebddbcdbaecbddbaejacadbcbadecda
cabaacdbaaiaedbedbcacdjbaebddbcdbaecbddbaejicadbcbadecda
cabaacdbaaiaedbedbcacdjbaebddbcdbaecjdbaebdacadbcbadecda
cabaacdbaaiaedbedbcacdjbaebddbcdbaecjdbaebdicadbcbadecda
cabaacdbaaiaedbedbcacdjbaebddbcdbaecjdbaejacadbcbadecda
cabaacdbaaiaedbedbcacdjbaebddbcdbaecjdbaejicadbcbadecda
cabaacdbaaiaedbedbcacdjbaejdbcdbaecbddbaebdacadbcbadecda
cabaacdbaaiaedbedbcacdjbaejdbcdbaecbddbaebdicadbcbadecda
cabaacdbaaiaedbedbcacdjbaejdbcdbaecbddbaejacadbcbadecda
cabaacdbaaiaedbedbcacdjbaejdbcdbaecbddbaejicadbcbadecda
cabaacdbaaiaedbedbcacdjbaejdbcdbaecjdbaebdacadbcbadecda
cabaacdbaaiaedbedbcacdjbaejdbcdbaecjdbaebdicadbcbadecda
cabaacdbaaiaedbedbcacdjbaejdbcdbaecjdbaejacadbcbadecda
cabaacdbaaiaedbedbcacdjbaejdbcdbaecjdbaejicadbcbadecda
cabaacdbaaiiedbedbcacdbdbaebddbcdbaecbddbaebdacadbcbadecda
cabaacdbaaiiedbedbcacdbdbaebddbcdbaecbddbaebdicadbcbadecda
cabaacdbaaiiedbedbcacdbdbaebddbcdbaecbddbaejacadbcbadecda
cabaacdbaaiiedbedbcacdbdbaebddbcdbaecbddbaejicadbcbadecda
Last edited by danielrocha on Mon Oct 31, 2005 4:03 pm, edited 1 time in total.
Daniel
UFRN HDD-1
Brasil

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Oct 30, 2005 7:15 pm

For these inputs post in this thread:

Code: Select all

1
a 0
000
3
a 0
b 01
c 10
00110001
8
a 101
b 1
c 10
d 1001
e 1010
f 101010
g 101011
h 1010101
010101010101000101001010111010100101011010101010101011010101010101010110101010101011010101010101101
0
this is the different output for my AC code:

Code: Select all

Case #1
aaa
aa
aa

Case #2
abcab
abcb
bcab
bcb

Case #3

Then, I don't know if these are legal.
Some of them clearly are not.
I think that can confuse.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Oct 30, 2005 9:19 pm

No, they are not legal, since 0<code<100.

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Mon Oct 31, 2005 4:19 pm

Yes, you are correct. My previous input wasn't legal. I edited the post above, so now I hope it contains a valid input/output.
Daniel
UFRN HDD-1
Brasil

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Tue Nov 01, 2005 7:53 pm

hi everybody ,
i am getting wa in the problem . any i/o is appreciated ...

Code: Select all

code deleted after ac
Last edited by Riyad on Wed Nov 02, 2005 7:58 am, edited 1 time in total.
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue Nov 01, 2005 8:28 pm

Hi Riyad!
I haven't checked your code deeply, but for me is strange that you stop when your counter is 100 and then you sort the first 100 strings that you found. If you search in alphabetical order the first ones strings, the first 100 must be the first in alphabetical order, else you are sorting the first 100 strings that your algorithm find but maybe are not the first 100 of the total possible strings.
Maybe this is not your mistake but repeat, if you search in alphabetical order you don't need sort nothing, else the first 100 that your algorithm find maybe are not the first 100 in alphabetical order.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Wed Nov 02, 2005 7:25 am

hey emilio ,
thanx for the reply . i figured out my mistake as soon as i posted ...now fixed my mistake and got ac ..........thanx anywayz
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Mon Dec 12, 2005 11:40 am

Jan wrote:You can try the following input...

Input:

Code: Select all

3
a 0
b 01
c 10
00110001
0
Output:

Code: Select all

Case #1
abcab
Hope it works.
Accepted program gives :
Case #1
abcab
abcb
bcab
bcb

So, two points to note :
1. No code value has leading zero/s
2. Code value must be >0

predator
New poster
Posts: 3
Joined: Sun Jun 25, 2006 6:33 pm
Location: Bangladesh
Contact:

confused about the statement

Post by predator » Mon Jun 26, 2006 7:13 am

hi,
i am getting WA in this problem. i am confused about the statement saying that "A code may or may not be preceded by a 0 in the encrypted string". can any one plz tell me what this contraint means ?

my approach is : when i find a 0 in the enc string i try decrypting it including that zero and excluding the zero. i sort all the possible outcome and take the unique outcomes and then keep the first 100. i used memoization so i keep doing this in every step.

Code: Select all


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
#include<deque>
#include<string>
#include<cassert>
#include<algorithm>
#include<map>
#include<functional>
using namespace std;

#define SIZE 105
#define LIMIT 1000
#define INF 2000000000
#define EPS 1e-7

#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define ABS(a) ((a)>0 ? (a) : -(a))



long size;
char dic[27][SIZE];
vector<char> avail;
char input[SIZE];

vector<string> mem[SIZE];
bool mask[SIZE];



bool takeinput();
vector<int> match(int, char[],int );
vector<string> recur(int start);


int main()
{
	int i,kase=0;
	vector<string> res;

	while(takeinput())
	{
		memset(mask,0,sizeof mask);
		for(i=strlen(input);i>=0;i--)	mem[i].clear();

		mask[strlen(input)]=1;
		mem[strlen(input)].push_back("");

		res=recur(0);

		cout<<"Case #"<<++kase<<endl;
		for(i=0;i<res.size() && i<100;i++)
			cout<<res[i]<<endl;
		cout<<endl;

	}

	return 0;
}


vector<string> recur(int start)
{
	int i,j,k;
	vector<int> tm;
	vector<string> temp;
	vector<string>::iterator last;
	
	if(!mask[start])
	{	
		mask[start]=1;

		for(i=0;i<avail.size();i++)
		{
			tm=match(start,dic[avail[i]-'a'],0);
			
			for(j=0;j<tm.size();j++)
			{
				temp=recur(tm[j]);
			
				for(k=0;k<temp.size();k++)
				{
					mem[start].push_back(avail[i]+temp[k]);	
				}
				sort(mem[start].begin(),mem[start].end());
				
				last=unique(mem[start].begin(),mem[start].end());
				mem[start].erase(last,mem[start].end());

				if(mem[start].size()>LIMIT)
					mem[start].erase(mem[start].begin()+LIMIT,mem[start].end());
			}
		}
	}

	return mem[start];
}

vector<int> match(int start,char enc[],int index)
{
	vector<int> vec,temp;

	if(index==strlen(enc))
	{	
		vec.push_back(start);
		return vec;
	}

	if(start==strlen(input))
	{
		vec.clear();
		return vec;
	}

	if(input[start]==enc[index])
	{
		temp=match(start+1,enc,index+1);
		vec.insert(vec.end(),temp.begin(),temp.end());
	}
	if(input[start]=='0')
	{
		temp=match(start+1,enc,index);
		vec.insert(vec.end(),temp.begin(),temp.end());
	}

	return vec;
}

bool takeinput()
{
	long i;
	char real[10];

	cin>>size;
	if(size==0)
		return false;

	avail.resize(size);

	for(i=0;i<size;i++)
	{
		scanf("%s",&real);
		avail[i]=real[0];
		scanf(" %s",&dic[real[0]-'a']);
	}

	sort(avail.begin(),avail.end());

	cin>>input;

	return 1;
}

Post Reply

Return to “Volume 109 (10900-10999)”