Editorial for Số hiệu hoán vị


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=12;
      fact:array[1..12] of longint=(1,2,6,24,120,720,5040,40320,362880,
      3628800,39916800,479001600);
var n:byte;
    k:longint;
    a,d:array[1..max] of byte;
{‘‘‘‘‘‘‘‘‘‘‘‘‘‘}
procedure re;
var t:byte;
begin
     n:=0;
     while not seekeoln do
     begin
        inc(n);
        read(t);
        a[n]:=t;
     end;
     readln;
     read(k);
end;
{‘‘‘‘‘‘‘‘‘‘‘‘‘‘}
procedure timhv;
var i,j,dem:byte; t,r:longint;
begin
     fillchar(a,sizeof(a),0);
     fillchar(d,sizeof(d),0);
     for i:=1 to n-1 do
     begin
          r:=fact[n-i];
          t:=(k+r-1) div r;
          k:=k-(t-1)*r;
          dem:=0;
          while t>0 do
          begin
               inc(dem);
               if d[dem]=0 then dec(t);
          end;
          a[i]:=dem;
          d[dem]:=1;
     end;
     r:=n*(n+1) div 2;
     for i:=1 to n-1 do r:=r-a[i];
     a[n]:=r;
     for i:=1 to n do write(a[i],' ');
end;
{‘‘‘‘‘‘‘‘‘‘‘‘‘‘}
procedure doihv;
var i,j,dem:byte; t,r,k1:longint;
begin
     k1:=0;
     for i:=1 to n-1 do
     begin
          dem:=0;
          for j:=1 to i-1 do
              if a[j]<a[i] then inc(dem);
          r:=fact[n-i];
          k1:=k1+r*(a[i]-dem-1);
     end;
     writeln(k1+1);
end;
{&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;&#8216;}
begin
     re;
     doihv;
     timhv;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>
#include<cstdlib>

char s[100];
int a[15], used[15];

int factorial(int n) {
    int res = 1;
    for(int i = 2; i <= n; ++i) res *= i;
    return res;
}

int main() {
    gets(s); int n = 0;
    for(char * buf = strtok(s, " "); buf != NULL; buf = strtok(NULL, " "))
        a[n++] = atoi(buf);
    int p = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 1; j < a[i]; ++j)
            if(used[j] == 0) p += factorial(n-i-1);
        used[a[i]] = 1;
    }
    printf("%d\n", p + 1);
    scanf("%d", &p);
    memset(used, 0, sizeof used);
    for(int i = 0; i < n; ++i) {
        if(i) printf(" ");
        for(int v = 1; v <= n; ++v)
            if(used[v] == 0) {
                if(p > factorial(n-i-1)) p -= factorial(n-i-1);
                else {
                    printf("%d", v); used[v] = 1;
                    break;
                }
            }
    }
}

Code mẫu của ladpro98

program shhv;
uses    math;
const   fi='';
var     inp:text;
        n,i,t,j,k,p:longint;
        a,f:array[0..20] of longint;
        check:array[0..20] of boolean;
begin
        assign(inp,fi);reset(inp);
        while not seekeoln(inp) do
        begin
                inc(n);
                read(inp,a[n]);
        end;
        readln(inp,p);
        f[1]:=1;
        for i:=2 to n do f[i]:=i*f[i-1];
        k:=0;
        for i:=1 to n do
        begin
                t:=0;
                for j:=1 to a[i]-1 do
                if not check[j] then inc(t);
                inc(k,f[n-i]*t);
                check[a[i]]:=true;
        end;
        writeln(k+1);
        for i:=1 to n do check[i]:=false;
        for i:=1 to n do
        begin
                for j:=n-1 downto 0 do
                begin
                        t:=0;
                        for k:=1 to j do if not check[k] then inc(t);
                        if (not check[j+1]) and (t*f[n-i]<p) then break;
                end;
                write(j+1,' ');
                check[j+1]:=true;
                dec(p,t*f[n-i]);
        end;
end.

Code mẫu của RR

const
  MAXN=12;
var
  now,j,i,n,res:longint;
  a:array[1..MAXN] of longint;
  used:array[1..MAXN] of boolean;
  gt:array[0..MAXN] of longint;
begin
  gt[0]:=1; for i:=1 to MAXN do gt[i]:=gt[i-1]*i;

  while not seekeoln do
    begin
      inc(n);
      read(a[n]);
    end;

  fillchar(used,sizeof(used),false);
  now:=n-1;
  for i:=1 to n do
    begin
      j:=1;
      while (j<a[i]) do
        begin
          if not used[j] then inc(res,gt[now]);
          inc(j);
        end;
      used[j]:=true;
      dec(now);
    end;
  writeln(res+1);

  fillchar(used,sizeof(used),false); now:=n-1;

  readln(res); dec(res);
  for i:=1 to n do
    begin
      j:=1;
      while res>=gt[now] do
        begin
          if not used[j] then dec(res,gt[now]);
          inc(j);
        end;
      while used[j] do inc(j);
      write(j,' ');
      used[j]:=true; dec(now);
    end;
  writeln;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <iostream>
main()
{
char ch,ch1;      
long t=0,c[13],a[13],KQ=0,x;
while(scanf("%c",&ch)>0&&ch!='\n')
  {                                                           
  if(ch!=' ')
    {
    if(ch=='1')
      {
      scanf("%c",&ch1);
      if(ch1==' ')
        {
        t++;
        a[t]=1;
        }
      else
        {
        t++;
        a[t]=10+ch1-48;
        }
      }    
    else
      {             
      t++;
      a[t]=ch-48;
      }
    }
  }
//for(long i=1;i<=t;i++)
  //printf("%ld ",a[i]);
c[0]=1;
for(long i=1;i<=t;i++)
  c[i]=c[i-1]*i;
for(long i=1;i<=t;i++)
  {
  KQ=KQ+(a[i]-1)*c[t-i];
  for(long j=i+1;j<=t;j++)
    if(a[j]>a[i])
      a[j]--;
  }
printf("%ld\n",KQ+1);  
scanf("%ld",&x);
x=x-1;
for(long i=1;i<=t;i++)
  a[i]=i;
for(long i=1;i<=t;i++)
  {
  long n=x/c[t-i];
  printf("%ld ",a[n+1]);
  for(long j=n+1;j<=t-i;j++)
    a[j]=a[j+1];
  x=x%c[t-i];
  }
//getch();
}

Code mẫu của ll931110

Program SHHV;
        Const
                input  = '';
                output = '';
        Var
              a,d: array[1..12] of byte;
                v: array[1..12] of longint;
                c: array[1..12] of boolean;
                n: integer;
                p: longint;

Procedure init;
          Var
                f: text;
                i: byte;
          Begin
                Assign(f, input);
                        Reset(f);
                        n:= 0;
                        While not SeekEoln(f) do
                                Begin
                                        inc(n);
                                        read(f, a[n]);
                                End;
                        For i:= 1 to n do dec(a[i]);
                        Readln(f, p);
                Close(f);

                v[1]:= 1;
                For i:= 2 to 12 do v[i]:= v[i - 1] * i;

                Fillchar(c, sizeof(c), true);
          End;

Function sovarr: longint;
         Var
                i,j: byte;
                  x: longint;
         Begin
                x:= 1;
                For i:= 1 to n - 1 do
                        Begin
                                x:= x + a[i] * v[n - i];
                                For j:= i + 1 to n do if a[j] > a[i] then dec(a[j]);
                        End;
                sovarr:= x;
         End;

Procedure sovnum;
          Var
                i,t,k,j: byte;
          Begin
                For i:= 1 to n - 1 do
                        Begin
                          If p = 0 then
                                Begin
                                        j:= i;
                                        k:= 1;
                                        For k:= n downto 1 do if c[k] then
                                                Begin
                                                        d[j]:= k;
                                                        inc(j);
                                                End;
                                        exit;
                                End
                         else
                           Begin
                             t:= p div v[n - i];
                             If p mod v[n - i] <> 0 then inc(t);

                             k:= 1;
                             While t > 0 do
                                   Begin
                                        If c[k] then dec(t);
                                        If t > 0 then inc(k);
                                   End;

                             d[i]:= k;
                             c[k]:= false;

                             t:= p div v[n - i];
                             p:= p - t * v[n - i];
                           end;
                        End;
                For i:= 1 to n do if c[i] then d[n]:= i;
          End;

Procedure printresult;
          Var
                f: text;
                i: byte;
          Begin
                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, sovarr);
                        sovnum;
                        For i:= 1 to n do write(f, d[i], ' ');
                Close(f);
          End;

Begin
        init;
        printresult;
End.

Code mẫu của khuc_tuan

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] tmp = sc.nextLine().split(" ");
        int n = tmp.length;
        int p = sc.nextInt();
        int[] a = new int[n];
        int[] gt = new int[13];
        for (int i = 0; i < gt.length; ++i)
            gt[i] = i == 0 ? 1 : i * gt[i - 1];
        for (int i = 0; i < n; ++i)
            a[i] = Integer.parseInt(tmp[i]);
        int r = 0;
        for (int i = 0; i < n; ++i) {
            for (int t = 1; t < a[i]; ++t) {
                boolean co = false;
                for (int j = 0; j < i; ++j)
                    if (a[j] == t)
                        co = true;
                if (!co)
                    r += gt[n - i - 1];
            }
        }
        System.out.println(r + 1);
        for (int i = 0; i < n; ++i) {
            for (int t = 1; t <= n; ++t) {
                boolean co = false;
                for (int j = 0; j < i; ++j)
                    if (a[j] == t)
                        co = true;
                if (!co) {
                    if (p <= gt[n - i - 1]) {
                        a[i] = t;
                        break;
                    } else
                        p -= gt[n - i - 1];
                }
            }
        }
        for (int i = 0; i < n; ++i)
            System.out.print(i == 0 ? a[i] : (" " + a[i]));
        System.out.println();
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.