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ố

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$)

ừ, bạn thử làm theo cách toán học xem: tìm min a+b khi biết ab>=n;

Lâu lâu lên VMF, thấy forum thuật toán hay hay, vào phá đám chút.
Có thể chứng minh: $\text{minimize}\{a + b\} \text{with } a \times b = n \iff \text{minimize}\{|a - b|\}$ (hình như bạn làm theo cách này)

Time complexity: $O(1)$

Một bài đơn giản:
Phân tích số $\frac{a}{b}$ dưới dạng ($k$ càng nhỏ càng tốt):
$$\frac a b = \sum_{i=1}^{k} \frac 1 {M_k} = \frac 1 {M_1} + \frac 1 {M_2} + ... + \frac 1 {M_k}$$

Thêm một bài này nữa:

Cho tập số tự nhiên $A$ chứa $n$ số tự nhiên, n dòng dạng

i j x

tức $A_i - A_j \ge x$

Tìm một tập nghiệm thoả mãn, nếu không có in ra IMPOSSIBLE

Có bao nhiêu số có 6 chữ số khác nhau mà trong đó 2 chữ số kề nhau không thể là số lẻ

Mình không hiểu điều kiện này.

--------------------------------------

Kết quả (chỉ kết quả) (mang tính tham khảo): https://ideone.com/OoMLpn (edited, nhầm đề)

Cho một bàn cờ $3 \times 4$ được đánh số như sau:

\begin{matrix}
1 & 2 & 3\\
4 & 5 & 6\\
7 & 8 & 9\\
10 & 11 & 12\\
\end{matrix}

Dòng đầu đặt 3 mã đen, dòng cuối đặt 3 mã trắng. Hỏi cần ít nhất bao nhiêu lượt để chuyển đổi chỗ mã trắng và đen ?

Bài toán tương đương với:
Tìm $min$ của $\frac{\left( \sum kx_k \right) \left( \sum x^2_k \right)}{ \left( \sum x_k \right)^3 }$
[...]
Do có một số vấn đề, em chưa chắc chắn với lời giải của mình (em sẽ post sau), nhưng mọi người thử xem kết quả:
 
$C(n) = \frac{2 (n+1) (2n-1)- 2 \sqrt {2n+2}} {9 n (n-1)}$ có đúng không ?

Bài giải của em không dùng đại số thuần túy nên em sẽ post lời giải sau

Với $a \in [2,6],\ b \in [3,7],\ c \in [4,8]$, tính số nghiệm nguyên của phương trình (không tính các hoán vị):
$1.\ \ \ a + b + c = 18 $

$2.\ \ \ a + b + c = k   $

$k$ nhận giá trị nào để số nghiệm nguyên của phương trình là lớn nhất, nhỏ nhất

Theo tính toán sơ bộ của mình thì kết quả lần lượt là:

10, 15, (21 hoặc 9)

Trong các số

$$C_{2007}^0, C_{2007}^1, C_{2007}^2,...,C_{2007}^{ 2007}$$

có bao nhiêu số chẵn?

 

Hãy tổng quát hóa bài toán

Em tổng quát hóa + giải tổng quát luôn (thực ra bài này rất dễ):
Trong các số $C_{n}^0, C_{n}^1, C_{n}^2,\ldots,C_{n}^{n}$ (với $n \in \mathbb Z^+$)

Trong tam giác Pascal thì mỗi $C_{n}^0, C_{n}^1, C_{n}^2,\ldots,C_{n}^{ n}$ là các số ở hàng thứ $n$

Mà hàng thứ $n$ thì luôn có $n+1$ số.

Do đó ta chỉ cần đếm số số chẵn trong mỗi hàng bằng cách đếm số số lẻ. Ta có cách làm sau:

Để đếm số số hạng lẻ trong cột $n$, chuyển $n$ qua hệ nhị phân. Goi $x$ là số chữ số một của $n_{(2)}$. Số số hạng lẻ sẽ là $2^x.$
 

 

Parity: To count odd terms in row $n$, convert n to binary. Let $x$ be the number of $1$s in the binary representation. Then number of odd terms will be $2^x$

-Wikipedia-

 

Chứng minh: Xem ở file đính kèm   Odd Coefficients.pdf   56.15K   2135 Số lần tải (cái này em Google Search)

Áp dụng vào bài toán 

Có $2007 = 1024 + 512 + 256 + 128 + 64 + 16 + 4 + 2 + 1$

Nên có dạng nhị phân là $11111010111.$ ($9$ số $1$)

Vậy số số chẵn trong dãy mà đầu bài cho sẽ là: $\boxed{2007 +1 -  2^{9} = 1496}$
 
Nguyên nhanh tay quá

Giải hệ phương trình : \left\{\begin{matrix} x^4+y^4 = 1\\ x^3+y^3 = x^2+y^2 \end{matrix}\right.

Từ $x^4 + y^4 = 1 \implies |x|,|y| \le 1 \implies x^3 + y^3 \le x^2 + y^2$

Đẳng thức xảy ra $\iff x^3 = x^2, y^3 = y^2, x^4 + y^4 = 1 \iff (x=0,y=1), (x=1,y=0)$

Cho 100 số thực dương thỏa mãn điều kiện:
i) $\sum\limits_{i=1}^{100}{a_{i}}^{2} > 10000$
ii) $ \sum\limits_{i=1}^{100}a_{i} < 300$
Chứng minh rằng luôn tồn tại 3 số có tổng không nhỏ hơn 100.

Note: lời giải của em có hỗ trợ từ 1 người bạn và có hỗ trợ từ công nghệ.
 
Không mất tổng quát, giả sử $x_{i+1} \ge x_i$ và ta sẽ đi chứng minh $x_{100} + x_{99} + x_{98} \ge 100$.
Giả sử đầu bài sai, tức $\not\exists 3$ số có tổng $\ge 100 \implies S = x_{100} + x_{99} + x_{98} < 100\ \text{(iii)}$
Gọi $x_j \ge x_i \ge t \ge 0$
Xét $(x_i-t)^2+(x_j+t)^2 = x_i^2+x_j^2+2t(x_j-x_i+t) \ge x_i^2+x_j^2$ (vì $x_j - x_i + t \ge 0$)
$\implies$ nếu thay $x_i -t \to x_i,\ x_j +t \to x_j$ thì vẫn cho tổng $2$ số không đổi nhưng tổng bình phương tăng lên.
Ta cũng có thể thay $x_{100}, x_{99}, x_{98}$ bằng $a = \frac S3$ là trung bình cộng của $3$ số đó mà không ảnh hưởng tới các điều kiện bài toán. (với $a < \frac {100}{3}$)
 
Phần thuật toán:
 

$\boxed{1.}$ Gán $i = \min,\ j = \max$ (lưu ý: $0 < x_i, x_j < a$)

$\boxed{2.}$ Nếu $i \ge j \to \boxed {\text{stop}}$

$\boxed{3.}$ Còn không, $t = \min \{x_i, a-x_j\},\ x_i := x_i - t,\ x_j := x_j + t$. Như nói ở trên, khi thế $x_i -t \to x_i,\ x_j +t \to x_j$ thì vẫn cho tổng $2$ số không đổi nhưng tổng bình phương tăng lên do đó, ta được dãy mới và cũng cũng thoả điều kiện (i), (ii), (iii)

$\boxed{4.}$ Quay lại bước $\boxed 1$

Phần Output, và giải: 
Sau khi vòng lặp kết thúc, ta thu được: $0 = x_1 = x_2 =\ldots = x_{i-1}< x_i \le x_{i+1} = x_{i+2} = \ldots = x_{100} = a$
$\implies x_i + (100 - i)\cdot a < 300, x_i^2 + (100-i)\cdot a^2 > 10^4, 0 < x_i \le a < \frac {100} 3$
$\implies 10^4 - ab > (300 - b)\cdot a = ca^2 > 10^4 - b$ (với $b = x_i,\ c = 100 - i$)
$\implies b = 0 \lor a<1$
$\boxed{\text{TH1:}\ a<1}\implies 10^4 < b^2 + ca^2 < b+ca < 300 \implies$ vô lí
$\boxed{\text{TH2:}\ b=0} \implies c\cdot 10^4 < (ac)^2 < (300)^2 \implies c < 9 \implies 9a^2 > ca^2 > 10^4$
$\implies 3a > 100 \iff a > \frac {100} 3 \implies$ mâu thuẫn
Vậy điều giả sử là sai, đầu bài là đúng. Bài toán được chứng minh

Cách khác:

Giả sử $x_1 \ge x_2 \ge \ldots \ge x_{100}, S = x_1 + x_2 + x_3$

$$\implies x_1^2+x_2^2+x_3^2+ \ldots +x_{100}^2\\ \le x_1^2+x_2^2+x_3^2+\left\lfloor\frac{300-S}{x_3}\right\rfloor x_3^2+\left(300-\left\lfloor\frac{300-S}{x_3}\right\rfloor x_3\right)^2 \\ \le (S-2x_3)^2+2x_3^2 + \left\lfloor\frac{300-S}{x_3}\right\rfloor x_3^2+\left(300-\left\lfloor\frac{300-S}{x_3}\right\rfloor x_3\right)^2$$

Đi tắm đã, lúc nào em làm tiếp, bây giờ em "hơi" lười

Hướng giải đúng đấy ạ

$X^3 - aX^2 + \frac 12(a^2-b^2)X - \frac 12 a(a^2-b^2)=0$

$\implies (X - a)(X^2 + \frac 12a(a^2-b^2)) = 0$

$\implies ...$

Áp dụng công thức $Newton$ hoặc $waring$ ta được:

$\left\{\begin{matrix}
 p=a\\
 p^2-2q=b\\
 p^3-3pq+3r=c
\end{matrix}\right.$

Với $x+y+z=p,xy+yz+zx=q,xyz=r$

$\Leftrightarrow \left\{\begin{matrix}
 p=a \\
 q=\frac{a^2-b}{2}\\
 r=\frac{a^3-3ab+2c}{6}
\end{matrix}\right.$

Suy ra $x,y,z$ là ba nghiệm của phương trình $X^3-aX^2+\frac{a^2-b}{2}X-\frac{a^3-3ab+2c}{6}=0$

Giải phương trình này là cả một vấn đề

 

giải hệ phương trình sau với a,b,c là tham số

$\left\{\begin{matrix} x+y+z=a\\ x^{2}+y^{2}+z^{2}=b\\ x^{3}+y^{3}+z^{3}=c \end{matrix}\right.$

 

Nghiệm xấu khủng khiếp, giải ra sẽ được

 
Mình xin sửa đầu bài:
$x+y+z=a, x^2 + y^2 + z^2 = b^2, x^3 + y^3 + z^3 = a^3$ (thế nghiệm đẹp hơn)