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

Bạn giải thích rõ hơn chút đi

Cách sort lại:
Mình dùng C++ (dạng mã giả) để minh hoạ vì có sẵn STL hơn:

int arr[n + 1];// đánh số từ 0

arr[n] = số integer nhỏ nhất;

int res[n];

int cnt = 0;

sort(arr, arr + n) // sort dãy theo thứ tự tăng dần

for (int i = 0; i < n; i++) { // đánh số từ 0

      if (arr[i] != arr[i + 1]){

             res[cnt] = arr[i];

             cnt++;

      }

      if (cnt == 0){

                cout << 1 << endl; // output kết quả

                cout << arr[n];

      } else {

                cout << cnt << endl;

                for(int i = 0; i < cnt; ++i) cout << res[i] << " ";

      }

}

Cách dùng set:

int n;

cin >> n;

int in;

set<int> s;

for(int i = 0; i < n; ++i){

     cin >> in;

     s.insert(s);

}

// s.size() và cách số trong s là kết quả.

Cách dùng hash table, tương tự cách dùng set

Mình cũng chẳng chắc là tối ưu hay chưa, không thì sắp xếp đi!

Bài 3 dùng thuật toán Lùa bò về chuồng liệu có tối ưu không bạn nhỉ?

Naive: O(n^2)

Sắp xếp:

Merge sort / Heap Sort / Quick Sort: $O(n log n)$
Radix Sort: $O(kn)$ (k là số chữ số trung bình)
 

Dùng cấu trúc dữ liệu:

Map / Set (red-black tree): $O(n log n)$
Hash Table: $O(n)$

Với dữ liệu ~1000 thì sort lại là đủ, và nếu bạn không gặp đen thì hash table là nhanh nhất.

ừ, 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 đề)

Chỗ này sai cho $k=4$ thì UCLN bằng 3 đó

Anh biết rồi buiminhhieu, ý anh là nk0kckungtjnh làm sai cái đoạn mà em đã chỉ ra mà;

Và cả đầu bài cũng không đúng nữa

$a  b = c  d,\ gcd(a, b)=1 \implies \ gcd(c, d) = 1\ $ ? (thử với a = 3, b = 4, c = 2, d = 6)

sage: E = EllipticCurve([0,0,1,0,-1]); E

Elliptic Curve defined by y^2 + y = x^3 - 1 over Rational Field
sage: E.integral_points(both_signs=True)
[(1 : -1 : 1), (1 : 0 : 1), (7 : -19 : 1), (7 : 18 : 1)]

Rõ ràng chỉ có hữu tỉ nghiệm thoả mãn.

Đầu bài đúng phải là:
 

> Chứng minh tồn tại vô số số hữu tỉ $n$ để $n^2 + n + 1$ là lập phương một số hữu tỉ

Chứng minh: Ta dễ thấy là rank của Elliptic Curve (E) là 1 (ở dòng [(1 : -1 : 1), (1 : 0 : 1), (7 : -19 : 1), (7 : 18 : 1)]), hoặc:
sage: E.analytic_rank()
1

Nên tồn tại vô số nghiệm hữu tỉ thoả mãn.

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)

cho a,b,c là các số thực thoả mãn $\sum a^{2}= 1$

Chứng minh

$\left | \left ( a+b+c \right )-2abc \right |\leq \sqrt{2}$

http://diendan.hocma...784&postcount=4

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

Không ai làm được 4 5 6 à?!  

Mình xin tiếp tục nhé!!
Bài toán 4:
Cho bàn cờ vua 8x8. Người ta đặt lên bàn cờ 12 quân tốt vào 12 ô.
Chứng minh rằng: có thể chọn 4 hàng và 4 cột sao cho 12 quân tốt nằm trong 4 hàng và 4 cột đó
Bài toán 5:
Hỏi như bài 4 với bảng 2nx2n. Đặt 3n quân cờ. Chọn n hàng và n cột (tổng quát)
Bài toán 6:
Cho đa giác lồi 2n cạnh.
Chứng minh rằng: tồn tại ít nhất một đường chéo không song song với bất kì cạnh nào của đa giác đó

                                       
 

Bài 4, 5: 
Thi thử KHTN và giải tại đây

Bài 6: KHTN vòng 2 năm 2006

Giải phương trình

$x^{3}-3abx+a^{3}+b^{3}=0$ với a, b là tham số

Gợi ý:
$pt\ \iff (x + a + b)(x^2+a^2+b^2 - ax - bx - ab) = 0$

Bạn giải và biện luận thôi, chú ý phương trình: 

$(x^2+a^2+b^2 - ax - bx - ab) = 0 \iff \frac {(x-a)^2 + (x-b)^2 + (a-b)^2}2 = 0$

Kết luận: $x = - (a+b)$

_{a) Cho $2012$ điểm trên mặt phẳng. Chứng minh tồn tại hình vuông chứa đúng $1006$ điểm}

_{b) Cho $(m + n)$ điểm trên mặt phẳng. Tồn tại hay không hình vuông chứa đúng $m$ điểm ? Chứng minh.}

Bài 1: Cho $A,B,C,D$ lần lượt là $4$ đỉnh của một hình vuông. Một người muốn làm con đường kết nối $4$ điểm này, nhưng do thiếu kinh phí ông ta phải nghĩ ra 1 con đường ngắn nhất. Hãy giúp ông ta làm điều đó.
 
 
Bài 2 (khá dễ): Cho $(O;1)$ và các điểm $A_1,\ A_2,\ A_3,\ldots,\ A_n$ trên mặt phẳng.
Chứng minh tồn tại điểm $I$ nằm trên $(O)$ sao cho $IA_1 + IA_2 + IA_3 +...+ IA_n \ge n$

Sao tới giờ mới bắt đầu lo hả em ?!

 

Em tự kiếm tất cả đề thi vào trường đó từ 10 năm trở lại đây, post lên đây rồi anh đoán dạng cho nhé ! 

Hay anh thử dự cho em đề KHTN + ĐHSP năm nay để em tủ, dự cả đề Ngữ Văn thì càng tốt ạ . Biết đâu anh lại là thánh dự   

Không biết tỉnh em là tỉnh nào chứ như anh ở Hải Dương thì người ta hiếm khi cho cực trị hình học mà  có cho thì nó phải rất dễ. Chứng minh tứ giác nội tiếp thì chỉ cần phải chứng minh dựa vào góc nội tiếp tức là chứng minh tổng 2 góc đối bằng 180 hoặc 2 góc cùng chắn một cung bằng nhau. Ta cứ lần lượt lấy 1 cặp góc (có trình tự) của cái tứ giác cần chứng minh rồi xem nó có khả năng bằng nhau hay tổng 180(dựa vào đề bài). Nếu có thì tìm cách chứng minh, nếu không thì chuyển sang cặp khác. Chứng minh 3 điểm thẳng hàng, chẳng hạn lần lượt A, B, C thì ta xem có tia nào đó gốc B, chẳng hạn Bx rồi chứng minh $\widehat{ABx}+\widehat{CBx}=180$, tuơng tự với tia Ay gốc A thì ta sẽ chứng minh $\widehat{yAB}=\widehat{yAC}$. Có lẽ em phải post bài lên thì mới nói rõ được

Cậu cũng tỉnh Hải Dương ? Huyện nào thế ? Avatar để hình cờ vua có vẻ cũng là Hobby player, cách đây mấy năm (2 hay 3 thì phải) bạn có chơi giải của tỉnh không ấy nhỉ, biết đâu mình quen.

Cho a và b là 2 số nguyên ,m là một số nguyên dương , a và m nguyên tố cùng nhau .Tính

$S= \sum_{i= 0}^{m-1}\left \{ \frac{ai+b}{m} \right \}$

"Mình" hỏi chút, kết quả có phải là $b + \frac 12a (m-1)$ (thay $i$ vào rồi tính bình thường)
Thấy nó hơi dễ nên hỏi lại (vì đang ở box Olympic)