11407 - Squares

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 11407 - Squares

Post by Chirag Chheda » Fri Jun 27, 2008 8:17 am

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

Keep posting.
Bye.

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

Re: 11407 - Squares

Post by masteringminds » Tue Jul 08, 2008 3:43 am

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 :D

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

Re: 11407 - Squares

Post by helloneo » Tue Jul 08, 2008 4:42 pm

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

Post by masteringminds » Tue Jul 08, 2008 4:45 pm

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

Post by helloneo » Tue Jul 08, 2008 4:59 pm

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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11407 - Squares

Post by Shafaet_du » Sun Oct 10, 2010 9:07 pm

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!!

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

Re: 11407 - Squares

Post by plamplam » Fri Nov 11, 2011 12:20 am

Omg I have read previous posts and now all I can say is WTF :roll: ! 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

Post by braverman » Sat Apr 13, 2013 6:32 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Squares, 11407

Post by brianfry713 » Tue Apr 16, 2013 1:55 am

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

Post by anando_du » Fri Mar 20, 2015 10:12 am

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

Post Reply

Return to “Volume 114 (11400-11499)”