10622 - Perfect P-th Powers

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

10622 - Perfect P-th Powers

Post by alex[LSD] » Mon Feb 02, 2004 10:37 am

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.
The more contests are held, the happier I am.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Feb 02, 2004 11:54 am

You, me, and many others, it seemed. :)

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

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Mon Feb 02, 2004 12:35 pm

Went there. Read it. Made the program work. Still aint proud of myself. But Gee that was a nasty one! :evil:
The more contests are held, the happier I am.

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Re: (Something...) Powers. From Waterloo contest.

Post by horape » Mon Feb 02, 2004 2:26 pm

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 :D )

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]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Mon Feb 02, 2004 8:30 pm

Thanks
Most of my trouble was about -2147483648.
NASTY PROBLE! :evil:
The more contests are held, the happier I am.

porfiry czarnecki
New poster
Posts: 5
Joined: Wed Feb 04, 2004 4:58 pm
Location: Poland, Gliwice

10622 (perfect p-th powers)

Post by porfiry czarnecki » Wed Feb 04, 2004 5:06 pm

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
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Wed Feb 04, 2004 5:27 pm

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

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

porfiry czarnecki
New poster
Posts: 5
Joined: Wed Feb 04, 2004 4:58 pm
Location: Poland, Gliwice

Post by porfiry czarnecki » Wed Feb 04, 2004 8:08 pm

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
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Wed Feb 04, 2004 8:29 pm

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
New poster
Posts: 5
Joined: Wed Feb 04, 2004 4:58 pm
Location: Poland, Gliwice

Post by porfiry czarnecki » Wed Feb 04, 2004 9:56 pm

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
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Wed Feb 04, 2004 10:38 pm

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

...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!
Last edited by Aleksandrs Saveljevs on Thu Feb 05, 2004 1:21 am, edited 1 time in total.

porfiry czarnecki
New poster
Posts: 5
Joined: Wed Feb 04, 2004 4:58 pm
Location: Poland, Gliwice

Post by porfiry czarnecki » Wed Feb 04, 2004 11:08 pm

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

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

Frustrations---Wanting some helps

Post by Mahmud776 » Tue Feb 10, 2004 7:09 pm

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]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

Post by alex[LSD] » Wed Feb 11, 2004 8:58 am

-2147483648

Output : 31
The more contests are held, the happier I am.

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

Not specified

Post by Mahmud776 » Mon Mar 01, 2004 2:41 pm

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

Post Reply

Return to “Volume 106 (10600-10699)”