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.

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

Please read the guidelines before commenting.


There are no comments at the moment.