10655 - Contemplation - Algebra
Moderator: Board moderators
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
Hmm!
Perhaps! I am the problem setter with highest number of problems . You participate in contests to enjoy and I also set problems for the same reason. Sometimes I have to do some experiments to enjoy. This problem was such a experiment with all those nasty tricks. For example:
a) Input is terminated by a line containing 0 0, not "0 0 0" and there were inputs like "0 0 3" so many were trapped.
b) a and b could be complex.
c) Still there were inputs like "1 0 200000000" or "2 1 200000000" so yes fast exponentiation was required or you had to handle this case expecially.
And still there are some more traps.
I was actually so worried, I had no time to set a difficult problem but somehow I had to keep you busy for five hours. Problem G was difficult but I knew few people will understand and try it.
Allmost all elite problem setters have some problems which only he can solve and with it a few others. As my number of problems is highest so is the no of nasty problems.
I should have been slammed for problem F (which was wrong) not problem E I guess .
a) Input is terminated by a line containing 0 0, not "0 0 0" and there were inputs like "0 0 3" so many were trapped.
b) a and b could be complex.
c) Still there were inputs like "1 0 200000000" or "2 1 200000000" so yes fast exponentiation was required or you had to handle this case expecially.
And still there are some more traps.
I was actually so worried, I had no time to set a difficult problem but somehow I had to keep you busy for five hours. Problem G was difficult but I knew few people will understand and try it.
Allmost all elite problem setters have some problems which only he can solve and with it a few others. As my number of problems is highest so is the no of nasty problems.
I should have been slammed for problem F (which was wrong) not problem E I guess .
OK, that complex numbers are involved, maybe, very maybe some people could have thought of that during contest time (like Adrian Kuegel, but he needed a hint from you too!).
But that input contains lines like 0 0 3 that should be processed beats it all! What the heck does this have to do with programming skills or knowledge of algorithms?
Please, I beg you, next time make real problems without dumb traps to spoil all our time. After all, it's a PROGRAMMING contest and not a (mind)READING contest!
But that input contains lines like 0 0 3 that should be processed beats it all! What the heck does this have to do with programming skills or knowledge of algorithms?
Please, I beg you, next time make real problems without dumb traps to spoil all our time. After all, it's a PROGRAMMING contest and not a (mind)READING contest!
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
Hmm
Well,
As I said my intension is to make problem solvers read problem statement carefully and think about all the traps.
It is a O-level math
If a+b=2 ab =7 find the value of a^5+b^5.
I set this problem from that math. And when I did this sort of Algebra I had no idea about complex numbers. may be the math culture of your country is different.
a^3+b^3=(a+b)^3-3ab*(a+b) and such forms can be found for higher powers using lower powers.
As I said my intension is to make problem solvers read problem statement carefully and think about all the traps.
It is a O-level math
If a+b=2 ab =7 find the value of a^5+b^5.
I set this problem from that math. And when I did this sort of Algebra I had no idea about complex numbers. may be the math culture of your country is different.
a^3+b^3=(a+b)^3-3ab*(a+b) and such forms can be found for higher powers using lower powers.
Re: Hmm!
This is the nasty one..... all other tricks should have been expected if one is to solve a difficult problem....shahriar_manzoor wrote:Sometimes I have to do some experiments to enjoy. This problem was such a experiment with all those nasty tricks. For example:
a) Input is terminated by a line containing 0 0, not "0 0 0" and there were inputs like "0 0 3" so many were trapped.
wow....And still there are some more traps.
indeed a nice one
After having solved it finally i feel that it is indeed a nice one, but then, may be some pity must have been shown on the solvers. Not too many traps on one problem that too in a contest.
abi
abi
10655 - Contemplation! Algebra
I got 5+ WA during contest in this problem, please help.
Are the above outputs for the respective inputs ok?
If yes please give some more inputs,
else if wrong then please give the right output.
Thanks in advance.
-Dreamer
Code: Select all
Input:
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
0 0
Output:
2
0
-4
-8
-8
0
Are the above outputs for the respective inputs ok?
If yes please give some more inputs,
else if wrong then please give the right output.
Thanks in advance.
-Dreamer
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
-
- New poster
- Posts: 5
- Joined: Thu Jan 01, 2004 10:43 pm
- Location: Gdynia, Poland
Hi Dreamer!
In my opinion your input are wrong because there doesn't exist such integer that a+b=2 and a*b=2.
If you tried solving those equations you would be given:
a*(2-a)=2
-a^2 + 2a - 2 = 0
delta = 4-4*(-1)*2 = -4 <0 => there is no integer a.
Or maybe I misunderstood everything... Anyway, I had also some difficulties with that problem and I still dont know what tricky inputs had been made. Problem seems to be easy but... If anybody who have solved it could write some inputs I would be grateful.
In my opinion your input are wrong because there doesn't exist such integer that a+b=2 and a*b=2.
If you tried solving those equations you would be given:
a*(2-a)=2
-a^2 + 2a - 2 = 0
delta = 4-4*(-1)*2 = -4 <0 => there is no integer a.
Or maybe I misunderstood everything... Anyway, I had also some difficulties with that problem and I still dont know what tricky inputs had been made. Problem seems to be easy but... If anybody who have solved it could write some inputs I would be grateful.
"Imagination is more important than knowledge" Albert Einstein
The equation still has a solution. It's just not part of the real number line.
Read the other post concering this matter:
http://online-judge.uva.es/board/viewtopic.php?t=5688
Read the other post concering this matter:
http://online-judge.uva.es/board/viewtopic.php?t=5688
some test cases
you may want to try out some test cases like this
10 11 2
1 1 10000
2 2 11
0 0 3
0 0 4
12 13 5
1 1 0
1 1 1
0 0
my ac program gives
78
-1
-64
0
0
146652
2
1
10 11 2
1 1 10000
2 2 11
0 0 3
0 0 4
12 13 5
1 1 0
1 1 1
0 0
my ac program gives
78
-1
-64
0
0
146652
2
1
Why make it so complex?!
What's wrong with this one, it gives WA!
[cpp]
#include <iostream>
#include <complex>
#include <cmath>
#include <stdio.h>
using namespace std;
int main() {
long pi = 0, qi = 0, ni = 0;
while (scanf("%d %d %d", &pi, &qi, &ni) > 2) {
double p = pi;
double q = qi;
double n = ni;
complex<double> temp = complex<double>(p * p - 4 * q, 0);
complex<double> a = (p + sqrt(temp)) / 2.0;
complex<double> b = (p - sqrt(temp)) / 2.0;
complex<double> d = pow(a, n) + pow(b, n);
cout << real(d) << endl;
}
return 0;
}
[/cpp]
I'm new here. what compiler does oj use, where can i get it? i get a lot ce, runs ok in my comp(vc++).
[cpp]
#include <iostream>
#include <complex>
#include <cmath>
#include <stdio.h>
using namespace std;
int main() {
long pi = 0, qi = 0, ni = 0;
while (scanf("%d %d %d", &pi, &qi, &ni) > 2) {
double p = pi;
double q = qi;
double n = ni;
complex<double> temp = complex<double>(p * p - 4 * q, 0);
complex<double> a = (p + sqrt(temp)) / 2.0;
complex<double> b = (p - sqrt(temp)) / 2.0;
complex<double> d = pow(a, n) + pow(b, n);
cout << real(d) << endl;
}
return 0;
}
[/cpp]
I'm new here. what compiler does oj use, where can i get it? i get a lot ce, runs ok in my comp(vc++).
After countless tries, I finally got AC, it certainly has alot of traps, I ended up with a whole list of if statements to catch each of the traps in my program...
Need to catch the following
n==0
p==0 && q==0
p==1 && q==0
p==0 && q==1
p==2 && q==1
Input
Output:
Need to catch the following
n==0
p==0 && q==0
p==1 && q==0
p==0 && q==1
p==2 && q==1
Input
Code: Select all
0 0 0
0 0 1
0 0 200000000
1 3 0
999999 999999 0
1 0 200000000
2 0 61
2 1 0
2 1 100
2 1 200000000
0 0 0
0 1 1
0 1 2
0 1 3
0 1 199999999
0 1 200000000
0 1 200000001
0 1 200000002
5 6 7
10 20 10
90 87 3
999 231 2
0 0
Code: Select all
2
0
0
2
2
1
2305843009213693952
2
2
2
2
0
-2
0
0
2
0
-2
2315
393600000
705510
997539
10655
I think it's not a hard one, and not finding out any mistake in my code. But I use Dev-C++ compiler and not getting the right result. I don't know the problem is syntax or type changing or something else.. Is there someone willing to run the prog for me and see what's wrong?
[c]
#include<stdio.h>
#include<math.h>
long long power(long long,long);
void main(void)
{
long p,q,c;
long long a,b;
while(1)
{
scanf("%ld %ld",&p,&q);
if(p==0 && q==0)
break;
scanf("%ld",&c);
a=(p+sqrt(p*p-4*q))/2,b=p-a;
printf("%lld\n",power(a,c)+power(b,c));
}
}
long long power(long long a,long c)
{
int x;
long long t,ans;
if(c==0 || a==1)
return 1;
if(a==0)
return 0;
if(c==1)
return a;
for(t=a,x=0,ans=1;x<64;x++)
{
if(t<64)
t*=t;
if(c%2==1)
ans*=t;
c/=2;
}
return ans;
}
[/c]
[c]
#include<stdio.h>
#include<math.h>
long long power(long long,long);
void main(void)
{
long p,q,c;
long long a,b;
while(1)
{
scanf("%ld %ld",&p,&q);
if(p==0 && q==0)
break;
scanf("%ld",&c);
a=(p+sqrt(p*p-4*q))/2,b=p-a;
printf("%lld\n",power(a,c)+power(b,c));
}
}
long long power(long long a,long c)
{
int x;
long long t,ans;
if(c==0 || a==1)
return 1;
if(a==0)
return 0;
if(c==1)
return a;
for(t=a,x=0,ans=1;x<64;x++)
{
if(t<64)
t*=t;
if(c%2==1)
ans*=t;
c/=2;
}
return ans;
}
[/c]