964 - Custom Language
Moderator: Board moderators
964 - Custom Language
I'm quite stuked in this problem. I can't understand the specification well.
Here are few quetions:
1. Does the arithmetic operations cause an overflow with long long?
2. If there is an invalid inustruction (not defined instruction, too many args,
too long variable name ...), is it supposed to print "ABORTED"? Or if the
interpreter doesn't execute that inustruction, doesn't care?
3. Same quetion as 2 for invalid data in data section.
4. what is "something wrong happens"? I assumed like below.
- undefine instruction, too many args, too few args, too long variable name
- invalid data
- if the stack is empty with instruction POP, DUP, WRITE, JUMPPOS, JUMPZERO
- if the stack doesn't have more than 2 item with instruction ADD, SUB, DIV, MUL
- zero divide
- READ when no more inputs.
- if the variable has no associated value with insturction PUSH, JUMP(POS, ZERO)
5. Does the instruction JUMPPOS, JUMPZERO removes the top of the stack?
Answer of the quetions or some i/o helps me.
Thanks in advance.
----
Sory for my poor English.
Here are few quetions:
1. Does the arithmetic operations cause an overflow with long long?
2. If there is an invalid inustruction (not defined instruction, too many args,
too long variable name ...), is it supposed to print "ABORTED"? Or if the
interpreter doesn't execute that inustruction, doesn't care?
3. Same quetion as 2 for invalid data in data section.
4. what is "something wrong happens"? I assumed like below.
- undefine instruction, too many args, too few args, too long variable name
- invalid data
- if the stack is empty with instruction POP, DUP, WRITE, JUMPPOS, JUMPZERO
- if the stack doesn't have more than 2 item with instruction ADD, SUB, DIV, MUL
- zero divide
- READ when no more inputs.
- if the variable has no associated value with insturction PUSH, JUMP(POS, ZERO)
5. Does the instruction JUMPPOS, JUMPZERO removes the top of the stack?
Answer of the quetions or some i/o helps me.
Thanks in advance.
----
Sory for my poor English.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
I had to go by the same description when writing the testset, and had the same type of questions as you have. So I took the description as literally as possible, making sure the input was correct (as should be with any testset), and clarifying the interpretation choices in the examples.
Since the input consists of a code section and a data section, the following conclusions can be made:
- The code section consists of a program, and a program is defined as a list of instructions, and an instruction is defined as being one from the list given. So to be valid, the code section should not contain instructions not defined by the list. In other words, a parser should not fail when parsing the code section. This answers your question 2, and part of question 4.
- The data section consists of a list of integers. This answers your question 3, and part of question 4.
There is some vagueness in the description about the concepts 'integer' and 'variable'. For 'integer' I took the 'normal' interpretation as being a 32-bit signed number, but took care that the input would not cause arithmetic overflow/underflow when the program was executed correctly (NB: division by zero is not arthimetic overflow). This answers your question 1.
Nothing is said in the description about declaring and initialising variables, so I made what I think is the most sensible choise: a variable doesn't exist before it's assigned a value, an attempt to read a variable before it is initialised, causes and error. I illustrated that in the 4th and 5th sample case. You should note that only the interpreter can decide wether a variable is initialised or not, not the parser because the parser doesn't know the flow of events.
There are two ways a program can end:
- Normally: an implicit or explicit jump to an address outside the range of the list of instructions. In that case the program should print a list of all output generated by WRITE instructions. By implicit I mean the jump to the next instruction after successfully executing an instruction or not taking a conditional jump.
- Abnormally: 'something wrong happens'. It should then only print the word 'ABORTED', as in the second sample case. As what that 'something wrong' consists of, the problemsetter leaves us in the dark, so we're left with common sense. I think your list in question 4, apart for the first two items, sums it up quite nicely.
About your question 5: I think the last sentence of the description answers that and the 3rd sample case illustrates it.
There is one issue I didn't cover in the samples: not all instructions are atomic.
In most instructions this makes no difference for the flow of events, but for the conditional jumps it does. So let me add the following I/O to illustrate my choices:
Input
OutputAn equally valid choice would have led to printing 'ABORTED' in this case, but I chose the former.
I hope this clarifies matters, if not please say so.
Since the input consists of a code section and a data section, the following conclusions can be made:
- The code section consists of a program, and a program is defined as a list of instructions, and an instruction is defined as being one from the list given. So to be valid, the code section should not contain instructions not defined by the list. In other words, a parser should not fail when parsing the code section. This answers your question 2, and part of question 4.
- The data section consists of a list of integers. This answers your question 3, and part of question 4.
There is some vagueness in the description about the concepts 'integer' and 'variable'. For 'integer' I took the 'normal' interpretation as being a 32-bit signed number, but took care that the input would not cause arithmetic overflow/underflow when the program was executed correctly (NB: division by zero is not arthimetic overflow). This answers your question 1.
Nothing is said in the description about declaring and initialising variables, so I made what I think is the most sensible choise: a variable doesn't exist before it's assigned a value, an attempt to read a variable before it is initialised, causes and error. I illustrated that in the 4th and 5th sample case. You should note that only the interpreter can decide wether a variable is initialised or not, not the parser because the parser doesn't know the flow of events.
There are two ways a program can end:
- Normally: an implicit or explicit jump to an address outside the range of the list of instructions. In that case the program should print a list of all output generated by WRITE instructions. By implicit I mean the jump to the next instruction after successfully executing an instruction or not taking a conditional jump.
- Abnormally: 'something wrong happens'. It should then only print the word 'ABORTED', as in the second sample case. As what that 'something wrong' consists of, the problemsetter leaves us in the dark, so we're left with common sense. I think your list in question 4, apart for the first two items, sums it up quite nicely.
About your question 5: I think the last sentence of the description answers that and the 3rd sample case illustrates it.
There is one issue I didn't cover in the samples: not all instructions are atomic.
In most instructions this makes no difference for the flow of events, but for the conditional jumps it does. So let me add the following I/O to illustrate my choices:
Input
Code: Select all
PUSH 1
JUMPZERO addr
PUSH 12345
WRITE
#
#
Code: Select all
12345
#
I hope this clarifies matters, if not please say so.
Judge data: bug report.
After removing checking variable syntax I receive AC
So, perhaps judge data contains illegal variables like : "a0","A", etc.
Code: Select all
bool check_token(const char *p)
{
//A variable s is a string in [a-z][1-9a-z]*
if (!islower(p[0])) return false;
for(int i=1;p[i];i++)
{
if (!islower(p[i]) && !isdigit(p[i])) return false;
if (p[i] == '0') return false;
}
return true;
}
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Can anyone tell me whats the output of the folowing input set
Input:
Thanks in advance.
Input:
Code: Select all
PUSH 12345
POP x
PUSH 0
PUSH 1
PUSH 0
PUSH 0
POP abdvdhsjashgdhgasdhgajdgashdgjasghdajdgh
JUMPZERO 10
JUMP 9
PUSH 1
WRITE
JUMPPOS 5
#
#
PUSH 12345
POP x
PUSH 1
PUSH 0
PUSH 0
POP abdvdhsjashgdhgasdhgajdgashdgjasghdajdgh
JUMPZERO 9
JUMP 8
PUSH 1
WRITE
JUMPPOS 4
#
#
PUSH 1
JUMPZERO abcde
PUSH 1
WRITE
#
#
PUSH 1
JUMPZERO abcde
PUSH 1
WRITE
WRITE
#
#
READ
#
#
PUSH 0
JUMPZERO abcde
PUSH 1
WRITE
#
#
JUMPZERO 1
#
#
JUMPPOS 1
#
#
Ami ekhono shopno dekhi...
HomePage
HomePage
For you input, my code ouput below
Code: Select all
1
1
#
ABORTED
#
1
#
ABORTED
#
ABORTED
#
ABORTED
#
ABORTED
#
ABORTED
#
Thanks rio. My code produces same output. But I am still getting TLE. I have to check it again.
Ami ekhono shopno dekhi...
HomePage
HomePage
I have tried all day long, but cant figure out my error
. I m still getting TLE. Here is my code. Its quite long. Sorry for posting the code. Hope anybody helps.
Thanks in advance.
![:(](./images/smilies/icon_frown.gif)
Code: Select all
Removed...
Last edited by Jan on Thu Nov 02, 2006 7:07 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Hmm, there are some errors, and the code is too slow. I think the slowness is due to your juggling strings upto the lowest level; try tokenisation instead.
One error is that you can't handle negative arguments:Should print '-6', not 'ABORTED'. As I said above, I took 'interger' as meaning signed 32-bit (the type 'int' in C, 'integer' in Pascal) and the sample input contains a negative number.
There's another error, but I'm not going to add too many spoilers
.
One error is that you can't handle negative arguments:
Code: Select all
PUSH -7
PUSH 1
ADD
WRITE
#
#
There's another error, but I'm not going to add too many spoilers
![:)](./images/smilies/icon_smile.gif)
Thanks Joachim. I have to save the input in a different way. And yes, the isdigit() function should be rewritten.
. Thanks again.
I think you leave me in dark. But thats the best way to helplittle joey wrote:There's another error, but I'm not going to add too many spoilers.
![:)](./images/smilies/icon_smile.gif)
Ami ekhono shopno dekhi...
HomePage
HomePage
I have changed my code. But now I m getting WA.
. This problem made me mad.
Hope anyone helps. Thanks in advance.
![:cry:](./images/smilies/icon_cry.gif)
Code: Select all
Removed... Checking
Last edited by Jan on Thu Nov 02, 2006 10:11 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Thank you very^(inf) much Joachim. I have got it Accepted.
. Finally, hard time passed.
![:D](./images/smilies/icon_biggrin.gif)
Ami ekhono shopno dekhi...
HomePage
HomePage