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.
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