Editorial for VOI 07 Bài 1 - Dãy con không giảm dài nhất
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
var n:integer; a:array[1..10000] of longint; d:array[1..10000] of integer; procedure rf; var i:integer; begin readln(n); for i:=1 to n do readln(a[i]); end; procedure pr; var i:integer; t:longint; begin fillchar(d,sizeof(d),0); for i:=1 to n do begin t:=trunc(sqrt(2*a[i])); if t*(t+1)=2*a[i] then begin if a[i]>=a[i-1] then d[i]:=d[i-1]+1 else d[i]:=1; end; end; end; procedure wf; var i,max:integer; begin max:=0; for i:=1 to n do if d[i]>max then max:=d[i]; write(max); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <algorithm> #include <cstdio> #include <cmath> using namespace std; #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define N 10005 int seq[N], a[N], n; int inZ( double db ) {return db == floor(db);} int main() { scanf( "%d", &n ); fo(i,1,n) scanf( "%d", a+i ); seq[0] = -1; int res = 0; fo(i,1,n) if(inZ((-1+sqrt(1+8*a[i]))/2)) { if( seq[i-1] != -1 && a[i-1] <= a[i] ) seq[i] = seq[i-1] + 1; else seq[i] = 1; if(seq[i] > res) res = seq[i]; } else seq[i] = -1; printf( "%d\n", res ); return 0; }
Code mẫu của ladpro98
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; int n, now, ans; int a[100000]; bool ok(int x) { x += x; int y = sqrt(x); return y * (y + 1) == x; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n; int ans = 0; for(int i = 1; i <= n; i++) { cin >> a[i]; if (a[i] < a[i - 1]) now = 0; if (ok(a[i])) now++; else now = 0; ans = max(ans, now); } cout << ans; return 0; }
Code mẫu của RR
uses math; var res,i,n:longint; a,f:array[0..10111] of longint; function check(i:longint):boolean; var n:longint; begin i:=i*2; n:=trunc(sqrt(i)); exit( n*(n+1) = i ); end; begin read(n); for i:=1 to n do read(a[i]); for i:=1 to n do if check(a[i]) then begin if a[i]>=a[i-1] then f[i]:=f[i-1]+1 else f[i]:=1; end else f[i]:=0; for i:=1 to n do res:=max(res,f[i]); writeln(res); end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> #include <math.h> int check(int k) { int n = int(sqrt(2*k)); if(n*(n+1)/2 == k) return 1; else return 0; } int main() { int n,a[10001],t=0,max = 0; scanf("%d",&n); for(int i = 1;i<=n;i++) { scanf("%d",&a[i]); if(check(a[i])==1) { if(a[i]>=a[i-1]) t++; else t = 1; } else t = 0; if(t>max) max = t; } printf("%d",max); //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program QBMSEQ; Const input = ''; output = ''; maxn = 10000; maxv = 10000 * 10000; Var a: array[1..maxn] of integer; k: array[1..15000] of integer; n,max,num: integer; Procedure init; Var f: text; i: integer; Begin Assign(f, input); Reset(f); Readln(f, n); For i:= 1 to n do readln(f, a[i]); Close(f); End; Procedure gens; Begin k[1]:= 1; num:= 1; While k[num] < maxv do Begin inc(num); k[num]:= k[num - 1] + num; End; End; Function search(x: integer): boolean; Var inf,sup,mid: integer; Begin inf:= 1; sup:= num; Repeat mid:= (inf + sup) div 2; If k[mid] = x then exit(true) else if k[mid] < x then inf:= mid + 1 else sup:= mid - 1; Until inf > sup; search:= false; End; Procedure solve; Var i,curr: integer; Begin max:= 0; curr:= 0; For i:= 1 to n do If search(a[i]) then Begin If curr = 0 then curr:= 1 else If a[i] >= a[i - 1] then inc(curr) else curr:= 1; If max < curr then max:= curr; End else curr:= 0; End; Procedure printresult; Var f: text; Begin Assign(f, output); Rewrite(f); Writeln(f, max); Close(f); End; Begin init; gens; solve; printresult; End.
Code mẫu của skyvn97
Code mẫu của khuc_tuan
#include <iostream> using namespace std; int ds[100000], nd; int n, a[100000]; bool ok[100000]; int main() { for(int i=1, s=0;;++i) { s += i; if(s>100000000) break; ds[nd++] = s; } scanf("%d", &n); for(int i=0;i<n;++i) { scanf("%d", a+i); ok[i] = binary_search( ds, ds+nd, a[i]); } int res = 0; for(int i=0;i<n;++i) if(ok[i]) { int j = i; while(j+1<n && ok[j+1] && a[j+1]>=a[j]) ++j; res >?= (j-i+1); i = j; } printf("%d\n", res); //system("pause"); return 0; }
Comments