10950 - Bad Code

[TISARKER]

I am getting wrong answer .
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.

[polone]

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

[SRX]

hi
my output is
aaa

[Jan]

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.

[polone]

Sorry I misunderstanding the problem...

[polone]

deleted:)

[danielrocha]

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

[Emilio]

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.

[little joey]

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

[danielrocha]

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.

[Riyad]

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

Code: Select all

code deleted after ac

[Emilio]

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.

[Riyad]

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

[L I M O N]

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]

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;
}