2013-06-28 09:13:10| 人氣1,579| 回應0 | 上一篇 | 下一篇

[UVA] 12636 - Disguised Giveaway

Output

For each case, print the case number and the input integers in ascending order, separated by a single space. If there are multiple solutions, print the one with the smallest first integer (after sorting), in case of tie, the one with the smallest second integer and so on. You can assume for the given input there will always be a possible solution.

Sample Input Output for Sample Input

10 12 16 30 48 40

10 20 8

Case 1: 2 5 6 8

Case 2: 2 4 5

Problemsetter: Jane Alam Jan, Special Thanks: Md. Mahbubul Hasan, Rujia Liu

題目解法：
類似於 10202 - Pairsumonious Numbers, 只是加法變成乘法。
已經知道前兩個最小乘積分別是 A[0]*A[1], A[0]*A[2], 但無法確定
A[1]*A[2] 與 A[0]*A[3] 誰大誰小, 因此這裡採用窮舉的方式,
藉此得到 A[0], A[1], A[2] 如此一開就可以找到全部的數字。

但是題目很容易 overflow, 注意一下範圍 between 2 and 10⁹
當答案超過時要特別忽略他, 否則會在後面計算的時候 overflow, 測資就是用這個卡人的。

#include <stdio.h>
#include <math.h>
#include <set>
#include <algorithm>
using namespace std;
long long gcd(long long x, long long y) {
    unsigned long long tmp;
    while(x%y)
        tmp = x, x = y, y = tmp%y;
    return y;
}
#define eps 1e-1
int sol(long long &x, long long a, long long b, long long c) {
    // x = sqrt(a*b/c)
    long long g;
    g = gcd(a, c), a /= g, c /= g;
    g = gcd(b, c), b /= g, c /= g;
    if(c != 1) return -1;
    a = a*b; // a < 10^18
    long long l = 1, r = 1000000000, m;
    while(l <= r) {
        m = (l+r)/2;
        if(m*m == a) {
            x = m;
            return 1;
        }
        if(m*m > a)
            r = m-1;
        else
            l = m+1;
    }
    return -1;
}
long long M[40005], A[205];
int main() {
    /*freopen("in.txt", "r+t", stdin);
   freopen("out2.txt", "w+t", stdout);*/
    int testcase, cases = 0;
    int n, m, i, j, k;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        m = n*(n-1)/2;
        multiset<unsigned long long> ori;
        for(i = 0; i < m; i++) {
            scanf("%lld", &M[i]);
            ori.insert(M[i]);
        }
        sort(M, M+m);
        int flag;
        printf("Case %d:", ++cases);
        for(i = 2; i < m; i++) {
            // A[0] * A[1] = M[0]
            // A[0] * A[2] = M[1]
            // A[1] * A[2] = M[i]
            flag = sol(A[0], M[1], M[0], M[i]);
            if(flag < 0)    continue;
            flag = sol(A[1], M[i], M[0], M[1]);
            if(flag < 0)    continue;
            flag = sol(A[2], M[1], M[i], M[0]);
            if(flag < 0)    continue;
            multiset<unsigned long long> R;
            multiset<unsigned long long>::iterator it;
            R = ori;// copy
            it = R.find(M[0]), R.erase(it);
            it = R.find(M[1]), R.erase(it);
            it = R.find(M[i]), R.erase(it);
            if(A[0] < 2 || A[1] < 2 || A[2] < 2)
                continue;
            if(A[1] <= A[0] || A[2] <= A[1])
                continue;
            for(j = 3; j < n; j++) {
                it = R.begin();
                if((*it)%A[0])
                    break;
                A[j] = (*it)/A[0];
                if(A[j] > 1000000000 || A[j] < 2)
                    break;
                if(A[j] <= A[j-1])
                    break;
                for(k = 0; k < j; k++) {
                    it = R.find(A[j]*A[k]);
                    if(it == R.end())
                        break;
                    R.erase(it);
                }
                if(k != j)// not found
                    break;
            }
            if(j == n) {// found
                for(j = 0; j < n; j++)
                    printf(" %lld", A[j]);
                puts("");
                break;
            }
        }
    }
    return 0;
}

我要檢舉

#12636#Disguised Giveaway

台長： Morris

您可能對以下文章有興趣

[UVA][正環][spfa] 10557 - XYZZY

[UVA][dp] 12030 - Help the Winners

[UVA][簡單多邊形面積] 10065 - Useless Tile Packers

[UVA] 598 - Bundling Newspapers

人氣(1,579) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][Easy] 10919 - Prerequisites
此分類上一篇:[UVA] 586 - Instant Complexity

回應(0)