Page 2 of 3

Hmm!

Posted: Mon May 24, 2004 11:57 am
by shahriar_manzoor
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 :).

Posted: Mon May 24, 2004 12:21 pm
by Maniac
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!

Posted: Mon May 24, 2004 12:27 pm
by Maniac
PS if you want to know wether you've been slammed for problem F, see the other thread '22.05.04 Contest Problem F'. It's not full of praise as well...

Hmm

Posted: Mon May 24, 2004 1:07 pm
by shahriar_manzoor
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.

Re: Hmm!

Posted: Mon May 24, 2004 2:15 pm
by technobug
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.
This is the nasty one..... :) all other tricks should have been expected if one is to solve a difficult problem.... :)
And still there are some more traps.
wow....

indeed a nice one

Posted: Tue May 25, 2004 9:40 pm
by abishek
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

10655 - Contemplation! Algebra

Posted: Tue May 25, 2004 10:26 pm
by Dreamer#1
I got 5+ WA during contest in this problem, please help. :(

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? :o
If yes please give some more inputs,
else if wrong then please give the right output.

Thanks in advance.
-Dreamer

Posted: Tue May 25, 2004 10:46 pm
by Marcin Kwiatkowski
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.

Posted: Tue May 25, 2004 11:39 pm
by UFP2161
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

some test cases

Posted: Wed May 26, 2004 7:06 am
by abishek
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

Why make it so complex?!

Posted: Mon May 31, 2004 2:06 pm
by The Class
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++).

Posted: Mon May 31, 2004 3:40 pm
by abishek
hi,
one hard lesson that i have learnt is never use doubles when the problem can be solved in integers.
try to do it only with integers.
abi

Posted: Wed Jun 02, 2004 8:43 am
by InOutMoTo
Try to solve this by DP.
Because test data must contain complex numbers.
(I originally used solve a+b, a*b individually)

After using DP, it still contains a prob....a large exp.
So u must find the iteration to simplify prob.
(eg: a+b = 0, a*b = 1. a= i^3, b=-i^3)




good luck :D

Posted: Tue Jun 08, 2004 7:09 pm
by shuniu
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

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 
Output:

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

Posted: Tue Jun 15, 2004 5:57 pm
by htl
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]