11203 - Can you decide it for ME?

[andmej]

Hello all, nice people:

I don't know why I am getting wrong answer at this problem.

Here's the input i'm trying:

Code: Select all

49
??M?E???
xM?Ex?
??M??E????
M?E?
??m?e???
?M?E??
12M12E????
ME
M?E
?M?E?
?ME?
ME?
???ME???
???M?E????
??????????M?E???????????
??????????M?E??????????
????????????????????M?E?????????????????????
????????????????????M?E??????????????????????
?????????????????????M?E???????????????????????
??????????????????????M?E????????????????????????
?M?E??M?E??
?M?E?M
??M??E???
??M??E????
??M???E???
??M???E????
?M????E?????
M????E?????
?M??E???
?M???E????
?M????E?????
?M?????E??????
?M??????E???????
?M???????E????????
?M????????E?????????
?M?????????E??????????
?M??????????E???????????
?M???????????E????????????
?M????????????E?????????????
?M?????????????E??????????????
?M??????????????E???????????????
?M???????????????E????????????????
?M????????????????E?????????????????
?M?????????????????E??????????????????
?M??????????????????E???????????????????
?M???????????????????E????????????????????
?M????????????????????E?????????????????????
?M?????????????????????E??????????????????????
?M??????????????????????E???????????????????????

And the output from my program:

Code: Select all

theorem
no-theorem
theorem
no-theorem
no-theorem
theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
theorem
theorem
no-theorem
theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
theorem
no-theorem
no-theorem
theorem
no-theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem

Can somebody with an AC code please check this answers?
Does somebody have some extra critical input?

If you wan't I can post my code, but basically what I am doing is as follows:

1. Read the line

2. If the line contains a character different to M, E, or ? then output no-theorem and read next line

3. Extract x, y and z (as denoted in the problem: xMyEz) from the read string

4. If any one of these equals "" or contain a character different from ? then output no-theorem and read next line

5. If the delimiter between x and y is different from M or the delimiter between y and z is different from E, output no-theorem and read next line

6. If the length of y is greater than 1, then delete from y its last character and delete from z its last character until the length of y equals 1 ("un-theoremize").

7. If the length of x + 1 equals z, then it is an axiom, output theorem and read next line; else it is not valid, output no-theorem and read next line.

I alredy checked if the input method was correct and it seems like it is.

Any suggestion?

Thanks a lot for your help.

By the way, i'm sorry to post this problem at the CXI Volume's forum, but CXII Volume's forum is still not available.

[rio]

Your output is same as my AC code's.
Your alogrithm seems to be right (Actually, step 6, 7 could be done more simply).

Silly bug may be in your code.

[DP]

There can be M & E more than 1.

[andmej]

Thanks for your answers.

Your alogrithm seems to be right (Actually, step 6, 7 could be done more simply).

How?

There can be M & E more than 1.

What do you mean with this?

Do you mean that M and E can appear in the string more than once? If that's what you mean, then they wouldn't be correct theorems, for instance, the input:

Code: Select all

10
?MM?EE??
?M?E???M?E??
ME?ME?ME?
??M??E????
??M??E?????
??M??E????M
??M??E???E??M?E??
?M?E?M
?M?E?E
?M?E??

produces this output:

Code: Select all

no-theorem
no-theorem
no-theorem
theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
theorem

[sohel]

STEP 6 & 7 ::

if( x + y == z ) yes;
else no;

[andmej]

STEP 6 & 7 ::

if( x + y == z ) yes;
else no;

Thanks.

I'm using this approach now but still can't get accepted. I'm beginning to beleive there is some sort of special case that i'm not considering. I'm going a little desperate now so I will post my Pascal code; Just in case some of you people would like to check it:

Code: Select all

program problem11203 (input, output);

begin
writeLn('Finally got accepted. Nice problem.');
end.

Sorry for being so newbish

Edit:

Anyone?

Some extra critical input?

Any idea?

Can you help me?

Thanks!

[abdullah<cse du>]

Hi,

I have just got accepted the program. My procedure is:

1. Cheack for any invalid letters in the string (except '?' ,'M', 'E').
2. If number of 'M' or number of 'E' is more than one than invalid.
3. count '?' before 'M' (x), before 'E' (y)and than to the end of the string(z).
4. If any count is zero than invalid.
5. If x+y=z than valid.

I think this will help you.

ABDULLAH.

[Mushfiqur Rahman]

Dear, andmej
I saw your approach but didn't found anyting wrong. Sometimes we face this problem, theres no error in the code and algorithm but judge giving WA.
In this circumstances we should re code the problem without opening the existing code.
If it fail then should leave it for few days. After some days should take the problem as a new problem and try to solve it without the help of previous code and approach.

[tobby]

Any idea?

Can you help me?

Thanks!

Hello. I think your code has some really really small mistakes. Look at this line:

Code: Select all

if (s[1] <> 'M') then //if next char is not an M 

What if s is an empty string? What do you think will happen?

[andmej]

Any idea?

Can you help me?

Thanks!

Hello. I think your code has some really really small mistakes. Look at this line:

Code: Select all

if (s[1] <> 'M') then //if next char is not an M 

What if s is an empty string? What do you think will happen?

I think in that case a runtime error would produce, although that code got WA and no RE

Or maybe it just exists from the function "isTheorem" and returns true, wich could be the correct explanation to WA

Begin of Edit:

I think that was exactly the problem, because of this:

I had several very unpleasant experiences with Runtime Errors (RE) being reported as Wrong Answer (WA).

Reason for those is mentioned in post about 'submitting Pascal'. It turns out that FPC does not emit error signal (at least not under Linux), so if RE occurs your program either just abort, leaving your result output unfinished (and thus producing WA), or it write few error strings and then abort, which again result in WA since those error strings were not expected in output.

(More here: http://online-judge.uva.es/board/viewtopic.php?t=12303)

Runtime errors are reported as WA in Pascal

End of Edit.

Anyway, I will remove this code because alredy got accepted.

Dear, andmej
I saw your approach but didn't found anyting wrong. Sometimes we face this problem, theres no error in the code and algorithm but judge giving WA.
In this circumstances we should re code the problem without opening the existing code.
If it fail then should leave it for few days. After some days should take the problem as a new problem and try to solve it without the help of previous code and approach.

I did what you said and finally got accepted!

I was able to write shorter and clearer code on the second try. My new program was about 30 lines shorter than the old one. Thanks for the advice Musfiqur.

Thanks also to Abdullah for posting his algorithm.

[SARKAR]

can u plzzzzzzzzzzz telll me y
?M?E?
is not a theorem




10 case of ur 49 cases long input





sorry i misunderstood the problem
i got it now[/b]

[Freyr]

Hmm, I've run all the test cases I can think off, and I'm not exactly sure why this keeps getting WA.

Anyone have any test data that can trip this program up?

Code: Select all

AC, thanks!

Thanks muchly!

[rio]

Try this.

Code: Select all

1
?E?E??

----
Rio

[andmej]

Changing line 18 for

Code: Select all

            if((line[i] == 'E' && ef) || (line[i] == 'M' && !ef)){ 

should do the job.

Please remove your code after this to not spoil the problem to others.

[Freyr]

Ah, of course! Well, I feel like an idiot now, haha. Thanks guys