PSYCHON - Psycho

Given an integer N, the number N is called “Psycho Number”. Psycho Number is calculated as follows:

First, If we factorize N , then we have some prime and their power. Assume that, there are M powers. From M powers , you should count the number of even and odd powers. Then if the number of even power is strictly greater than odd power, then we call the number N is “Psycho Number”, otherwise the number N is call “Ordinary Number”.

As for example, if N = 67500 then prime factorization, 

67500 = 22 x 33 x 54

Count even powers and odd powers . This number have 2 even power(2, 4) and 1 odd power (3). Since even power 2 (2, 4) is greater than odd power 1 (3), so the number 67500 is a Psycho Number.

Input:

An integer T (1 <= T <= 106) denoting the number of test cases followed by T lines. Each containing a single integer N (1 <= N <= 107).

Output:

For each case print  “Psycho Number” or “Ordinary Number”.

Sample

Sample Input
2
3
4

Sample Output
Ordinary Number
Psycho Number
Note: 0 and 1 are not a psycho number.
Psycho 2: Psycho Function Psycho 3: Make Psycho Psycho 4: Psycho34 (easy)

Problem setter: Shipu Ahamed, Dept. of CSE, Bangladesh University of Business and Technology (BUBT)

[ Edited by EB ] Warning: Some input files are broken.


Added by:Shipu Ahamed
Date:2013-09-18
Time limit:0.5s
Source limit:6000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-05-20 14:25:51 Abhinav
Finally after 7 WA and 5 Tle ...... AC :)
2015-04-02 14:18:25 Madhav
good question!!
2015-03-04 20:46:56 Sayak Haldar
nice one..:)

Last edit: 2015-03-10 05:17:51
2015-01-04 23:53:01 Kid Algorist
I wonder why fast I/O gives a TLE and scanf/printf ACs in 0.32.
Its generally the other way round.
--Francky--> Maybe because input don't end with EOL, and rather with EOF on the last line.

--Thanks.

Last edit: 2015-01-12 22:08:02
2014-12-26 23:47:02 xiaowuc1
The input data do not conform to the given specification. See submission ID 13276252, which attempts to read in T lines and throws an error if it encounters a NULL string.
2014-05-23 09:21:20 [Lakshman]
Read this in problem statement "even power is strictly greater than odd power"

Last edit: 2014-05-23 09:36:18
2014-05-23 07:58:31 [Lakshman]
@codenite what is your output for this 1875248? for help you can come to forum.

check this :: http://www.spoj.com/forum/viewtopic.php?f=3&t=13097&sid=6e9b0f43deea01262e3f57a3d4f95fab

Last edit: 2014-05-23 07:59:04
2014-05-14 19:36:55 Andy
just inputting and outputting random answer get tle, then how do I solve this?
--ans(Francky)--> I just ran my basic AC code, and it seems that there's no changes. Sorry, I can't help more. What looks like your IO ? (According to your psycho34 code, it should be ok) ???

--andy--> even my fast input got TLE. I tried running my precalculation without I/O, get WA (so I think my algo is sufficient). Then I tried running my I/O without any calculation and get TLE.
If it's OK to ask, what is the intended complexity for this?
--Francky--> Mine was O(N^0.5), 0%-opti.

--andy--> Thank you, finally AC. I think it's probably because I declared 10mil size array (still not sure though). Really didn't think O(n^0.5) will get AC due to 10^6 test case (total 3bil operation worst case)
--Francky--> This mean In_file is weak on that point,...

Last edit: 2014-05-14 21:06:38
2014-05-14 13:00:51 [Lakshman]
@Francky what about new Psycho with n<=10^18.
--ans(Francky)--> I prepare it, in order to allow Python solutions. Do you prefer do it ? I've yet began.

-Lakshman-->I was just thinking, It would be better if you create this new Psycho, I would like to solve that problem in python.

--Francky--> I've set a 10^14 edition (it is enough) ; I think it is hard-tutorial or easy-classical. Let's see. Good luck.

Last edit: 2014-05-14 01:01:10
2014-05-14 13:00:51 Francky
Basic brute force can pass. Problem (and others) moved to tutorial.
Constraints with N<10^18 allow a easy O(N^1/3) solution. This could be make a decent classical problem. This one is moved.

Shipu --> now i want to learn what is the meaning of brute force....... or sqrt root or logn solution.... :/ and why it's moved to tutorial After 1767 submission....... again moved to classical or hidden .....

--ans(Francky)--> It's very annoying you counter EB action. Please trust. This one is a decent tutorial problem, not more. No need to hide it. It isn't a classical problem. If you can't see it, then someone else can set a O(N^1/3) edition. The others one don't have more interest, and can be tutorial or hidden, as you like. Please stop counter EB action ; you were sent several warnings in the past.

Last edit: 2014-05-13 19:13:10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.