ilovelife

 

var f,g:text;

    s1,s2,s:string;

    i,j:integer;

begin

assign(f,'');

reset(f);

assign(g,'');

rewrite(g);

 while not eoln(f) do

       begin

       readln(f,s1);

       readln(f,s2);

       i:=1;

       repeat

        if length(s2)>length(s1) then

           begin

             s:=s2;

             s2:=s1;

             s1:=s;

           end;

        if s1[i]<>s2[i] then insert(s1[i],s2,i);

        i:=i+1;

       until pos(s2,s1)<>0;

       writeln(g,s1);

       end;

 close(f);

 close(g);

 end.

 

 Bạn điền tên file inp,out vào là đc! Nếu có thể thêm thì xét trường hợp 2 xâu chả có gì liên quan(vd: abcg,def => abcgdef), vì text của cách mình không có chia cho trường hợp đó!

 

Bài toán quy hoạch động cổ điển: tham khảo  Levenshtein distance

Sẵn cũng có 1 bài về xâu mà làm chưa ra, đăng lên cùng làm :

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.

Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.

Dữ liệu vào

Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.

Kết qủa

Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ.

Giới hạn

Chuỗi s có độ dài không vượt quá 2000.

Ví dụ

Dữ liệu mẫu
lmevxeyzl

Kết qủa
level
 

Bài toán quy hoạch động cổ điển: tham khảo LCS

P/S: là test chứ không phải text nhé.

Sự may mắn có cơ sở

aoqua.png

Em nghĩ có  thể giải bài này bằng decision tree + pruning search. (Xin lỗi em hiện tại hơi bận nên chưa nên không có ngay "sản phẩm")

Chứng minh cần tối đa 7 lần: thử tất cả các trường hợp ? (em nghĩ nó chưa phải cách hay, tốn thời gian)

Chứng minh rằng tích của số tự nhiên có $k$ chữ số với số tự nhiên có $n$ chữ số thì có $k+n$ hoặc $k+n-1$ chữ số.

$A_k \times A_n < 10^{k + 2} \times (10^{n + 2} - 1) = A_{n + k + 1}$
Chứng minh tương tự $A_k \times A_n > A_{n + k - 2}$

Note: Gọi $A_k$ là số có $k$ chữ số

ok! vậy là chu vi nhỏ nhất khi nó là hình vuông

Không phải lúc nào cũng như vậy:
Ví dụ: 10 thì chu vi nhỏ nhất sẽ là 7 x 2

Nói cách khác nếu $n$ là số chính phương thì $a = b = \sqrt n$

$a = b = \left \lfloor \sqrt n  \right \rfloor$ // phần nguyên của căn $n$

while $a * b < n$:

       $a++$

       if $a * b < n$:

             $b++$

# Mình chưa kiểm tra, có thể sửa cái while kia = if luôn mà không gây ảnh hưởng

Giải phương trình nghiệm nguyên dương $m,n$ thỏa mãn:

$n^2-7n+16=2.3^m$

Xét đồng dư cho 2 $\implies  n = 2k$. Xét đồng dư cho 3 $\implies k = 3h + 1$, dễ suy ra kết quả bài toán (Xét đồng dư cho $9$)