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

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

### Q11407: Squares

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.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
For example, 1000 = 324 + 676 = 18*18 + 26*26.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:
Thanks both of you.

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

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
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

### 11407 - Squares

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11407 squares

abhi wrote: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
New poster
Posts: 18
Joined: Wed Jan 03, 2007 2:36 am
Location: Los Teques, Venezuela

### Re: 11407 squares

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11407 squares

Saul Hidalgo wrote: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
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11407 - Squares

Code: Select all

``````Code Removed
``````
Thnx to Jan
Last edited by Chirag Chheda on Fri Jun 27, 2008 8:19 am, edited 1 time in total.

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

### Re: 11407 - Squares

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11407 - Squares

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.
Ami ekhono shopno dekhi...
HomePage

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

### Re: 11407 - Squares

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11407 - Squares

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

Code: Select all

``if(sqrt(i)*sqrt(i)==i)``
Ami ekhono shopno dekhi...
HomePage

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

### Re: 11407 - Squares

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
``if(int(sqrt(i))*int(sqrt(i))==i)``