10312

bolster · Post by **bolster** » Mon Jul 01, 2002 11:40 pm

No definition of non-binary bracketing was given.

please clarify, thanks.

bolster

Picard · Post by **Picard** » Tue Jul 02, 2002 12:56 am

here is definition, but it's a spoiler too:
http://mathworld.wolfram.com/BinaryBracketing.html

(my short definition was wrong)

bolster · Post by **bolster** » Tue Jul 02, 2002 2:48 am

thanks =)

Ihor Bobak · Post by **Ihor Bobak** » Tue Jul 02, 2002 5:04 pm

Picard wrote:here is definition, but it's a spoiler too:
http://mathworld.wolfram.com/BinaryBracketing.html

in short: binary bracketing when maximum two 'x' stand next to each other. non-binary when it's not binary, so there is somewhere a 'xxx'.

Better definition: "the number of different ways in which a product of n different ordered factors can be calculated by pairs"

To author of the task:
Dear Shahriar, please, next time include the definition of the terms and don't make people surf the internet, since they would better spend this time to problem solving.

Best regards,
Ihor Bobak.

10153EN · Post by **10153EN** » Tue Jul 02, 2002 5:28 pm

Excuse me, the above definition still confused me. Could you explain more to me with the example in the problem description? I wanna know what's the difference between the first 6 bracketing and the last 5.

Thx in advance.

broderic · Post by **broderic** » Tue Jul 02, 2002 6:51 pm

a binary operation is one that accepts two arguments as input.
so +,-,*,/ are all binary operators. A binary bracketing is a bracketing
such that all operations are binary.

think of the x's as arguments to an operator. if we have xxxx, then
the operator is getting 4 arguments. however, if we put brackets like
this: (xx)(xx) then (xx) is binary (it accepts 2 arugments) and (xx)(xx) is binary since it recieves
two arugments, namely two (xx)'s. so (xx)(xx) is a binary bracketing.

some more examples: ((xx)x)x. this is binary since (xx) is binary, and
if we replace (xx) with y, then we have (yx)x. (yx) is obviously binary so replace it with z and we end up with zx. Thus, the whole thing is
a binary bracketing.

((xx)xx)x is NOT binary. To see this, let y=(xx). then we have (yxx)x, and yxx is not binary because it accepts 3 arguments.

There's a well known formula for calculating how many ways
(n+1) terms can be binary bracketed, which makes this problem a piece
of cake.

I hope this clears it up.

Broderick

madrazoman · Post by **madrazoman** » Thu Oct 31, 2002 5:20 am

please help me. i'm having WA

and i dont know if is beacuse of the data type im using. with a long long i got 42624971294485657 as output with 26 as input. is this right?
other with input 24 give 1416118615851221 with a double and 1416461675464871 with a long long.
thanks
[/cpp]

cytse · Post by **cytse** » Thu Oct 31, 2002 6:50 am

I used long long in my program.

BTW, it is strange that you get a correct answer to 24 with double

madrazoman · Post by **madrazoman** » Thu Oct 31, 2002 9:42 am

for input 1 and 2 output is 0, right?

cytse · Post by **cytse** » Thu Oct 31, 2002 5:09 pm

madrazoman · Post by **madrazoman** » Thu Oct 31, 2002 8:10 pm

thanks, but i still don't get it... would be better if i make the 0<n<=26 calculations on my own and just print them?
could any one write some correct output ? thanks

cytse · Post by **cytse** » Fri Nov 01, 2002 6:25 am

Well...It is a solution, but you can't find the numbers on your own, so at the end you still need to write a program

I don't want to post all output here, because everyone may simply get AC by hardcoding.

As mentioned before, the output to 24 is 1416118615851221. If you get this correct, you should have the correct formula.

sjn · Post by **sjn** » Sun Mar 16, 2003 11:37 pm

i also got WA several times and don't know why till now

my program for the input
24
25
26

is the following:
1416118615851221
7759443920290221
42620109348084205

am i right?
thx in advance

anupam · Post by **anupam** » Sat Jul 12, 2003 3:30 pm

i used the formula for catalon numbers and for total number of bracketing
that is the recurrence formula given in the mathworld. but got wa.
would anuone please tell the output of case 25 and 20??
plz.

shahriar_manzoor · Post by **shahriar_manzoor** » Sat Jul 12, 2003 4:14 pm

I thought example is the best form of definition. So I used example in my problem. Now I find that some people things the other way. Well! I cannot please everyone. For example if I give the definition of complete graph in my problem! An expert in graph theory will feel annoyed and vice versa for a novice in the same topic.

OJ Board

10312 - Expression Bracketing

10312 - Expression Bracketing

confused

Hmm