Editorial for Chuỗi hạ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

const maxn=255;
      base=1000000000;
      dg=9;
type bignum=array[0..20] of longint;
var n,re,i,j,t:longint;
    f:array[1..maxn,1..maxn*2] of bignum;
    d:array[0..maxn] of longint;
    a:bignum;
    s,st:string;
    code:integer;

procedure plus(var a,b,c:bignum);
var i,mem,max:longint;
begin
     mem:=0;
     if b[0]>c[0] then max:=b[0] else max:=c[0];
     for i:=1 to max do
         if b[i]+c[i]+mem>=base then
         begin
              a[i]:=(b[i]+c[i]+mem) mod base;
              mem:=1;
         end
         else
         begin
              a[i]:=b[i]+c[i]+mem;
              mem:=0;
         end;
     if mem=1 then
     begin
          inc(max);
          a[max]:=1;
     end;
     a[0]:=max;
end;

procedure minus(var a,b,c:bignum;z:longint);
var i,mem:longint;
begin
     mem:=0;
     for i:=1 to b[0] do
         if b[i]-c[i]-mem>=0 then
         begin
              a[i]:=b[i]-c[i]-mem;
              mem:=0;
         end
         else
         begin
              a[i]:=b[i]+base-c[i]-mem;
              mem:=1;
         end;
     a[0]:=b[0];
     while (a[a[0]]=0) and (a[0]>1) do dec(a[0]);
     if z=0 then exit;
     mem:=1;
     for i:=1 to a[0] do
         if a[i]+mem=base then
         begin
              a[i]:=0;
              mem:=1;
         end
         else
         begin
              inc(a[i]);
              mem:=0;
              break;
         end;
     if mem=1 then
     begin
          inc(a[0]);
          a[a[0]]:=1;
     end;
end;

procedure put(var a,b:bignum);
var i:longint;
begin
     for i:=0 to b[0] do a[i]:=b[i];
end;

function small(var a,b:bignum):boolean;
var i:longint;
begin
     small:=true;
     if a[0]<b[0] then exit;
     if a[0]>b[0] then
     begin
          small:=false;
          exit;
     end;
     for i:=a[0] downto 1 do
     begin
          if a[i]<b[i] then exit;
          if a[i]>b[i] then
          begin
               small:=false;
               exit;
          end;
     end;
end;

begin
     readln(n);
     readln(s);
     a[0]:=(length(s)+dg-1) div dg;
     for i:=1 to a[0]-1 do
     begin
          st:=copy(s,length(s)-i*dg+1,dg);
          val(st,a[i],code);
     end;
     t:=length(s) mod dg;
     if t=0 then t:=dg;
     st:=copy(s,1,t);
     val(st,a[a[0]],code);

     f[n,n*2,0]:=1; f[n,n*2,1]:=1;
     for j:=n*2-1 downto n do
     begin
          f[n,j,0]:=1;
          f[n,j,1]:=2*n-j+1;
     end;
     for i:=n-1 downto 1 do
     begin
          put(f[i,i*2],f[i+1,i*2+1]);
          for j:=i*2-1 downto i do
              plus(f[i,j],f[i+1,j+1],f[i,j+1]);
     end;

     minus(a,f[1,1],a,1);
     for i:=1 to n do
         for j:=i*2 downto d[i-1]+1 do
             if small(a,f[i,j]) then
             begin
                  d[i]:=j;
                  minus(a,a,f[i,j+1],0);
                  break;
             end;

     for i:=1 to n do write(d[i],' ');
end.

Code mẫu của happyboy99x

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

const int N = 250 + 5, BASE = 1000000000, MAX_DIGIT = 30, LOG_BASE = 9;
struct BigInteger {
    int d[MAX_DIGIT], n;

    void operator = (const int &x) {
        memset(d, 0, sizeof d); n = 0;
        for(int t = x; t != 0; t /= BASE)
            d[n++] = t % BASE;
    }

    bool operator < (const BigInteger &a) const {
        if(n < a.n) return true;
        if(n > a.n) return false;
        for(int i = n-1; i >= 0; --i)
            if(d[i] < a.d[i]) return true;
            else if(d[i] > a.d[i]) return false;
        return false;
    }

    void operator += (const BigInteger &a) {
        int rem = 0; n = max(n, a.n);
        for(int i = 0; i < n; ++i) {
            int p = d[i] + a.d[i] + rem;
            if(p >= BASE) d[i] = p - BASE, rem = 1;
            else d[i] = p, rem = 0;
        }
        if(rem) d[n++] = rem;
    }

    void operator -= (const BigInteger &a) {
        int rem = 0;
        for(int i = 0; i < n; ++i) {
            int p = d[i] - a.d[i] - rem;
            if(p < 0) d[i] = p + BASE, rem = 1;
            else d[i] = p, rem = 0;
        }
        while(n > 0 && d[n-1] == 0) --n;
    }

    void scan() {
        string s; cin >> s; int l = s.size();
        reverse(s.begin(), s.end());
        memset(d, 0, sizeof d);
        for(n = 0; LOG_BASE * n < l; ++n)
            for(int j = min(LOG_BASE * (n+1), l) - 1; j >= LOG_BASE * n; --j)
                d[n] = d[n] * 10 + s[j] - '0';
    }
} f[N][2*N];

int main() {
    int n; BigInteger x;
    scanf("%d", &n); x.scan();
    for(int v = 2*n; v >= n; --v) f[n][v] = 1;
    for(int p = n-1; p >= 1; --p)
        for(int v = 2*p; v >= p; --v)
            for(int nv = 2*(p+1); nv > v; --nv)
                f[p][v] += f[p+1][nv];
    for(int p = 1, v = 1; p <= n; ++p, ++v) {
        while(f[p][v] < x) x -= f[p][v], ++v;
        if(p > 1) printf(" ");
        printf("%d", v);
    }
    printf("\n");
    return 0;
}

Code mẫu của RR

{$R+,Q+}
program CHUOIHAT;
uses
  math;
const
  FINP='';
  FOUT='';
  MAXN=251;
  oo=100000000;
type
  bigNum=array[0..100] of longint;
var
  n:longint;
  c:array[1..MAXN,0..MAXN*2] of bigNum;
  k:bigNum;
procedure inp;
var
  f:text;
  s:string;
  code:integer;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  readln(f,s);
  while length(s)>8 do
    begin
      inc(k[0]);
      val(copy(s,length(s)-7,8),k[k[0]],code);
      s:=copy(s,1,length(s)-8);
    end;
  inc(k[0]);
  val(s,k[k[0]],code);
  close(f);
end;
operator +(a,b:bigNum) c:bigNum;
var
  nho,i:integer;
begin
  fillchar(c,sizeof(c),0);
  c[0]:=max(a[0],b[0]);
  nho:=0;
  for i:=1 to c[0] do
    begin
      c[i]:=a[i]+b[i]+nho;
      nho:=c[i] div oo;
      c[i]:=c[i] mod oo;
    end;
  if nho>0 then begin inc(c[0]); c[c[0]]:=nho; end;
end;
procedure tru(var a:bigNum;b:bigNum);
var
  nho,i:integer;
begin
  nho:=0;
  for i:=1 to a[0] do
    begin
      a[i]:=a[i]-b[i]-nho;
      if a[i]<0 then
        begin
          nho:=1;
          a[i]:=a[i]+oo;
        end
      else nho:=0;
    end;
  for i:=a[0] downto 1 do if a[i]<>0 then break;
  a[0]:=i;
end;
operator >=(a,b:bigNum) c:boolean;
var
  i:integer;
begin
  if a[0]>b[0] then begin c:=true; exit; end;
  if b[0]>a[0] then begin c:=false; exit; end;
  for i:=a[0] downto 1 do
    begin
      if a[i]>b[i] then begin c:=true; exit; end;
      if b[i]>a[i] then begin c:=false; exit; end;
    end;
  c:=true;
end;
procedure solve;
var
  i,j:integer;
begin
  for j:=n to n*2 do
    begin
      c[n,j,0]:=1;
      c[n,j,1]:=1;
    end;
  for i:=n-1 downto 1 do
    begin
      c[i,i*2+1]:=c[i+1,i*2+2];
      for j:=i*2 downto i do
        c[i,j]:=c[i+1,j+1]+c[i,j+1];
    end;
end;
procedure ans;
var
  f:text;
  i,j,jj:integer;
begin
  assign(f,FOUT); rewrite(f);
  jj:=0;
  for i:=1 to n do
    begin
      for j:=jj+1 to 2*i do
        if c[i,j]>=k then break else tru(k,c[i,j]);
      write(f,j,' '); jj:=j;
    end;
  close(f);
end;
begin
  inp;
  solve;
  ans;
end.

Code mẫu của khuc_tuan

n=input()
X=input()
F=[[0 for _x in range(2*n+1)] for _y in range(n+1)]
a=[0 for _x in range(n+1)]
for k in range(1,2*n+1): F[n][k]=1
for i in range(n-1,0,-1):
    F[i][2*i]=F[i+1][2*i+1]+F[i+1][2*i+2]
    for j in range(2*i-1,0,-1): F[i][j]=F[i][j+1]+F[i+1][j+1]
def truyvet(i,j,X):
    if(i<=n):
        for k in range(j+1,2*n+1):
            if F[i][k]>=X:
                a[i]=k
                truyvet(i+1,k,X)
                return
            else: X-=F[i][k]

truyvet(1,0,X)
for i in range(1,n+1): print a[i],

Comments

Please read the guidelines before commenting.


There are no comments at the moment.