any hint or test case ?

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?

Do you known test?I got wa 2,but I think that my program is right)

Who can help me!!!tell me how to solve the problem!!!

for i := 2 to n do
    begin
      min:=maxlongint;
      for j := 1 to trunc(sqrt(i)) do
        if min>f[i-j*j] then
          min:=f[i-j*j];
      f[i]:=min+1;
    end;

Объясните по русски, что им надо???

Hi,

It looks like, input test cases are not large enough. My DP program is taking 3 seconds for large inputs like 50000 or 60000 etc, but it got accepted in 0.062 seconds. Admins need to look at this.

Varun

There exists a proof by Lagrange, that 4 square are enough to display any number and it's a direct answer.
It's a kind of Number Theory problem. I find it very useful because there is just 2 or 3 conditions you should check.
Good Luck

I have Wrong Answer on test number 18. Tell me please, how I can solve this problem. Where I can get Tests for this problem

Tell my please, why I have Wrong Answer on test number 13 and if it is not problem, tell how I can solve this problem to e-mail WitaliyProg@mail.ru
Thanks!

answer == 1  - manually
answer == 2  - manually
answer == 3  - n%8 !=7
else answer ==4

I have Ac with wrong solution. My solution fails on 112 and other 4^k(8n+7) where k>=2 tests.

DP is easy. I want to know the easiest solution to the problem. Please contact me. megatronbiao@gmail.com

Thanks.

Sorry for my English.

#include <iostream>
#include <cmath>
using namespace std;
int data[60001];
int main()
{
    int n;
    cin>>n;
    data[1]=1;
    data[2]=2;
    for (int i=3;i<=n;++i) {
        int min=data[i-1]+1;
        for (int j=2;j<=245;++j) {
            if (i>=j*j) {
               if (min>data[i-j*j]+1) min=data[i-j*j]+1;
            }
            else break;
        }
        data[i]=min;
    }
    cout<<data[n];
    return 0;
}

I know AC solution, that checks correctly for answers 1 and 2, but distinguishes answers 3 and 4 using simple test

if (n%8==7) {
   answer 4
} else {
   answer 3
}

One of tests that it not passes is 59996. It answers 3 while correct answer is 4. Please add some tests where n%8!=7 and answer is 4.

pleas tell me where is my mistake?

var n,q,a:longint;
begin
  read(n); q:=0;
   while n>=1 do
    begin
      a:=trunc(sqrt(n));
      a:=sqr(a); inc(q);
      n:=n-a;
    end;
   write(q);
end.

#include<stdio.h>
long func(long a,long b,long c);
long pow(long x,long y);
long result=1;
long n;
long k;
int count=0;
int main(){
    scanf("%ld",&n);
    k=n;
    for(;k>0;){
               k-=pow((long)sqrt(k),2);;
               result=1;
               count++;
    };
    func(n,0,(long)sqrt(n));
    printf("%d",count);
    for(;;);
};
long pow(long x,long y){
     if (y!=0) return x*pow(x,y-1);
     return 1;
};
long func(long a,long b,long c){
     int i;
     if (b>=count || a<0) return 0;
     if (b<count && a==0){
        count=b;
        printf("%ld %ld %ld\n",a,b,c);
     };
     for(i=c;i>0;i--) func(a-pow(i,2),b+1,i);
};

Could you give me some tests?

Can anybody explain me DP algo what is it?

#include <stdio.h>
#include <math.h>
int N, kol, Optkol;
void kvad(int n)
{
 for (int i=sqrt(double(n)); i>=1; i--)
    {
     if (n-i*i>=0 && kol+1 < Optkol)
       {
        kol++;
        mas[kol] = i*i;
        n -= i*i;
        if (n>0) kvad(n);
        else if (n == 0)
          Optkol = kol;

        l--;
        n=n+i*i;
       }
     }
}

int main()
{ scanf("%d", &N);
  Optkol = N;
  kvad(N);
  printf("%d\n", Optkol);


        return 0;
}