[UVA] 12636 - Disguised Giveaway
|
J |
Disguised Giveaway Input: Standard Input Output: Standard Output |
|
Well, I was planning to set a problem for beginners, that is: given n distinct integers each between 2 and 109, find the multiplication of all pairs. For example, n = 4 and the integers are 2, 5, 8 and 6, then the result would be 10 12 16 30 48 40. As the results can be printed in any order so, I wrote a special judge for this problem.
But it was a long time ago. Now I want to finish this problem and found that I only have the answer file of the problem. The input file is missing. All you have to do is to generate the input file from the answer file.
Input
Input starts with an integer T (T ≤ 25), denoting the number of test cases.
Each case starts with an integer n (3 ≤ n ≤ 200). The next line contains n*(n-1)/2 integers showing the all pair multiplications.
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
|
2 4 10 12 16 30 48 40 3 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 109
當答案超過時要特別忽略他, 否則會在後面計算的時候 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;
}