COLONY - Linearian Colony

no tags 

Description

Linearians are pecurliar creatures. They are odd in several ways:
  1. Every Linearian is either red or blue.
  2. A Linearian colony is a straight line, aligned N-S with the magentic field.
  3. A colony starts with single red Linearian.
  4. Every year, each Linearian produces an offspring of the opposite color. After birth, the parent moves just south of the offspring. (Since everyone is born at once, this does make for a lot of jostling, but everyone stays in order.)
So a colony grows as follows:
N ----------- S

Year 0: R
Year 1: BR
Year 2: RBBR
Year 3: BRRBRBBR
Year 4: RBBRBRRBBRRBRBBR
Given a year and a position along the N-S axis, determine what the color of the Linearian there will be.

Input

The first line is the year Y (0 <= Y <= 51). The second line is the position P from north to south, 0-indexed (0 <= P < 2^Y).

Ouput

The color of the Linearian, either red or blue.
Input Input
3
6
51
123456789012345
Output Output
blue
red

hide comments
nadstratosfer: 2017-07-22 01:45:43

Remember "red" in year 0. Costed me WA.

vengatesh15: 2016-12-31 13:55:14

Thue-Morse Sequence

poda_venna: 2016-08-31 17:14:45

Indian Connection!!

gohanssj9: 2016-07-14 20:01:55

Solving this helps in solving Indian Connection Problem, or solving Indian Connection problem helps in solving this one. Both Ways work.

more_practice: 2016-06-27 21:57:07

1.)
write recursively problem on copy it's very simple
2.)code same as translation of it.
this is example of ques. which is very hard to solve iteratively but fun for recursion.

Last edit: 2016-06-27 22:00:08
utkarsh538: 2016-04-25 11:37:06

just think in opposite manner i.e from Yth year to 0th year.

hkshenoy: 2015-10-26 12:08:01

@sam_29 use pow function instead of bit wise

sam_29: 2015-10-24 21:26:43

Can Anyone tell why i'm getting wrong ans i have checked it for all the edge cases and normal cases also it is giving the correct and but getting wrong ans on 5th test case.
Link to my solution is http://www.spoj.com/submit/COLONY/id=15459950

gajbhiye: 2015-10-01 07:36:25

AC in 1 go!!!

gullu_mishra: 2015-09-17 21:58:39

AC in 1 go... but took time for finding logic...really awsmm prblm... :)


Added by:BYU Admin
Date:2013-10-18
Time limit:0.182s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET