SPOJ.com - Problem PSYCHON

PSYCHON - Psycho

no tags

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 = 2²x 3³x 5⁴.

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 <= 10⁶) denoting the number of test cases followed by T lines. Each containing a single integer N (1 <= N <= 10⁷).

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.

Submit solution!

hide comments

< Previous 1 2 Next >

	Abhinav: 2015-05-20 14:25:51 Finally after 7 WA and 5 Tle ...... AC :)
	Madhav: 2015-04-02 14:18:25 good question!!
	Sayak Haldar: 2015-03-04 20:46:56 nice one..:) Last edit: 2015-03-10 05:17:51
	Kid Algorist: 2015-01-04 23:53:01 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
	xiaowuc1: 2014-12-26 23:47:02 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.
	[Lakshman]: 2014-05-23 09:21:20 Read this in problem statement "even power is strictly greater than odd power" Last edit: 2014-05-23 09:36:18
	[Lakshman]: 2014-05-23 07:58:31 @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
	Andy: 2014-05-14 19:36:55 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
	[Lakshman]: 2014-05-14 13:00:51 @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
	Francky: 2014-05-14 13:00:51 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

Submit solution!

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