Algorithm

problem link- https://www.spoj.com/problems/NFURY/

NFURY - Training Land of Fury

#dynamic-programming

 

S.H.I.E.L.D. is recruiting soldiers for the battle with Loki's army. Nick Fury has come to Manhattan to find a large area of land to be used for training purposes. He meets a popular landlord there who is a little foolish by nature.
He gives square pieces of land with integral sides and charges on the basis of number of pieces of land bought irrespective of how large a piece of land is. Fury has to buy exactly A square units of land. Help Fury by determining the minimum number of pieces that should be bought in order to minimize the expenditure.

Input

The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains a single integer A denoting the area that nick fury want to buy.

  • 10 ≤ T ≤ 100000
  • 1 ≤ A ≤ 1000

Output

For each test case print the minimum number of pieces that should be bought.

Example

Input:
4
1
2
3
10

Output:
1
2
3
2

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 1e5+5;

int dp[1005];

int main(){
	io;
	for(int i = 1;i <= 1000; i++)
		dp[i] = INT_MAX;
	dp[0] = 0;
	dp[1] = 1;
	for(int i = 2; i <= 1000; i++){
		for(int j = i;j >= 0; j--){
			if((i-(j*j)) >= 0)
			dp[i] = min(dp[i], 1 + dp[i - (j*j)]);
		}
	}
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		cout << dp[n] << endl;
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4
1
2
3
10

Output

x
–
+
cmd
1
2
3
2
Advertisements

Demonstration

SPOJ Solution-Training Land of Fury-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python