10437 - Playing With Fraction

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

Moderator: Board moderators

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

10437 Playing with Fractions

Post by Whinii F. » Fri Feb 14, 2003 11:22 am

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
New poster
Posts: 45
Joined: Fri Oct 19, 2001 2:00 am
Contact:

Send me your code

Post by suman » Fri Feb 14, 2003 5:39 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Apr 16, 2003 7:45 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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Apr 16, 2003 9:49 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Apr 16, 2003 11:41 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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Apr 16, 2003 11:53 pm

Just got AC. For input '18|3' I wrote '18|3' in stead of '6' :oops: 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 :oops: :oops:

dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

10437 - Playing With Fraction

Post by dpitts » Thu Aug 26, 2004 9:21 am

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:(

Post by Moha » Wed Oct 12, 2005 3:30 pm

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

Post by Moha » Wed Oct 12, 2005 7:25 pm

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, :D, with special thanks little joey, for his binary code!

metaphysis
Learning poster
Posts: 92
Joined: Wed May 18, 2011 3:04 pm

Re: 10437 - Playing With Fraction

Post by metaphysis » Mon Jul 24, 2017 4:57 am

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

Post Reply

Return to “Volume 104 (10400-10499)”

Who is online

Users browsing this forum: No registered users and 1 guest