The most important idea for this task is the fact that according to Lagrange’s Four Square Theorem, every natural number can be written as the sum of squares of four non-negative integers.
Good luck, hope this will help!

Edited by author 13.11.2021 00:26

Edited by author 13.11.2021 00:26

We could solve it by Theorem on the sum of four squares, I wonder how to solve it by DP? If you know, please help me, thank you!

#include <iostream>
#include <cmath>
using namespace std;

int minCoins(int coins[], int m, int V)
{
    int table[V+1];

    table[0] = 0;

    for (int i=1; i<=V; i++)
        table[i] = INT_MAX;

    for (int i=1; i<=V; i++)
    {
        for (int j=0; j<m; j++)
            if (coins[j] <= i)
            {
                int subResult = table[i-coins[j]];
                if (subResult != INT_MAX && subResult + 1 < table[i])
                    table[i] = subResult + 1;
            }
    }
    return table[V];
}

int main()
{
    int V;
    cin>>V;
    int coins[1000];
    int i;


    for(i=1;i<=sqrt(V);i++)
    {
        coins[i-1] = (i)*(i);
    }
    int m = sqrt(V);

    cout<< minCoins(coins, m, V)<<endl;
    return 0;
}



This problem can be translated to get the minimum amout of coins to get the value N.(We must just check that the coins are the actual square numbers).

i write the output and the square roots.
Input 41 Answer 2
16 25
Input 51 Answer 3
1 1 49
Input 19 Answer 3
1 9 9
Input 102 Answer 3
1 1 100
Input 18467 Answer 3
25 6561 11881
Input 6334 Answer 3
25 225 6084
Input 26500 Answer 2
256 26244
Input 19169 Answer 2
400 18769
Input 15724 Answer 3
36 1764 13924
Input 11478 Answer 3
4 25 11449
Input 29358 Answer 3
4 5329 24025
Input 26962 Answer 2
1681 25281
Input 24464 Answer 3
64 64 24336
Input 5705 Answer 3
4 225 5476
Input 28145 Answer 2
256 27889
Input 23281 Answer 3
9 7396 15876
Input 16827 Answer 3
49 5329 11449
Input 9961 Answer 3
16 144 9801

There can be any solution but the number of square roots is unique

Wheres my wrong? help pleas
#include <bits/stdc++.h>

const int maxn = (int)1e6;
const int mod = (int)1e9 + 7;

using namespace std;

int n;
int dp[maxn]={-1};

int calc(int n){
    int res=n;
    dp[0]=0;
    if(dp[n] != -1)
        return dp[n];
     for(int i=1; i*i <= n; i++){
         res=min(res,1+calc(n-i*i));
     }
    return dp[n]=res;
}

int main(){
    scanf("%d",&n);
    printf("%d\n", calc(n));

    return 0;
}

Edited by author 20.12.2015 23:27

Edited by author 11.10.2015 17:44

my code:
#include<iostream>
#include<cmath>
using namespace std;
main()
{
    unsigned int n,temp,nc;
    cin>>n;
    nc=n;
    temp=sqrt(n);
    if(n==0)
    cout<<0;
    else if(temp*temp==n)
    cout<<1;
    else
    {
        unsigned int x=-1,m=0,q=4,t;
        for(unsigned int i=temp;i>=1;i--)
        {
            t=i;
            while(x!=0)
            {
                x=n-t*t;
                n=x;
                t=sqrt(x);
                m++;
            }
        if(m<q)
            q=m;
        if(m==2)
            break;
        x=-1;
        m=0;
        n=nc;
        }
        cout<<q;
    }
}

Hi
I got WA on test 10 |:
I need some testcase!
PLZ HELLLLLP MEEEE! :D

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int function(int n)
{
    if (n == 1)
        return 1;
    else
        if (n == 0)
        return 0;
    else{

        int k = 999999999;
        for (int i = 1; i <= sqrt(n); i++)
        {
            int a = function(n - i*i);
            if (a < k )
                k = min(k, a);
        }
        return function(k) + 1;



    }


}

int main()
{
    int n;
    cin >> n;
    cout << function(n) << endl;

}

I am getting a WA at test #5

Here's my code :
#include <iostream>

using namespace std;

int main(){
  int n,i=1,count=0;
  cin>>n;
  while(n>0){
    if(i*i<=n)
      i++;
    else{
      n-=(i-1)*(i-1);
      i=1;
      count++;
    }
  }
  cout<<count<<endl;
  return 0
}

Use Brute Force approach with Lagrange's four square theorem, but to short-cut do check only  1, 2, 3 case. If those do not give any squares then output 4 (see Lagrange's theorem). :)

Hello i wrote the following code in python , but it takes too much time, hwo should it be improved
class timus1073:
    def __init__(self):
        pass

    def problem(self,y):

        a = [0] + range(1,60001)

        b = [x**2 for x in range(1,246)]

        for i in b:
            j = 0
            while j+i <= 60000:
                if (a[j+i] > a[j] + 1):
                    a[j+i] = a[j] + 1

                j = j + 1


        return a[y]


if __name__ == "__main__":
    p = timus1073()
    a = input()
    print p.problem(int(a))

var
 fi,fv:text;
 chi,kolc: longint;
procedure round_sqrt(a:longint; var kol:longint);
var
   b:longint;
begin
     b:=trunc(sqrt(a));
     b:=b*b;
     a:= a-b;
     if a> 0 then begin
        kol:=kol+1;
        round_sqrt(a,kol);
     end
     else kol:=kol+1;
end;
begin
assign(fi,'input.txt');
reset(fi);
assign(fv,'output.txt');
rewrite(fv);
{============}
read(fi,chi);
kolc:=0;
if chi>0 then
round_sqrt(chi,kolc);
write(fv,kolc);
{============}
close(fi);
close(fv);
end.

My program 4729094 got AC, but the same program gives WA2 on problem 1593 (harder tests). So, there is a class of numbers those my solution gives incorrect answer and I think some of such numbers must be below 60000

Could you give me case for 14.Thank you.

Could you give me case for test 14? Thank you!

I get WA on Test 14, some can help me with this? Here's my code.

#include <iostream>
#include <math.h>

int solve( float val_p )
{
    int id = 0,
        sqr = 0,
        seqCount = 0,
        bestCount = 9999,
        maxVal = val_p,
        n = (int)sqrt( val_p );
    for( int seqID = n; seqID > n/2; seqID-- )
    {
        id = seqID;
        maxVal = val_p;
        seqCount = 0;
        while( id > 0 )
        {
            sqr = id*id;
            --id;
            if ( maxVal >= sqr )
            {
                maxVal -= sqr;
                id = sqrt( float( maxVal ) );
                if ( ++seqCount > bestCount )
                    break;
            }
        }
        bestCount = std::min( bestCount, seqCount );
    };
    return bestCount;
};

int main()
{
    unsigned int val = 0;
    while( std::cin >> val )
    {
        if ( val > 60000 || val <= 0 ) break;
        std::cout << solve( val ) << std::endl;
    }
    return 0;
}

Why I have Crash (access violation)?

Of course, Dynamic Programming solution is better.
But for your info there is a theorem of Lagrange.
Quote from Wikipedia
"Lagrange's four-square theorem states that any natural number can be represented as the sum of four integer squares"

http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem

Example,
    3 = 1^2 + 1^2 + 1^2  + 0^2
    31 = 5^2 + 2^2 + 1^2 + 1^2
    310 = 17^2 + 4^2 + 2^2 + 1^2.

Here is my C# code:


using System;
class Program
{

    static void Main()
    {
        int n = int.Parse(Console.ReadLine());

        for (int i1 = 0; i1 <= (int)Math.Sqrt(n); i1++)
            for (int i2 = 0; i2 <= (int)Math.Sqrt(n); i2++)
                for (int i3 = 0; i3 <= (int)Math.Sqrt(n); i3++)
                    for (int i4 = 0; i4 <= (int)Math.Sqrt(n); i4++)
                        if (i1 * i1 + i2 * i2 + i3 * i3 + i4 * i4 == n)
                        { Console.WriteLine(Math.Sign(i1)+Math.Sign(i2)+Math.Sign(i3)+Math.Sign(i4)); return; }

    }
}

var n,tmp,i:word;
begin
i:=0;
read(n);
repeat
tmp:=sqr(trunc(sqrt(n)));
n:=n-tmp;
i:=i+1;
until n=0;
writeln(i);
end.

This is my programm, why it's wrong? I do some test and i think to my programm is right. Help please, where my mistake?