325 - Identifying Legal Pascal Real Constants

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

Moderator: Board moderators

Archangel
New poster
Posts: 29
Joined: Wed Jun 26, 2002 9:00 am

325 - Identifying Legal Pascal Real Constants

Post by Archangel » Wed Jul 24, 2002 10:57 pm

Does anybody have any idea of tricky input ?? :cry: I got so many times wrong answer...><

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Sun Aug 18, 2002 1:13 pm

me too :(
anyway, is 0e-0 legal or illegal?

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

325 DFA? WHY WA?

Post by obayashi » Tue Sep 17, 2002 8:03 am

It's just a simple DFA problem but the judge gave me WA.
Please help me.

Code: Select all

#include <iostream>
using namespace std;
char str[1000];
int trans[8][4] = 
{
	{1,2,9,9},
	{9,2,9,9},
	{9,2,3,5},
	{9,4,9,9},
	{9,4,9,5},
	{6,7,9,9},
	{9,7,9,9},
	{9,7,9,9}
};
int getMap (char c) {
	switch (c)
	{
		case '+':
		case '-':
			return 0;
			break;
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			return 1;
			break;
		case '.':
			return 2;
			break;
		case 'e':
		case 'E':
			return 3;
			break;
		default:
			return 4;
			break;
	}
}
int check ()
{
	int len = strlen(str);
	int state = 0;
	int i,j;
	char *p = str;
	for (i=len-1;i>=0;i--)
		if (str[i]!=' ')
		{
			str[i+1] = '\0';
			break;
		}
	while (*p==' ') p++;
	cout<<p;
	for (;*p;p++)
	{
		j = getMap(*p);
		state = trans[state][j];
		if (state==9) return 0;
	}
	return (state==2 || state==4 || state==7);
}
int main ()
{
	while (1)
	{
		cin.getline(str,999);
		if (str[0]=='*') break;
		if (check())
		{
			cout<<" is legal."<<endl;
		} else
		{
			cout<<" is illegal."<<endl;
		}
		
	}
	return 0;
}
Time makes a fool of memory
And yet my memories still shine

Jorge Pinto
New poster
Posts: 11
Joined: Wed Jan 09, 2002 2:00 am
Location: Portugal

Post by Jorge Pinto » Thu Oct 10, 2002 6:10 pm

My accepted solution gives this output on these tests:

Input:
1E1
1e1
1E
1EE1
1 E1
.1E1
1E.1
1E1.1
++1E1
1E--1
1.1.1E1
abcd
1
1.1
0e-0
*

Output:
1E1 is legal.
1e1 is legal.
1E is illegal.
1EE1 is illegal.
1 E1 is illegal.
.1E1 is illegal.
1E.1 is illegal.
1E1.1 is illegal.
++1E1 is illegal.
1E--1 is illegal.
1.1.1E1 is illegal.
abcd is illegal.
1 is illegal.
1.1 is legal.
0e-0 is legal.

Hope it helps

Jorge Pinto

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Sat Oct 12, 2002 7:43 am

thank u!!!
i found where the problem lies and fixed it.

"1" is not a real constant...
Time makes a fool of memory
And yet my memories still shine

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

325 legal constant

Post by deddy one » Sat Jan 04, 2003 5:11 am

what is the tricky input in this problem???

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Mon Jan 06, 2003 6:55 am

Before, I get Accepted on this problem, I got frustated on WA. Since there are so many tricky cases on this problem, you must be very careful.
I think the followings will help you :
1. No any other valid character are allowed (e.g : a,b,c,d,...)
2. Using more than 1 dot before e/E is illegal (e.g: 1.1.1e1 is illegal)
3. 0e-0 is legal
4. An integer value is illegal (e.g: 9999 is illegal)
5. The exponent should be in integer
6. And so on.

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Mon Jan 06, 2003 8:30 am

thx angga
I guess I failed on your first rule,

one more thing :
"e" can only appear 1 time right???
just like dot.

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Mon Jan 06, 2003 9:24 am

another WA again and again
I almost give up already in this one

could anyone give me a really2 good tricky input
behind this
or maybe send me his exe so I can double check
everything again

I've tried almost every test case I could think of and
the result always WA over and over again :cry:

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Jan 06, 2003 10:09 am

Try this method:

only same states are allowed, also create biggest figure of good constant, it is: x[.(x)+][{E|e}(x)+]
where (x)+ means one or more digit
[x] means optional part of expression
{x|y} means one and exactly one of specified in brackets values

create a graph of all possible states of this expression -> it's quite small (below 20 states) and mark states which are correct as end states. implement finite state machine and run it :))))

I did it in this way and got accepted first time - very important are boundary conditions - unexcepted characters in input and so on ...

Best regards
Dominik

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Mon Jan 06, 2003 1:03 pm

ok, I'll try to code it again


thx Dominik,
but I still
really needed the bad tricky input cases.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Jan 06, 2003 3:01 pm

I'ii try to send it to you (on this page) tomorrow (If I will be able to find it on my hard disk ;-) ). Try all correct / incorrect strings and remember that, you must cut leading and trialing spaces, tabs and so on, but not in the middle of examined string :)

Good luck
Dominik

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Mon Jan 06, 2003 6:43 pm

well, ummm
actually in my code I didn't just cut out
the leading or trailing spaces, but
it cuts out all the spaces within the input line

that's the first thing my code do after
reading the input

is it wrong??

andrew10
New poster
Posts: 7
Joined: Wed Jan 08, 2003 10:18 am
Location: Indonesia

Post by andrew10 » Wed Jan 08, 2003 10:42 am

Would you like to show the accepted program for me please?
I really need your help for this program in C Language.

Thanks

andrew10
New poster
Posts: 7
Joined: Wed Jan 08, 2003 10:18 am
Location: Indonesia

Post by andrew10 » Wed Jan 08, 2003 10:44 am

Would you like to show the accepted program for me please?
I really need your help for this program in C Language.

Thanks

Post Reply

Return to “Volume 3 (300-399)”