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?

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

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]