[hankerrank]Counter game

https://www.hackerrank.com/contests/w8/challenges/counter-game

关键是二分查找等于或最接近的小于target的数。可以使用和mid+1判断来比较~ 另有一种做法如下：

http://*.com/questions/6553970/find-the-first-element-in-an-array-that-is-greater-than-the-target

#include <iostream>
#include <vector>
using namespace std;

uint64_t nextN(uint64_t N, vector<uint64_t> &vec) {
    int left = 0;
    int right = vec.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (vec[mid] == N) {
            return N / 2;
        } else if (vec[mid] > N) {
           right = mid - 1;
        } else {
           if (N < vec[mid + 1]) {
               return (N - vec[mid]);
           }
           left = mid + 1;
        }
    }
    return (N - vec[(left + right) / 2]);
}

int main() {
    int T;
    cin >> T;
    vector<uint64_t> vec;
    uint64_t p = 1;
    for (int i = 0; i < 64; i++) {
        vec.push_back(p);
        p *= 2;
    }
    while (T--) {
        uint64_t N;
        cin >> N;
        int move = 0;
        while (N != 1) {
            move++;
            N = nextN(N, vec);
        }
        if (move % 2 == 0) {
            cout << "Richard" << endl;
        } else {
            cout << "Louise" << endl;
        }
    }
    return 0;
}