Editorial for VOI 12 Bài 4 - Bản vanxơ Fibonacci


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int f[20]={0,1,2};

int cyclic(int u,int v)
{
    int l=v-u+1;
    for (int x=1;x<=l/2;x++)
        if (l%x==0)
        {
            int ok=1;
            for (int i=u+x;i<=v;i++)
                if (f[i%16]!=f[(i-x)%16]) 
                {
                    ok=0; break;
                }
            if (ok) return 1;
        }
    return 0;
}

int calc(int u,int v)
{
    int res=-1;
    if (v-u+1<=100)
    {
        for (int i=u;i<v;i++)
            for (int j=i+1;j<=v;j++)
                if (cyclic(i,j)) 
                    res=max(res,j-i+1);
    }
    else res=(v-u+1)/16*16;
    return res;
}

int main()
{
    int test,u,v;
    for (int i=3;i<=16;i++) f[i%16]=(f[i-1]+f[i-2])%7;

    cin >> test;
    while (test--) cin >> u >> v, cout << calc(u,v) << endl;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include <climits>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>

using namespace std;
int f[111];
int k;
LL u, v;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    f[0] = 1; f[1] = 2;
    FOR(i, 2, 100) f[i] = (f[i - 1] + f[i - 2]) % 7;
    cin >> k;
    while (k--) {
        cin >> u >> v;
        u--; v--;
        LL len = v - u + 1, ans = -1;
        if (len >= 32) ans = len / 16 * 16;
        else {
            u %= 32;
            FOR(i, u, u + len - 1)
            if (f[i] == f[i + 1]) ans = 2;
        }
        cout << ans << '\n';
    }
    return 0;
}

Code mẫu của RR

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

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 1011
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int test,u,v,n;

int main(){
   // freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);

    int x[] = {1, 2, 3, 5, 1, 6, 7, 6, 6, 5, 4, 2, 6, 1, 7, 1, 1, 2, 3, 5, 1, 6, 7, 6, 6, 5, 4, 2, 6, 1, 7, 1, 1, 2, 3, 5, 1, 6, 7, 6, 6, 5, 4, 2, 6, 1, 7, 1};

    scanf("%d",&test);
    for(int itest = 1; itest <= test; itest++){
        scanf("%d %d",&u,&v);
        n = v - u;
        if( n > 30){
            printf("%d\n",((n+1)/16)*16);
        }
        else{
            int t = (u-1)%16;
            bool flag = true;
            for(int i = t; i < t+n; i++){
                if(x[i] == x[i+1]){
                    printf("2\n");
                    flag = false;
                    break;
                }
            }
            if(flag) printf("-1\n");
        }
    }
}

Code mẫu của skyvn97

#include<cstdio>
const int res[]={0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1};
int fib(const int &x) {
    return (res[(x+1)%16]);
}
int count(const int &u,const int &v) {
    if (v-u+1>=32) return (((v-u+1)/16)*16);
    int i;
    for (i=u;i<v;i=i+1)
        if (fib(i)==fib(i+1)) return (2);
    return (-1);
}
int c,u,v,t;
int main(void) {
    scanf("%d",&t);
    for (c=1;c<=t;c=c+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        printf("%d\n",count(u,v));
    }
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.