10437 - Playing With Fraction

[Whinii F.]

I've been tackling this problem with divide and conquer..

To describe with EBNF:

expression = term { addop term }.
term = factor { mulop factor }.
factor = "(" expression ")" | number.
addop = "+" | "-".
mulop = "*" | "/".

(I've been using 64 bit integers, so there shouldn't be any problem with integer range things.. right?)
I tried to handle negative numbers too. Will this make any problem? :'(

Are there any tricky cases or those sort of things? Or are there fractions like 1|2|3|4|5 ??

Some inputs and outputs:

1/5-1/2
-3|10
1/2/3/4/5/6/7*8*7*6*5*4*3*2*1
8
(3+1/2*6)+1/2
13|2
132/((3+1/2*6)+1/2-(3+1/2*6)-1/2)
INVALID
13/(1*2*3*4*5*6*0)
INVALID
1|2+-1|2
0
1|2--1|2
1

Which are obvious..

Any suggestions?

Thanks in advance.

[suman]

Dear Whinii F.
I have checked your input and output. Your last two input were invalid. Others are ok. However you may send your source to me to check. Send at udvranto@hotmail.com


- Suman

[little joey]

I'm struggling with this one too.
The description says:

Each line contains an expression. Arbitrary number of spaces may be present in the expression.

But I just confirmed that a line can contain more than one expression; at least the line contains more characters after one legal expression is read.
If this is so, how should we separate them?
The line can contain arbitrary spaces, so how should we interpret

Code: Select all

12  +23 45 - 15

As one expression '12+2345-15' or as two expressions '12+23' and '45-15'.
I take the description litteraly: one expression per line, remove all spaces before parsing. But keep getting WA.

[Adrian Kuegel]

Your interpretation is right, just remove all spaces before parsing. I just looked at my code, it seems there are also '\t' which you have to remove.

[little joey]

Thanks Adrian for looking into it.
My conclusion that there where more characters after a valid expression was premature; sorry for that.
I remove all characters other than the valid ones ['(',')','*','+','-','0'..'9','|'] from the input before sending it to the parser. I do 64 bit arithmetic (signed), reduce all fractions along the way, detect division by zero, write 'a' instead of 'a|1', etc. but still get WA.
Anything I overlooked?

[little joey]

Just got AC. For input '18|3' I wrote '18|3' in stead of '6' Only my math functions did fraction reduction...

One of the best problems in the set, I think. Although I got 10+ WAs, they where all my own stupidity

[dpitts]

I keep getting WA, but all my test cases see to work okay.

-bash-2.05b$ cat data

Code: Select all

1/2
18|3
18/3
4294967296|4294967295
4294967296|4294967295 / 16
4294967296|4294967295 * 1|16
4294967296|4294967295 - 1
(256*256/(256*256-3|3) - 6) + (3|4 * 4|3)
1|0
2|4 / 0
2|4 / (4 - 4)
2/4 * (1 / 0)

-bash-2.05b$ ./a.out < data

Code: Select all

1|2
6
6
4294967296|4294967295
268435456|4294967295
268435456|4294967295
1|4294967295
-262139|65535
INVALID
INVALID
INVALID
INVALID

Am I not expecting some odd case? Are negative fractions allowed as a result/intermediate result? are intermediate results larger than 32bit? is (3/(3|0))=0 or INVALID? Anything else I'm not considering in my input?
This type of problem annoys me. I think I have it down, but the judge disagrees.

[Moha]

I got WA in this problem, can anybody test these testcases:
input:

• 3|1/4
  3/(3*4)
  0|1
  1|12-2/24

output:

i use signed long long to store step by step result, should i use Huge number?

• 3|4
  1|4
  0
  0

[Moha]

At last, I got accepted in this problem.
the point is, when you want to calculate sum of addition or minus of 2 fraction, i calculate a/b+c/d=(a*d+c*b)/(b*d) but in problem testcase it may overflow, so you should write it as f=gcd(b,d) ==> (a*(d/f)+c*(b/f))/((d/f)*b).
it`s ok now!

but I don`t expect that, so I think it`s better to say something about this is problem statement. who knows, may be we should use Huge number!!

anyway, I got accepted in another parsing problem, , with special thanks little joey, for his binary code!

[metaphysis]

The test data of this problem seems not very strong, otherwise BigInteger should be used to get accepted.