Page 2 of 2
Re: 11407 - Squares
Posted: Fri Jun 27, 2008 8:17 am
by Chirag Chheda
Thnx Jan.Your help helped me.
Finally I got ACC.
Keep posting.
Bye.
Re: 11407 - Squares
Posted: Tue Jul 08, 2008 3:43 am
by masteringminds
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;
}
Thanks in advance
Re: 11407 - Squares
Posted: Tue Jul 08, 2008 4:42 pm
by helloneo
Try this case..
My output is..
Re: 11407 - Squares
Posted: Tue Jul 08, 2008 4:45 pm
by masteringminds
mmmm...mine outputs 4
ok what do u think is the error?
Re: 11407 - Squares
Posted: Tue Jul 08, 2008 4:59 pm
by helloneo
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)
Re: 11407 - Squares
Posted: Sun Oct 10, 2010 9:07 pm
by Shafaet_du
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:
happy programming!!
Re: 11407 - Squares
Posted: Fri Nov 11, 2011 12:20 am
by plamplam
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
Squares, 11407
Posted: Sat Apr 13, 2013 6:32 am
by braverman
Getting WA, I checked my code with all inputs, and it gives me good results, I do not really know the problem
please help me, here is my code
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;
}
Re: Squares, 11407
Posted: Tue Apr 16, 2013 1:55 am
by brianfry713
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!:-)
Re: 11407 - Squares
Posted: Fri Mar 20, 2015 10:12 am
by anando_du
just used straight forward DP . And got AC on 1st go.. with in .032 sec.