#include<stdio.h>
int main()
{
int a[32]={1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961};
int i,t,j;
int dp[1005];
dp[1]=1;
dp[2]=2;
dp[3]=3;
for(i=4;i<=1000;i++)
{
dp[i]=i;
for(j=0;j<31;j++)
{
if(a[j]<=i && dp[i]>dp[i-a[j]]+1)
dp[i]=dp[i-a[j]]+1;
}
}
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
printf("%d\n",dp[n]);
}
return 0;
}
System Design Masterclass
A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.
1000+ learners
Details →Redis Internals
Learn internals of Redis by re-implementing some of the core features in Golang.
46+ learners
Details →