Description
Linearians are pecurliar creatures. They are odd in several ways:
- Every Linearian is either red or blue.
- A Linearian colony is a straight line, aligned N-S with the magentic field.
- A colony starts with single red Linearian.
- 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 |
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll y,p;
int main()
{
ll sum =1;
cin >> y>>p;
p++;
for(int i=1;i<=y;i++)
sum*=2;
int flag = 0;
ll l=1,r=sum;
while(l<r)
{
ll mid = (l+r)/2;
if(p<=mid)
{
flag ++;
r = mid;
}
else
{
l = mid+1;
}
}
//cout <<l<<r<< flag <<endl;
if(flag%2)
cout <<"blue"<<endl;
else
cout <<"red"<<endl;
return 0;
}