解題區/解題區 - UVa

UVa 10123 - No Tipping

contents

  1. 1. Problem
  2. 2. Sample input
  3. 3. Possible Output for sample input
  4. 4. Solution

Problem

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.

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.

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.

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 n the number of packages on the board (n <= 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 n 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 n 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 Impossible. There is no solution if in the initial configuration the board is not balanced.

Sample input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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

Possible Output for sample input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

Solution

題目描述：

給定一個木板，有兩個支撐點位於 -1.5 和 1.5 上，現在還附加了許多物件在木板上，要如何依序將物件拿起，同時不會讓木板因為不平衡而倒塌。

題目解法：

如何才能算是不平衡？

對於左支持點失去平衡為－其左力矩大於右力矩，因此向左傾斜
對於右支持點失去平衡為－其右力矩大於左力矩，因此向右傾斜

因此，根據貪婪的想法，中間 [-1.5, 1.5] 之間的物件肯定是最後才移走 (移走將減少力矩，因為它們貢獻給左支撐點的右力矩和右支持點的左力矩)。

之後，窮舉其他沒辦法判定的物件，依照產生的力矩由小到大依序窮舉，每一次決策要拿走左方還是右方最小力矩的物件，考慮較大力矩物件是沒有意義的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
int L, W, N, M;
vector< pair<int, int> > LEFT, RIGHT, D;
int find_flag; 
pair<int, int> path[128], pick[128];
int check(int n) {
    double LL, LR, RL, RR;
    LL = LR = RL = RR = 0;
    LL = RR = (L/2.0 - 1.5) * (L/2.0 - 1.5) * W / (double)L / 2;
    LR = RL = (L/2.0 + 1.5) * (L/2.0 + 1.5) * W / (double)L / 2;
    for(int i = 0; i < M; i++) {
        if(pick[i].first < -1.5) {
            LL += fabs(pick[i].first - (-1.5)) * pick[i].second;
        } else {
            LR += fabs(pick[i].first - (-1.5)) * pick[i].second;
        }
        if(pick[i].first < 1.5) {
            RL += fabs(pick[i].first - (1.5)) * pick[i].second;
        } else {
            RR += fabs(pick[i].first - (1.5)) * pick[i].second;
        }
    }
    for(int i = 0; i <= n; i++) {
        if(path[i].first < -1.5) {
            LL += fabs(path[i].first - (-1.5)) * path[i].second;
        } else {
            LR += fabs(path[i].first - (-1.5)) * path[i].second;
        }
        if(path[i].first < 1.5) {
            RL += fabs(path[i].first - (1.5)) * path[i].second;
        } else {
            RR += fabs(path[i].first - (1.5)) * path[i].second;
        }
    }
    return LL <= LR && RR <= RL;
}
void dfs(int l, int r, int dep) {
    if(l == LEFT.size() && r == RIGHT.size()) {
        find_flag = 1;
        for(int i = dep-1; i >= 0; i--)
            printf("%d %d\n", path[i].first, path[i].second);		
        for(int i = 0; i < M; i++)
            printf("%d %d\n", pick[i].first, pick[i].second);
        return;
    }
    if(l < LEFT.size()) {
        path[dep] = D[LEFT[l].second];
        if(check(dep))
            dfs(l+1, r, dep+1);
        if(find_flag)	return;
    }
    if(r < RIGHT.size()) {
        path[dep] = D[RIGHT[r].second];
        if(check(dep))
            dfs(l, r+1, dep+1);
        if(find_flag)	return;
    }
}
int main() {
    int cases = 0, p, q;
    while(scanf("%d %d %d", &L, &W, &N) == 3 && L + W + N) {
        LEFT.clear(), RIGHT.clear(), D.clear();
        M = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d %d", &p, &q);
            D.push_back(make_pair(p, q));
            if(abs(p) < 1.5) {
                pick[M++] = make_pair(p, q);
                continue;
            }
            if(p < 0) {
                LEFT.push_back(make_pair((fabs(2*p) - 3) * q, i));
            } else {
                RIGHT.push_back(make_pair((fabs(2*p) - 3) * q, i));
            }
        }
        sort(LEFT.begin(), LEFT.end());
        sort(RIGHT.begin(), RIGHT.end());
        find_flag = 0;
        printf("Case %d:\n", ++cases);
        dfs(0, 0, 0);
        if(!find_flag)
            puts("Impossible");
    }	
    return 0;
}