CRYPTO1 - The Bytelandian Cryptographer (Act I)

no tags 

The infamous Bytelandian Bit-eating Fanatic Organisation (BBFO for short) plans to launch an all-out denial-of-service attack on the Bytelandian McDecimal's fast food network by blocking the entrance to every restaurant with a camel (the purpose being to rid the Organisation of unhealthy competition, obviously). In a sly and perfidious move, the head cryptographer of BBFO decided to disclose the date and time of the planned attack to the management of McDecimal's, but in encrypted form (ha ha). He calculated the number of seconds from midnight 1970.01.01 GMT to the moment of attack, squared it, divided it by 4000000007 and sent the remainder by e-mail to McDecimal's. This made the original date impossible to decode.

Or did it?

*   *   *

You work as the head algorthimist at McDecimal's HQ and know nothing of what is happening in Byteland. Things are not going well. You are playing a quiet game of hearts against your computer and wondering why on earth Management are considering making you redundant. Suddenly, the CEO bursts into your office, saying:

- Look here, young man[lady]! I have this number and those guys claim it is supposed to be some date. I am giving you one second to tell me what it all means!

I am afraid you have no choice. You can't ask any further questions.
You just have to answer, now.

Input

The encrypted timestamp.

Output

The decrypted GMT time and date of attack, somewhere between 1970 and 2030, using standard 26 character formatting.

Example

Input:
1749870067

Output:
Sun Jun 13 16:20:39 2004


hide comments
kethansrinivas: 2016-04-30 15:53:06

four WA for changing code due to strftime displaying wrong output as Sun Jun 13 21:50:39 2004 instead of Sun Jun 13 16:20:39 2004 but got AC when submitted the code for 1st output without any changes in spoj. Its weird how there are differences in output of same code between my compiler and spoj.

mike: 2015-12-07 16:47:35

Be aware of format of time and avoid spelling mistakes of (Thu, Sep ,..etc)..that costed me 2 WA

Last edit: 2016-01-13 18:12:51
Shubham Dash: 2015-12-07 15:21:09

Easy in python

python_user: 2015-10-31 05:35:52

make sure that you use unsigned long long as the data type for the variables!!

Last edit: 2015-10-31 05:36:21
skrishna99: 2015-07-25 06:06:16

can we use tonelli shanks algorithm for this? or any different algorithm is there?

Parth: 2015-05-14 22:16:23

Nice Question !!
Learned modular arithmetic (quadratic congruence)!!

djordje: 2015-02-24 08:35:48

For given input, I have Jun 13 18:20:39 2004 for output (1087143639 in seconds). Is this correct? I see 1087143639 is solution by more users

Hot-Shot: 2014-12-26 15:27:28

yeah it is....
just hav to look up only two values its generates..
ahh learned something new.

sparky: 2014-12-07 10:53:47

Very nice question.
Do not get carried away by all the comments which suggest multiple answers for the same input. For every a^2 mod p, there are either 0 or 2 possible values of a(less than p), and only one of them will lie in the given interval (i.e. whose time is between 1970 and 2030)
THE QUESTION IS WELL-DEFINED

Last edit: 2014-12-07 10:54:42
Baojun Wang: 2014-09-27 20:44:08

SPOJ GHC (6.10) is way too old and seems broken, sometimes is very painful to spend time on unwanted stuff because seems nobody even have GHC 6.10 installed. I got AC with below function to convert time:


--
{-# LANGUAGE ForeignFunctionInterface #-}
import Foreign
import Foreign.C.Types
import Foreign.C.String
foreign import ccall unsafe "strftime" c_strftime :: CString -> CSize -> CString -> Ptr CULong -> IO CSize
foreign import ccall unsafe "gmtime" c_gmtime :: Ptr CULong -> IO (Ptr CULong)


utctime t = alloca $ \intptr -> do
poke intptr t
fp <- newForeignPtr_ intptr
withForeignPtr fp $ \p -> do
tm <- c_gmtime p
fmt <- newCString "%a %b %e %H:%M:%S %Y"
allocaBytes 64 $ \s -> do
r <- c_strftime s 64 fmt tm
peekCString s

Last edit: 2014-09-28 01:31:48

Added by:adrian
Date:2004-05-13
Time limit:1s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL 6 VB.net
Resource:;)