11407 - Squares

[WingletE]

I can't find a board for Volume CXIV, so I put this here.

Could somebody check for me if my answer below is right?

Code: Select all

Input:
10
10
100
1000
1001
2555
4999
5000
9998
9999
10000

Code: Select all

Output:
2
1
5
3
5
5
2
3
4
1

If my answer for the above testcase is right, someone give me some more tricky testcase please.
Thanks in advance!

[mmonish]

I get the following output from my AC code

Code: Select all

Output: 
2 
1 
2 
3 
3 
4
2 
3 
4 
1

Hope this helps.

[Observer]

For example, 1000 = 324 + 676 = 18*18 + 26*26.

[WingletE]

Thanks both of you.


I've adapted my code, but still getting wrong answer.
Help me, please.

Code: Select all

Input:
30
5
6
7
8
9
10
100
1000
1001
3333
3334
2555
4999
5000
7098
7099
7100
7111
7222
7777
8884
8999
9000
9001
9030
9025
9028
9998
9999
10000

Code: Select all

Output:
2
3
4
2
1
2
1
2
3
3
3
3
4
2
3
3
4
4
3
3
2
4
2
2
3
1
2
3
4
1

Are they alright?
Is there something else that I should pay attention to?

[abhi]

i am getting WA for this problem.it seems to be really simple.
please give me some special inputs.

here is my code

Code: Select all

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

int sqrs[101];

int main()
{
  
    for(int i=0;i<=100;i++){
        sqrs[i]=i*i;
    }
        
    int t;
    cin>>t;
    
    while(t--)
    {
        int N,c=0;
        cin>>N;
        
        //cout<<N<<" = ";
        while(N>0)
        {
            int i;
            for(i=0;i<101;i++)
                if(sqrs[i]>N)
                    break;
                    
            N-=sqrs[i-1];
            
            c++;
        }
        
        cout<<c<<'\n';
    }
    return 0;
    
}
            
        

[Robert Gerbicz]

i am getting WA for this problem.it seems to be really simple.
please give me some special inputs.

here is my code

Your code is totally wrong. It fails first for n=12.

Try to use dp. To speed up the build use also four squares theorem: f(n)<=4 for every n.

[Saul Hidalgo]

Hi! I'm using DP. And i got WA. I tested my program with all the cases, and i haven't error. Here is my code

Code: Select all

#include <cmath>
#include <iostream>

using namespace std;

int resul;

int dp[10001];
int dp2[10001];

void menor(int a){
	++resul;
	double temp=sqrt(a);
	int temp2=(int)temp;
	if (temp2*temp2!=a){
		for (int i=a-1 ; i>=1 ; i--){
			temp=sqrt(i);
			temp2=(int)temp;
			if (temp2*temp2==i){
				menor(a-i);
				break;
			}
		}
	}
}

int main(){
	int casos;
	cin >> casos;
	for (int caso=0 ; caso<casos ; caso++){
		int tempo;
		cin >> tempo;
		resul=0;
		if (dp2[tempo]!=-123){
			menor(tempo);
			cout <<resul << endl;
			dp[tempo]=resul;
			dp2[tempo]=-123;
		}
		else{
			cout <<dp[tempo] << endl;
		}
	}
	return 0;
}

Thanks to all

[Robert Gerbicz]

Hi! I'm using DP. And i got WA. I tested my program with all the cases, and i haven't error. Here is my code

I haven't checked your algorithm, but your code also fails on n=12, because it prints 4, but the correct answer is 3:

Code: Select all

 12=2^2+2^2+2^2

[Fewer terms isn't enough for n=12.]

[Chirag Chheda]

Code: Select all

Code Removed

Thnx to Jan

[Chirag Chheda]

Can someone plz reply..
Atleast tell me whether my algo is right or wrong
Thanx in advance

[Jan]

Try the cases.

Input:

Code: Select all

10
11
12
13
14
15
16
17
18
19
20

Output:

Code: Select all

3
3
2
3
4
1
2
2
3
2

Hope these help.

[Chirag Chheda]

Thank you sir for replying..
the output of my code for the test cases given by you match exactly with your output.
I wonder whats going wrong.Can you please give me some more test cases or check the output of my code with your ACC code for some other cases.
Also let me know if my algo is wrong

Waiting for your reply.
Thanx in advance

[Jan]

In my compiler your code returns different answers. However, can you explain the line?

Code: Select all

if(sqrt(i)*sqrt(i)==i)

[Chirag Chheda]

thats intersting that the same code returns different answers on different compilers.

Code: Select all

 if(sqrt(i)*sqrt(i)==i)

The above line means that if i is a perfect square than the answer should be 1 .That is it can be expressed as a square of only one number which is its squre root.

Also can u let me know for what input does my code return wrong answers on your machine..
Waiting for your reply

[Jan]

I think you haven't understood what I meant actually. Say i = 3. Then sqrt(i) = 1.7320508075688772935274463415059. And sqrt(i)*sqrt(i) = 3. But there can be problems with precisions. And it can occur even if i is a perfect square. I think you should write

Code: Select all

if(int(sqrt(i))*int(sqrt(i))==i)