INTER - Intercept

Long long ago, so long ago, no body knows how long ago, there was a huge galactic war. There was a very powerful general, General Ramuk, who had every possible soldier and scientist under him. One of his scientists reports that he had intercepted a transmission that he believes is from the aliens. A group of experienced cryptographers believe that in the following hypotheses:

  1. The aliens follow use binary system for representing numbers
  2. Their '0' should be interpreted as '1' and vice-versa
  3. The message is encoded as follows: [32bits of n1][16bits of n2][n2 bits of n3]
  4. The retransmission they expect is: [32bits of the remainder] when n3 is divided by n1.
  5. All the numbers are written, Most significant bit first.
  6. Remainder must be communicated in the following format:
    [remainder for 1st instance]
    [remainder for 2nd instance]
    in their own number system, without leading '1's ('0's).
  7. The number of instances is about 200.

The first transmission was completed. Ramuk is eagerly waiting for the second transmission, which must be replied. Being such a simple problem, he asks you to write a program to do the same.

He says: "Nee evalovu chinnadha codea ezhudhariyo avalovu parisu onnakku kaathhirriku ", which translates to: "The smaller the code you write, that much reward is awaiting you...".

You want to save the world from a probable Alien Invasion, and get as much money as possible.

Constant bit length numbers will be prefixed by '1's ('0's in their notation).


The scoring for this problem is the length of the source code.

Sample Input

NOTE: The colons (:) and newlines are for clarity

The actual input will be like:

(new line is again, for clarity)

Sample Output




Warning: Large Input.

Added by:Vimal
Time limit:3.619s
Source limit:500B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET
Resource:Own Problem

hide comments
2014-05-28 03:06:36 Linghui Liu
@hallvabo, thank you. I'm looking forward to your C submissions.

@piotr, you might update the score of DEC_BIN in the links page :p
2014-05-27 13:33:41 Hallvard Norheim Bø
@llhuii: that one looks hard to beat in C!
You can get a good score and 1st spot in C on main SPOJ, best score there is 152 by Bin Jin.

@piotr: I think the C highscore list might need an update soon :p

Last edit: 2014-05-27 13:37:21
2012-07-18 22:35:37 Hallvard Norheim Bø
There is something very strange going on with the "updated" Python version here. Replacing a ';' with a '\n' suddenly changed my solution from NZEC to AC?!?

edit: looks like it has something to do with using exec.
edit2: and now it suddenly worked? *sigh*

Last edit: 2012-07-19 04:49:51
2012-01-10 11:42:04 weltfremd
Took me quite a while to figure out that I couldn't use signed 32-bit ints for n1.
Lucky I made it. :)

EDIT: Forgot to mention there's an error in the second example. n2 is 19, not 20

Last edit: 2012-01-21 18:05:17
2010-11-12 11:37:02 Piotr KÄ…kol
@HWK - Now we have to wait for the response. ;-)
2010-11-11 18:32:46 HWK
My last solution was written with Python 2.6. Now I saved some bytes in a new solution. But I can't post it because Python 2.6 is replaced with 3.1.2. Could you upgrade Python 2.5 to 2.6? Then the old 2.5- and 2.6-programs should run.
2010-07-18 09:15:32 Piotr KÄ…kol
I don't know. You may contact Vimal and ask him again to lengthen time limit. (I won't write him again because I don't want to be importunate)
2010-07-17 16:59:28 Zoltán Zámbori
How can i calculate it?

Last edit: 2010-07-17 17:00:18
2010-07-17 14:15:34 Piotr KÄ…kol
I wrote to author of the task. Is 10s enought?
2010-07-16 19:34:03 Zoltán Zámbori
Time limit is too small for my ~100 bytes Ruby code.
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.