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

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

Q11407: Squares

Post by WingletE » Sat Mar 01, 2008 9:25 am

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
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sat Mar 01, 2008 3:17 pm

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

Post by Observer » Sat Mar 01, 2008 7:10 pm

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

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

Post by WingletE » Tue Mar 04, 2008 9:30 am

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

11407 - Squares

Post by abhi » Sun Mar 16, 2008 2:37 pm

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

Post by Robert Gerbicz » Sun Mar 16, 2008 3:52 pm

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

Post by Saul Hidalgo » Sun Mar 16, 2008 11:53 pm

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

Post by Robert Gerbicz » Mon Mar 17, 2008 12:54 am

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

Post by Chirag Chheda » Sat Jun 21, 2008 2:40 pm

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

Post by Chirag Chheda » Mon Jun 23, 2008 8:21 am

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

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

Re: 11407 - Squares

Post by Jan » Wed Jun 25, 2008 10:15 pm

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

Post by Chirag Chheda » Thu Jun 26, 2008 7:10 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11407 - Squares

Post by Jan » Fri Jun 27, 2008 7:47 am

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

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

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11407 - Squares

Post by Jan » Fri Jun 27, 2008 8:13 am

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

Post Reply

Return to “Volume 114 (11400-11499)”