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:
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
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
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.
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
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:
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
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:
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:
[Fewer terms isn't enough for n=12.]
Chirag Chheda
Learning poster
Posts: 74 Joined: Sat Jun 21, 2008 12:24 pm
Location: India
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:
Post
by Jan » Wed Jun 25, 2008 10:15 pm
Try the cases.
Input:
Output:
Hope these help.
Chirag Chheda
Learning poster
Posts: 74 Joined: Sat Jun 21, 2008 12:24 pm
Location: India
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:
Post
by Jan » Fri Jun 27, 2008 7:47 am
In my compiler your code returns different answers. However, can you explain the line?
Chirag Chheda
Learning poster
Posts: 74 Joined: Sat Jun 21, 2008 12:24 pm
Location: India
Post
by Chirag Chheda » Fri Jun 27, 2008 8:03 am
thats intersting that the same code returns different answers on different compilers.
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:
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