## 11407 - Squares

Moderator: Board moderators

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11407 - Squares

Finally I got ACC.

Keep posting.
Bye.

masteringminds
New poster
Posts: 4
Joined: Wed Jun 18, 2008 1:40 am

### Re: 11407 - Squares

I have tried many inputs and it supposedly works but Still get WA
It is a mix between Looping and Recursion coz I dont know DP!
Here is the code

Please try to find the error in the program

Code: Select all

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

int go (double n,int j)
{
int max=0;
if(n==0) return max;
n-=double(j*j);
j=int(sqrt(n));
max++;
max+= go(n,j);

return max;
}
int main()
{
//ifstream cin("a.txt");
int t,max=0,best=1000;
double n;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n;
best=1000;
for(int j=int(sqrt(n));j>0;j--)
{
max=go(n,j);
if(max<best)
best=max;
}
cout<<best<<endl;

}
return 0;
}``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11407 - Squares

Try this case..

Code: Select all

``````1
48``````
My output is..

Code: Select all

``3``

masteringminds
New poster
Posts: 4
Joined: Wed Jun 18, 2008 1:40 am

### Re: 11407 - Squares

mmmm...mine outputs 4
ok what do u think is the error?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11407 - Squares

masteringminds wrote:mmmm...mine outputs 4
ok what do u think is the error?
Well, I think go() function should do the same thing as the main() does.. (looping j from sqrt(n) to 1)

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11407 - Squares

N=a1^2+a2^2+a3^2+.........+an^2
so N-a1^2+a2^2+a3^2+.........+an^2=0

then i ran a breadth first search from N. it took .724 sec to get AC,time limit was 1 sec, so it was tight. If you don't use STL you don't need to be tensed about it.

sample:

Code: Select all

``````14
9999
10000
1
1001
4546
3467
2368
8990
2321
6789
3421
1256
1244
5467``````
output:

Code: Select all

``````4
1
1
3
2
3
2
3
3
3
3
2
4
3
``````
happy programming!!

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11407 - Squares

Omg I have read previous posts and now all I can say is WTF ! DP...BFS...etc why make this so complicated? First of all, n should be always 4 or less for every N in the range (1-10000). You can try to prove this (I did, believe me it's not so hard). Just use a boolean array and 4 nested loops. You can even precalculate and send a table. Got Accepted in 4 ms better than BFS huh
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

braverman
New poster
Posts: 1
Joined: Sat Apr 13, 2013 6:20 am

### Squares, 11407

Getting WA, I checked my code with all inputs, and it gives me good results, I do not really know the problem

Code: Select all

``````#include <math.h>
#include <stdio.h>
int main(){
int n,k=0,occ,max,t,i,j,a;
scanf("%d",&n);
while(k<n){
scanf("%d",&a);
max=100;
if(a==0) max=1;
for(j=int(sqrt(a));j>=1;j--){
i=j;
t=a;
occ=0;
while((i>=1)&(t>0)){
if(i*i<=t){
t-=i*i;
occ++;}
else
i--;
}
if(occ<max) max=occ;
}
printf("%d\n",max);
k++;
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: Squares, 11407

From uhunt:
AKJ88> @braverman There are several test cases for which your program doesn't print the correct output. For example 43 96 142 (r|d) (my ac code prints 3 for all of them).
AKJ88> 43: 5^2+3^2+3^2
AKJ88> I used dynamic programming to solve this problem. Recursive part was sth like this: count(num){ for(i=1; i<=sqrt(num); i++) res= min(res, 1+count(num-i^2)) }
AKJ88> It isn't a spoiler since it requires more things to be complete!:-)
Check input and AC output for thousands of problems on uDebug!

anando_du
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

### Re: 11407 - Squares

just used straight forward DP . And got AC on 1st go.. with in .032 sec.