let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI09 PAGODA - Đường lên Bái Đính

solution.md

Tóm tắt đề:

Cho 3 số A, B, C có cùng độ dài \(N \leq 200000\). Tìm cách hoán vị các chữ số trong C sao cho khi đọc theo chiều từ trái sang phải thì C lớn hơn cả A và B, khi đọc từ chiều phải sang trái thì C nhỏ hơn cả A và B. Đồng thời C phải nhỏ nhất có thể (theo chiều trái sang phải).

Bài này sử dụng đệ quy kết hợp nhánh cận. Chi tiết như sau:

  • Gọi X = max(A, B), so sánh theo chiều từ trái sang phải.
  • Gọi Y = min(A, B), so sánh theo chiều từ phải sang trái.
  • Lần lượt đệ quy để chọn các phần tử của C từ trái sang phải, mỗi lần chọn xong tại một vị trí cần kiểm tra xem với các kí tự còn lại của C, có thể tạo một số bé hơn Y khi đọc theo chiều phải sang trái hay không.
  • Trong khi đệ quy, C cần chọn sao cho nhỏ nhất có thể nhưng vẫn lớn hơn X, nên ta chia làm 2 hàm đệ quy như bên dưới, dq1 cho trường hợp C đang bằng X, dq2 khi C đã lớn hơn X.
main.pas
Open in Github • Download 
type int=longint;
var a,b,c,somax,somin: array[1..200000] of int;
    num: array[0..9] of int;
    n: int;
    ok: boolean;

procedure findmax();
var i: int;
begin
    for i:=1 to n do if a[i]>b[i] then begin
        somax:=a;
        exit();
    end else if a[i]<b[i] then begin
        somax:=b;
        exit();
    end;
    somax:=a;
end;
procedure findmin();
var i: int;
begin
    for i:=n downto 1 do if a[i]>b[i] then begin
        somin:=b;
        exit();
    end else if a[i]<b[i] then begin
        somin:=a;
        exit();
    end;
    somin:=a;
end;

function check(i: int): boolean;
var x: int;
begin
    if (c[i]<>-1) then begin
        if c[i]>b[i] then exit(false);
        if c[i]<b[i] then exit(true);
        exit(check(i-1));
    end;
    for x:=0 to b[i]-1 do if num[x]>0 then exit(true);
    if num[b[i]]=0 then exit(false);
    dec(num[b[i]]);
    check:=check(i-1);
    inc(num[b[i]]);
end;

procedure dq2(i: int);
var x: int;
begin
    if not check(n) then exit();
    if i>n then begin
        ok:=true;
        exit();
    end;
    for x:=0 to 9 do if num[x]>0 then begin
        dec(num[x]);
        c[i]:=x;
        dq2(i+1);
        if ok then exit();
        c[i]:=-1;
        inc(num[x]);
    end;
end;

procedure dq1(i: int);
var x: int;
begin
    if not check(n) then exit();
    if i>n then begin
        ok:=true;
        exit();
    end;
    for x:=a[i] to 9 do if num[x]>0 then begin
        c[i]:=x;
        dec(num[x]);
        if x>a[i] then dq2(i+1)
        else dq1(i+1);
        if ok then exit();
        c[i]:=-1;
        inc(num[x]);
    end;
end;

procedure main();
var i: int;
    t: char;
begin
    readln(n);
    for i:=1 to n do begin
        read(t);
        a[i]:=ord(t)-ord('0');
    end;
    readln();
    for i:=1 to n do begin
        read(t);
        b[i]:=ord(t)-ord('0');
    end;
    readln();
    fillchar(num,sizeof(num),0);
    for i:=1 to n do begin
        read(t);
        inc(num[ord(t)-ord('0')]);
    end;
    findmax();
    findmin();
    a:=somax;
    b:=somin;
    for i:=1 to n do c[i]:=-1;
    dq1(1);
    if ok then begin
        for i:=1 to n do write(c[i]);
    end else writeln(-1);
end;

begin
    main();
end.
Comments