?? problem - no tipping.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0044)http://plg.uwaterloo.ca/~acm00/010602/A.html -->
<HTML><HEAD><TITLE>Problem - No Tipping</TITLE>
<META http-equiv=Content-Type content="text/html; charset=GB18030">
<META content="MSHTML 6.00.2900.2963" name=GENERATOR></HEAD>
<BODY>
<H2>Problem A - No Tipping</H2>As Archimedes famously observed, if you put an
object on a lever arm, it will exert a twisting force around the lever's
fulcrum. This twisting is called torque and is equal to the object's weight
multiplied by its distance from the fulcrum (the angle of the lever also comes
in, but that does not concern us here). If the object is to the left of the
fulcrum, the direction of the torque is counterclockwise; if the object is to
the right, the direction is clockwise. To compute the torque around a support,
simply sum all the torques of the individual objects on the lever.
<P>The challenge is to keep the lever balanced while adjusting the objects on
it. Assume you have a straight, evenly weighted board, 20 meters long and
weighing three kilograms. The middle of the board is the center of mass, and we
will call that position 0. So the possible positions on the board range from -10
(the left end) to +10 (the right end). The board is supported at positions -1.5
and +1.5 by two equal fulcrums, both two meters tall and standing on a flat
floor. On the board are six packages, at positions -8, -4, -3, 2, 5 and 8,
having weights of 4, 10, 10, 4, 7 and 8 kilograms, respectively as in the
picture below.
<CENTER>
<P><IMG src="Problem - No Tipping.files/fulcrum.gif" align=center>
<P></CENTER>Your job is to remove the packages one at a time in such a way that
the board rests on both supports without tipping. The board would tip if the net
torque around the left fulcrum (resulting from the weights of the packages and
the board itself) were counterclockwise or if the net torque around the right
fulcrum were clockwise. A possible solution to this problem is: first remove the
package at position -4, then the package at 8, then -8, then 5, then -3 and
finally 2.
<P>You are to write a program which solves problems like the one described
above. The input contains multiple cases. Each case starts with three integers:
the length of the board (in meters, at least 3), the weight of the board (in
kilograms) and <EM>n</EM> the number of packages on the board (<EM>n</EM> <=
20). The board is supported at positions -1.5 and +1.5 by two equal fulcrums,
both two meters tall and standing on a flat floor. The following <EM>n</EM>
lines contain two integers each: the position of a package on board (in meters
measured from the center, negative means to the left) and the weight of the
package (in kilograms). A line containing three 0's ends the input. For each
case you are to output the number of the case in the format shown below and then
<EM>n</EM> lines each containing 2 integers, the position of a package and its
weight, in an order in which the packages can be removed without causing the
board to tip. If there is no solution for a case, output a single line
<TT>Impossible</TT>. There is no solution if in the initial configuration the
board is not balanced.
<H3>Sample input</H3><PRE>20 3 6
-8 4
-4 10
-3 10
2 4
5 7
8 8
20 3 15
1 10
8 5
-6 8
5 9
-8 4
8 10
-3 10
-4 5
2 9
-2 2
3 3
-3 2
5 1
-6 1
2 5
30 10 2
-8 100
9 91
0 0 0
<PRE>
<H3>Possible Output for sample input</H3>
<PRE>Case 1:
-4 10
8 8
-8 4
5 7
-3 10
2 4
Case 2:
1 10
8 5
-6 8
5 9
-8 4
8 10
-3 10
-4 5
2 9
-2 2
3 3
-3 2
5 1
-6 1
2 5
Case 3:
Impossible
</PRE>
</PRE></PRE></BODY></HTML>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -