FIBVAL - VOI 2012 Bản vanxơ Fibonacci

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

#define DEBUG(x) { cout << #x << " = "; cout << x << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,0,n) cout << a[_] << ' '; cout << endl; }

using namespace std;

int f[111];
int canDivide[111][111][111], good[111][111], best[111][111];

// canDivide(i,j,x) = can divide (i,j) to equal segments of length x
// good(i,j) = can divide(i,j) to k equals segment, for some k
// best(i,j) = longest good subsequence

int same(int i, int j, int len) {
    while (len--) {
        if (f[i++] != f[j++]) return 0;
    }
    return 1;
}

void init() {
    f[1] = 1; f[2] = 2;
    FOR(i,3,100) f[i] = (f[i-1] + f[i-2]) % 7;
//    PR(f, 100);

    FORD(i,100,1) FOR(j,i,100) {
        int len = j - i + 1;
        FOR(each,1,len-1) {
            if (len % each != 0) canDivide[i][j][each] = 0;
            else {
                int k = len / each;
                if (k == 2) canDivide[i][j][each] = same(i,i+each,each);
                else canDivide[i][j][each] = canDivide[i][j-each][each] && canDivide[i+each][j][each];
            }
            if (canDivide[i][j][each]) good[i][j] = 1;
        }
    }

    FORD(i,100,1)
    FOR(j,i,100) {
        if (good[i][j]) best[i][j] = j - i + 1;
        else best[i][j] = max(best[i+1][j], best[i][j-1]);

        if (best[i][j] == 0) best[i][j] = -1;
    }
}

int solve(int u, int v) {
    int res = -1;
    int len = (v - u + 1);
    if (len >= 32) res = (len / 16) * 16;
    else {
        int saveu = u, savev = v;
        if (len >= 9) res = 2;
        while (v % 8 != 1) --v;
        while (u % 8 != 0) ++u;
        if (u <= v) res = 2;

        u = saveu; v = savev;
    }

    return res;
}

int main() {
//    init();

    int ntest; scanf("%d", &ntest);
    while (ntest--) {
        int u, v; scanf("%d%d", &u, &v);
        printf("%d\n", solve(u, v));
    }
    return 0;
}

Download