시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Alabama Mobiles Inc. designs and manufactures mobiles, lightweight ”kinetic sculptures” consisting of bars hanging from strings. From each end of the bar hangs a string supporting either a small decorative object of some kind or another, smaller mobile. A well-designed mobile must have the weights of all the decorative items balanced, so that each bar in the mobile will naturally tend to hang horizontally. A bar can be balanced even if the weights hanging from either side are not equal. The string must be tied to the bar si that it divides the bar into two lengths L1 and L2, such that

L1 ∗ W1 = L2 ∗ W2

where W1 is the total weight hanging from the L1 side of the bar and W2 is the total length hanging from the other side.

Write a program to read a partial design for a new mobile and determine if it can be balanced and if, once balanced, the elements will swing freely without bumping or entangling with one another.

Each mobile will be described as a collection of bars and decorative objects. You will be given the lengths of the bars, the weights of all objects, and information on how the bars and objects are connected to one another. You may assume that the bars are made of a lightweight material so that their weight and the weight of the connecting strings are negligible compared to the weights of the decorative objects.

Every mobile will have at least one bar.

입력

  • The input consists of a number of mobile design specifications. Each mobile design is given as a parenthesized expression. These expressions are composed of two basic forms:

1. ( D w )
describes a decorative object. w is a floating point number giving the weight of the object.

2. ( B # L m1 m2
describes a bar.

  • # is an integer that constitutes a unique identifier for each bar. These integers will be assigned densely so that a mobile with a total of k bars will use the numbers 1 . . . k as identifiers. The order in which these identifiers appear within a total expression is arbitrary.
  • L is a floating point number indicating the length of the bar.
  • m1 and m2 are two parenthesized expressions describing the portion of the mobile hanging from each end of this bar.

In the above two forms, wherever a space is shown between the components of each form, the actual input may contain 1 or more spaces and/or line terminators. An exception to this rule is that, to either side of a ’(’ or ’)’ in these forms, the input may contain zero or more spaces and/or line terminators.

Every mobile will contain at least one bar.
End of input is indicated by a line containing only: ()

출력

For each mobile specification, the program should print one line of output for each bar, in order by the object number of the bar. Each line will have the form

Bar N must be tied L from one end.

where N is the identifying number of the bar and where L is the smaller of the two lengths L1 and L2 as described above and is printed to one decimal place precision.

예제 입력

(B 2 4.0
  (D 1.0 )
  (B 1 2.0  (D 1.0 )  (D 2.0 )))
()

예제 출력

Bar 1 must be tied 0.7 from one end.
Bar 2 must be tied 1.0 from one end.

힌트