Editorial for VM 08 Bài 01 - Bậc thang


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

const max=100000;
var n,k,a,b,c:longint;
    kt:boolean;
    d:array[1..max] of byte;

procedure rf;
var  i:longint;
begin
     readln(n,k);
     fillchar(d,sizeof(d),0);
     kt:=true;
     for i:=1 to k do
     begin
          read(a);
          d[a]:=1;
          if d[a-1]=1 then
          begin
               kt:=false;
               break;
          end;
     end;
end;

procedure pr;
var j,i:longint;
begin
     c:=0;
     if not kt then exit;
     a:=1;
     if d[2]=0 then b:=1 else b:=0;
     c:=a+b;
     for i:=4 to n do
     begin
          a:=b; b:=c;
          if d[i]=0 then c:=(a mod 14062008 + b mod 14062008) mod 14062008
          else c:=0;
     end;
end;

procedure wf;
begin
     write(c);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <cstdio>

int n, k;
int f[100000+5];
bool t[100000+5];

int main() {
    scanf( "%d%d", &n, &k );
    while(k--) { int x; scanf( "%d", &x ); t[x] = true; }
    f[0] = 0; f[1] = 1;
    for( int i = 2; i <= n; ++i )
        f[i] = t[i] ? 0 : ((f[i-1]+f[i-2])%14062008);
    printf( "%d\n", f[n] );
    return 0;
}

Code mẫu của ladpro98

program vsteps;
uses    math;
const   base = 14062008;
var     f:array[0..100000] of longint;
        n,i,k,t:longint;
begin
        readln(n,k);
        for i:=1 to k do
        begin
        read(t);
        f[t]:=-1;
        end;
        f[1]:=1;
        for i:=2 to n do
        begin
                if f[i]=-1 then f[i]:=0
                else
                f[i]:=(f[i-1]+f[i-2]) mod base;
        end;
        write(f[n]);
end.

Code mẫu của RR

const
  base=14062008;
var
  f:array[1..100111] of longint;
  u,n,k,i:longint;
begin
  f[1]:=1;
  read(n,k);
  for i:=1 to k do
    begin
      read(u);
      f[u]:=-1;
    end;

  for i:=2 to n do
    if f[i]>=0 then
      begin
        if f[i-1]>=0 then inc(f[i],f[i-1]);
        if f[i-2]>=0 then inc(f[i],f[i-2]);
        f[i]:=f[i] mod base;
      end;
  writeln(f[n]);
end.

Code mẫu của hieult

#include <stdio.h>
main()
{
long m,n,a[100000],f[100000];
scanf("%ld %ld",&m,&n);
for(long i=1;i<=n;i++)
  scanf("%ld",&a[i]);
a[0]=1; a[n+1]=m; f[1]=1;
for(long i=1;i<=n;i++)
  f[a[i]]=0;
for(long i=0;i<=n;i++)
  for(long j=a[i]+1;j<a[i+1];j++)
    {
    f[j]=f[j-1]+f[j-2];
    if(f[j]>=14062008)
      f[j]=f[j]-14062008;
    }
f[m]=f[m-1]+f[m-2];
if(f[m]>=14062008)
  f[m]=f[m]-14062008;
printf("%ld",f[m]);
}

Code mẫu của ll931110

Program VSTEPS;
        Const
                input  = '';
                output = '';
        Var
                f: array[1..100000] of longint;
                c: array[1..100000] of boolean;
            p,n,k: longint;

Procedure init;
          Var
                fi: text;
               i,s: longint;
          Begin
               Fillchar(c, sizeof(c), false);
               Fillchar(f, sizeof(f), 0);

               Assign(fi, input);
                        Reset(fi);
                        Readln(fi, n, k);
                        For i:= 1 to k do
                                Begin
                                        read(fi, s);
                                        c[s]:= true;
                                End;
               Close(fi);

               f[1]:= 1;         p:= 14062008;
          End;

Procedure optimize;
          Var
                i: longint;
          Begin
                If c[2] then f[2]:= 0 else f[2]:= 1;
                For i:= 3 to n do
                        If c[i] then f[i]:= 0
                                else f[i]:= (f[i - 1] + f[i - 2]) mod p;
          End;

Procedure final;
          Var
                fo: text;
          Begin
                Assign(fo, output);
                        Rewrite(fo);
                        Writeln(fo, f[n]);
                Close(fo);
          End;

Begin
        init;
        optimize;
        final;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   100100
#define MOD   14062008
bool b[MAX];
int f[MAX];
int n,k;
void init(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    int i,x;
    for (i=1;i<=k;i=i+1) {
        scanf("%d",&x);
        b[x]=true;
    } 
}
void optimize(void) {
    int i;
    f[0]=0;
    f[1]=1;
    for (i=2;i<=n;i=i+1)
        f[i]=(f[i-1]*(1-b[i-1])+f[i-2]*(1-b[i-2]))%MOD;
    printf("%d",f[n]);
}
int main(void) {
    init();
    optimize();
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int n, k;
int f[100010], b[100010];

int main() {
    scanf("%d%d", &n, &k);
    for(int i=0;i<k;++i) {
        int x; scanf("%d", &x);
        b[x] = true;
    }
    f[1] = 1;
    for(int i=2;i<=n;++i) if(!b[i]) f[i] = ((i<1?0:f[i-1]) + (i<2?0:f[i-2])) % 14062008;
    cout << f[n] << endl;
    //system("pause");
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.