NSQUARE2  NSquare Sum ( Medium )
Nsquare Sum! Problem? ( Medium )
Given Q pairs of integers Ni, Ai ( 1 <= Ai, Q <= 10^5 , 4 <= N <= 10^2 ) a, find Ni numbers whose square sums is equal to Ai. If there're more than one solution, print the one lexicographically smallest . If there's no solution, print "Impossible".
Q = 1 Ni = 4 A1 = 16 { 4² + 0² + 0² + 0² = 16} 
Input
There's an integer Q ( 1 <= Q <= 10^5 ) in the first line; it stands for the number of queries. The next Q lines describe each query with two integers Ni, Ai ( 1 <= Ai <= 10^5, 4 <= Ni <= 10^2 ). Ni is the number of integers that you need to find whose sum of squares is equal to Ai.
Output
You have to print Q lines, each one with Ni numbers such that the sum of squares is equal to Ai. If there's no solution, you've to print "Impossible".
Example
Input: 1 4 16 Output: 0 0 0 4 Input: 1 4 15 Output: 1 1 2 3 
hide comments
Mateus Dantas [ UFCG ]:
20121002 04:12:40
Thank you Francky! I've adjusted time limit, and now it's feasible in all languages ( I hope so ). 

Vaishali Behl:
20121001 12:34:38
Last edit: 20121001 12:49:46 

Francky:
20121001 10:14:23
I got 0.00s in C, but TLE in python, with the same algo, time limit is perhaps strict for the small case, don't forget python interpreter is slow to start, it's perhaps the problem, or it's my first part that is too slow (I don't think).


:D:
20120930 22:35:24
I didn't mean limits were too loose. It just I'm happy SPOJ has a fast machine now. Leave limits higher, so that script languages can pass. 

Mateus Dantas [ UFCG ]:
20120930 14:42:01
I'll set the problem feasible in Python. 

Francky:
20120930 14:16:23
OK, but think about Python users, please ! It seems yet very hard in Python, no ?


Mateus Dantas [ UFCG ]:
20120930 13:58:55
I'll change the statement limits and recalculate the complexity. This cluster is really fast. 

:D:
20120930 11:09:54
You really need to recalculate your complexity estimates for the new cluster :) 
Added by:  Mateus Dantas [ UFCG ] 
Date:  20120930 
Time limit:  0.600s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Manoel Lucas 