2014-05-05

UVa 10089 - Repackaging

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

儘管如此世界依舊美麗 (Still world is beautiful それでもせかいはうつくしい插曲) ，比預期中的還要好看，可能是人物屬性的關係讓我欲罷不能啊！順帶附了劇中歌曲，詳細請等待 OST，

Problem

Coffee cups of three different sizes (identified as size 1, size 2 and size 3 cups) are produced in factories under ACM (Association of Cup Makers) and are sold in various packages. Each type of package is identified by three positive integers (S1, S2, S3) where Si (1 <= i <= 3) denotes the number of size i cups included in the package. There is no package with S1 = S2 = S3.

But recently it has been discovered that there is a great demand for packages containing equal number cups of all three sizes. So, as an emergency step to meet the demand ACM has decided to unpack the cups from some of the packages stored in its (unlimited) stock of unsold products and repack them in packages having equal number of cups of all three sizes. For example, suppose ACM has the following four types of packages in its stock: (1, 2, 3), (1, 11, 5), (9, 4, 3) and (2, 3, 2). So, one can unpack three (1, 2, 3) packages, one (9, 4, 3) package and two (2, 3, 2) packages and repack the cups to produce sixteen (1, 1, 1) packages. One can even produce eight (2, 2, 2) packages or four (4, 4, 4) packages or two (8, 8, 8) packages or one (16, 16, 16) package or even different combination of packages each containing equal number of size 1, size 2 and size 3 cups. Note that all the unpacked cups are used to produce the new packages, i.e., no unpacked cup is wasted.

ACM has hired you to write a program that will decide whether it is possible to produce packages containing equal number of all three types of cups using all the cups that can be found by unpacking any combination of existing packages in the stock.

Input

The input may contain multiple test cases. Each test case begins with a line containing an integer N (3 <= N <= 1000) indicating the number of different types of packages that can be found in the stock. Each of the next N lines contains three positive integers denoting respectively the number of size 1, size 2 and size 3 cups in a package. No two packages in a test case will have the same specification.

A test case containing a zero for N in the first line terminates the input.

Output

For each test case in the input print a line containing “Yes” if packages can be produced as desired, print “No” otherwise.

Sample Input

Sample Output

1
2

Yes
No

Solution

題目描述：

咖啡杯有三種不同大小，出售的時候每一包三者都有不同個數，表示成 (S1, S2, S3) = (小, 中, 大)。

現在要將其重新包裝，每一種包假設有無限個數，問有沒有拆包的方式，滿足

x1 * (a1, b1, c1) + ... + xn * (an, bn, cn) = (k, k, k)

其中 x[i] >= 0 的非負整數, k 為非負整數，也就是重新包裝後要產生 k 個 (1, 1, 1)，以方便出售。

題目解法：

整數線性規劃就別來了，畢竟連 k 都沒有確定，解方程也不曉得解集合是否符合條件。

最後，重新考量 (S1, S2, S3)，如果以 S1 為基準，則產生 (S2 - S1, S3 - S1) 的向量。(因為最後還是要跟 S1 的總個數去計算，利用相對數量方式去降維。)，轉換原本的滿足方程

x1 * (y1, z1) + ... + xn * (yn, zn) = (0, 0)

如果兩個二維向量 (a, b) 和 (c, d)，對於任意 p (a, b) + q (c, d) 的結果可以產生兩個向量間任意角度(<= 180 deg)的向量 (不考慮向量長度，p, q 是非負整數)。

明白了上述條件後，將所有包分配至以原點拉出的向量，只要能產生兩個反向向量就可以相消找到 (0, 0) 向量。相消的條件很簡單，使用極角排序，相鄰兩個角度差全小於 pi 即有存在相消情況。

#include <stdio.h> 
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
    int n, S1, S2, S3;
    const double pi = acos(-1);
    while(scanf("%d", &n) == 1 && n) {
        double A[1024];
        for(int i = 0; i < n; i++) {
            scanf("%d %d %d", &S1, &S2, &S3);
            A[i] = atan2(S2 - S1, S3 - S1);
        }
        sort(A, A + n);
        double gap = 0;
        for(int i = 1; i < n; i++) {
            gap = max(gap, A[i] - A[i-1]);
        }
        gap = max(gap, 2 * pi - (A[n-1] - A[0]));
        puts(gap > pi ? "No" : "Yes");
    }
    return 0;
}

Morris' Blog