10622 - Perfect P-th Powers

[alex[LSD]]

Funny, but I was having problems with that task.
Please help me with this:
1. Is magnitude of x the same as |x|?
2. I guess I could use some good tests to find where my program lies to me.

[Per]

You, me, and many others, it seemed.

1. Yes.
2. The judge data is available at the Waterloo site.

[alex[LSD]]

Went there. Read it. Made the program work. Still aint proud of myself. But Gee that was a nasty one!

[horape]

Funny, but I was having problems with that task.
Please help me with this:
1. Is magnitude of x the same as |x|?
2. I guess I could use some good tests to find where my program lies to me.

We needed 18 tries to get it working (yes, i'm a bit trigger happy when i get angry )

1. Yes.

Code: Select all

2147483647
32
-32
64
-64
4
-4

Output:

Code: Select all

1
5
5
6
3
2
1

Saludos,
HoraPe

[alex[LSD]]

Thanks
Most of my trouble was about -2147483648.
NASTY PROBLE!

[porfiry czarnecki]

I don't get it. I thought this problem is quite easy but I'm still getting wrong answer. What am I doing not in the proper way?

Code: Select all

program p10622(input, output);
var x : cardinal;

procedure check(x : cardinal);
var j : cardinal; i,k,nr,max : cardinal;
begin
max := 1;
for i := 2 to round(sqrt(x)) do if x mod i = 0 then
        begin
        j := i; nr := 1; k := x div i;
        while j < k do
                begin
                j := j*i;
                inc(nr);
                end;
        if (x div i = j) and (nr >= max) then
                begin
                max := nr+1;
                break;
                end;
        end;
writeln(output, max);
end;

BEGIN
while true do
        begin
        readln(input, x);
        if x = 0 then break
                else check(x);
        end;
END.

[Aleksandrs Saveljevs]

Sorry, I didn't check your code thoroughly, but "x" can be negative.

Also, note that RE in Pascal also results in WA.

[porfiry czarnecki]

At first I define x as a longint type but i got WA. In the text of the problem is written:

The value of x will have magnitude at least 2 and be within the range of a (32-bit) int in C, C++, and Java

... so I changed x into a cardinal type but the same error has occured.
I didn't know that RE is shown as a WA in pascal, so thanks. I've tested the 'check' procedure but I can't find mistake.
Maybe I've omited some important issue?

[Aleksandrs Saveljevs]

I meant that x can be less than 0, that is [-2; -2147483648], so the program crashes on sqrt(x) if x is negative. Longint is safe to use, however, you must not forget that you can't get |-2147483648| as longint. I still didn't check anything else, sorry.

[porfiry czarnecki]

You are right. Now I run 'check' with absolute value. I have also considered if x < 0 and p is even - then the procedure returns p=1.
The programme works over 0,5 sec longer. After this time it gives WA.
I used int64 instead of longint but it didn't help.

Code: Select all

program p10622(input, output);
type int = int64;
var
x : int;
a : longint;

procedure check(x : cardinal);
var i : longint; j,k,nr,max : int;
begin
max := 1;
for i := 2 to round(sqrt(x)) do if x mod i = 0 then
        begin
        j := i; nr := 1; k := x div i;
        while j < k do
                begin
                j := j*i;
                inc(nr);
                end;
        if (x div i = j) and (nr >= max) then
                begin
                max := nr+1;
                break;
                end;
        end;
if (a = -1) and not odd(max) then max := 1;
writeln(output, max);
end;

BEGIN
while true do
        begin
        readln(input, x);
        if x < 0 then
                begin
                a := -1; x := -x;
                end
        else a := 1;
        if x = 0 then break
                else if x > 0 then check(x);
        end;
END.

[Aleksandrs Saveljevs]

(the main thing in this edited post was as follows: )

...it is OK, I believe the answer for, say, -64, to be 3, not 1 (with the current configuration max will be 6, then 1), because -64=(-4)^3.

Good luck!

[porfiry czarnecki]

Great! the programme is accepted.
Thanks for example with -64 - I didn't consider the case with negative numbers differs from positive.

[Mahmud776]

What's wrong with my code, I can’t understand. My program produced correct answers of all inputs that I had found. But, Every time get shock when I submit my code. What’s wrong. Has any critical case that I have missed. In the problem statement,

The value of x will have magnitude at least 2 and be within the range of a (32-bit) int in C, C++, and Java.

According to this statement, the value of x will be always positive. Is not it? I considered both positive and negative for the value of x. But wrong answer is not escaping me.
Could anybody tell me something. I gave some inputs and outputs. Could anybody tell me about the correctness of my answers.

Inputs:
14348907
1254874569
-8388608
8388608
65536
-65536

Outputs:
15
1
23
23
16
1

Are my outputs correct? Could somebody give me some critical inputs and outputs.

[alex[LSD]]

-2147483648

Output : 31

[Mahmud776]

Hello everybody:
Although, i didn't get any good help, but i got accepted after getting a huge amount of wrong answers ( ).