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;
}