Page 1 of 4
10622 - Perfect P-th Powers
Posted: Mon Feb 02, 2004 10:37 am
by 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.
Posted: Mon Feb 02, 2004 11:54 am
by Per
You, me, and many others, it seemed.
1. Yes.
2. The judge data is available at the Waterloo site.
Posted: Mon Feb 02, 2004 12:35 pm
by alex[LSD]
Went there. Read it. Made the program work. Still aint proud of myself. But Gee that was a nasty one!
Re: (Something...) Powers. From Waterloo contest.
Posted: Mon Feb 02, 2004 2:26 pm
by horape
alex[LSD] wrote: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.
Output:
Saludos,
HoraPe
Posted: Mon Feb 02, 2004 8:30 pm
by alex[LSD]
Thanks
Most of my trouble was about -2147483648.
NASTY PROBLE!
10622 (perfect p-th powers)
Posted: Wed Feb 04, 2004 5:06 pm
by 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.
Posted: Wed Feb 04, 2004 5:27 pm
by 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.
Posted: Wed Feb 04, 2004 8:08 pm
by 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?
Posted: Wed Feb 04, 2004 8:29 pm
by 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.
Posted: Wed Feb 04, 2004 9:56 pm
by 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.
Posted: Wed Feb 04, 2004 10:38 pm
by 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!
Posted: Wed Feb 04, 2004 11:08 pm
by porfiry czarnecki
Great! the programme is accepted.
Thanks for example with -64 - I didn't consider the case with negative numbers differs from positive.
Frustrations---Wanting some helps
Posted: Tue Feb 10, 2004 7:09 pm
by 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.
Posted: Wed Feb 11, 2004 8:58 am
by alex[LSD]
-2147483648
Output : 31
Not specified
Posted: Mon Mar 01, 2004 2:41 pm
by Mahmud776
Hello everybody:
Although, i didn't get any good help, but i got accepted after getting a huge amount of wrong answers (
).