// UVa 11342 - Three-square #include <iostream> #include <string.h> #include <vector> using namespace std; #define MaxN 50000 int main() { int T[4][MaxN + 1]; memset(T, 127, sizeof(T)); vector<int> v1, v2; int oo = T[0][0]; for (int i = 0; i * i <= MaxN; i++) { T[1][i * i] = i; v1.push_back(i * i); } for (int j = 0; j < v1.size(); j++) { int f = v1[j]; for (int i = 0; i * i + f <= MaxN; i++) if (T[2][i * i + f] == oo) { T[2][i * i + f] = i; v2.push_back(i * i + f); } } for (int j = 0; j < v2.size(); j++) { int f = v2[j]; for (int i = 0; i * i + f <= MaxN; i++) if (T[3][i * i + f] == oo) T[3][i * i + f] = i; } int cases; for (cin >> cases; cases; cases--) { int n; cin >> n; if (T[3][n] == oo) cout << "-1" << endl; else { int s[4]; for (int i = 3; i >= 1; i--) { s[i] = T[i][n]; n -= T[i][n] * T[i][n]; } cout << s[1] << " " << s[2] << " " << s[3] << endl; } } return 0; }
Friday, December 11, 2015
UVa 11342 - Three-square
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment