## 10437 - Playing With Fraction

Moderator: Board moderators

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### 10437 Playing with Fractions

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.
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?

suman
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

### 10437 - Playing With Fraction

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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

### WA:(

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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

### I Got AC

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
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 10437 - Playing With Fraction

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