11407 - Squares

[Chirag Chheda]

Thnx Jan.Your help helped me.
Finally I got ACC.

Keep posting.
Bye.

[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

[helloneo]

Try this case..

Code: Select all

1
48

My output is..

Code: Select all

3

[masteringminds]

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

[helloneo]

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]

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]

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

[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;
}

[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!:-)

[anando_du]

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