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

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

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

 

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é.

Cách thông dụng nhất:
$a^3+b^3+c^3-3abc$
$=a^3+3ab(a+b)+b^3+c^3-3abc-3ab(a+b)$
$=(a+b)^3+c^3-3ab(a+b+c)$
$=(a+b+c)(a^2+2ab+b^2-ab-ac+c^2)-3ab(a+b+c)$
$=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)$
_____
P/s: Mình đang nghĩ thêm cách nữa, nếu được sẽ post lên.

Mình sẽ góp 1 cách (khá độc đáo...vì chẳng ai làm kiểu này cho tốn công), cũng khá nhanh
Có $G(x) = x^3 - (a + b+ c)x^2 + (ab + bc + ca)x - abc$ nhận a, b, c là nghiệm, thay x lần lượt bằng a, b, c xong cộng theo vế:
$a^3 + b^3 + c^3 - 3abc -...= 0 => a^3 + b^3 + c^3 - 3abc =(a+b+c)(a^2+b^2+c^2-ab-bc-ca)$

Đây là 1 đa thức khá quen thuộc, hãy phân tích nó thành nhân tử bằng càng nhiều cách càng tốt
$$a^3 + b^3 + c^3 - 3abc$$

$(a+b+c)(a^2+b^2+c^2-ab-ac-bc)$

Mình đang nói về cách làm chứ không phải kết quả vì bài này mình post không phải là nhờ giải hộ bài tập.

tưởng chung của bài 71 là giới hạn miền nghiệm $a \ge b \ge c$ khi đó $3c^3 \le 2001 \Leftrightarrow c \le 8$.

 

Anh đã thử và cảm nhận: a long story

Giới hạn như vậy: 8 trường hợp của c, mỗi trường hợp của c lại có vài trường hợp của a, b $\implies$ khá dài (cần kết hợp đồng dư, lời giải sẽ dễ chịu hơn)

Tiếp cho nóng nào
Bài 70: Giải phương trình nghiệm nguyên

$x^2 + y^2 + z^2 = 807$ ( một bài dễ ~~)

----------
Có $x^2 + y^2 + z^2 = 807 \equiv 3 \pmod 4\\ \implies x^2 \equiv y^2 \equiv z^2 \equiv 1 \pmod 4 \\ \iff 2\nmid x, y, z$
Đặt $x = 2x_1 + 1,y = 2y_1 + 1,z = 2z_1 + 1$
Phương trình tương đương 

$4 x^2+4 x+4 y^2+4 y+4 z^2+4 z+3 = 807 \\ \iff {x}^{2}+x+{y}^{2}+y+{z}^{2}+z=201 \\ \iff x(x+1)+y(y+1)+z(z+1)=201$

Mà $2 \mid VT \land 2 \nmid VP\implies$ vô nghiệm

 

Xin góp 1 bài: 

Bài 71: Giải phương trình nghiệm nguyên dương $a^3 + b^3 + c^3 = 2001$

Tiếp tục nào

Bài 73* : Chứng minh rằng phương trình sau không có nghiệm nguyên dương :

a.$x^{4}+y^{4}=z^{2}$

b.$x^{4}-y^{4}=z^{2}$

Bài 74 : Có tồn tại hay không các số nguyên $x$,$y$ thoả mãn điều kiện $1992x^{1993}+1993y^{4}=1995$

Bài 75 : Giải phương trình nghiệm nguyên : $x^{2}+x=y^{4}+y^{3}+y^{2}+y$

Bài 74: Xét đồng dư cho $4 \implies$ vô nghiệm

Bài 75: Nhân thêm $4$ rồi cộng $1$ vào $2$ vế, rồi chặn sẽ tìm đuợc nghiệm

Bài 73: a), b)
Đưa về phương trình pytago, chắc biểu diễn các nghiệm 1 hồi $\implies$ vô nghiệm (chưa thử, không biết lùi vô hạn được không)

EDIT: Đây là 1 bài toán của Nagell, đã được chứng minh vô nghiệm (các bạn thử Google xem có solution không ?).

Hâm nóng topic nào .
Bài 69: Giải phương trình nghiệm nguyên $5^x + 2.5^y + 5^z = 4500$ với $x<y<z$

$x<y<z$ làm ta nghĩ đến việc xét khoảng
#: $z<5 \implies VT < VP$
#: $z>5 \implies VT > VP$
#: $z=5$, thay, và thử $(x;y;z)=(3;4;5)$

n = 7 + 11m hoặc n = 6 + 11m (m là số nguyên dương)

Holy Crap, Forever Alone


Tết quyết đi kiếm gấu dự thi

Anh Hoàng nói chuẩn Nếu như có cuộc thi này lần 2, phải tìm một số biện pháp khác để chỉ có 2 người mới làm được

Anh kiếm được cái việc gì mà phải 2 người mới làm được thì tình hình là hơi bị nguy hiểm

Chả hiểu sao em báo cáo vài lần mà không thấy các mod xử lí:
4 post giống nhau + spam + lỗi tiêu đề + tiếng việt không dấu http://diendantoanho...hang-phan-biet/, http://diendantoanho...ớn-hơn-1802000/, http://diendantoanho...ớn-hơn-1802000/, http://diendantoanho...n-biet-doi-một/

Spam tại (post giống nhau)

 

http://diendantoanho...c/95730-số-học/

 

http://diendantoanho...c/95729-số-học/

 

http://diendantoanho...c/95727-số-học/

 

http://diendantoanho...c/95726-số-học/

----
Nhiều cách chứng minh:
http://vietgov.asia/so-nguyen-to_50
http://math.vn/showt...ố-số-ng-tố-4k-3
http://vuon-toan.blo...ulo-phan-4.html

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

Hình minh hoạ

trường nào đấy bác, để như thế khác gì bắt tính $6:2(1+2)$ với 2 đáp án 1 và 9 thì khoanh cái nào, đề bài rõ ràng nhưng kết quả thì không, cháu mà học lớp 3 thì cháu khoanh cả a, b, chúng đề không sai.

Mình nghĩ là b); a + a + a, tổng của 3 số a đúng hơn là tổng a số 3

$a+b+c+d \vdots 11$ và $a+c-b-d \vdots 11$
=> $a+b+c+d+a+c-b-d = 2(a+c) \vdots 11$
=> a+c = 11 => b+d = 11
*11 = 2+9=3+8=4+7=...=9+2
...
Lâu rồi không làm dạng này, không giải được

Đề này khá rắn, câu V mình mu-tis luôn
Câu 2.1
$pt \iff m+(x^2-2 x)^2-4 (x^2-2 x) = 0 (1)$
Đặt $x^2-2x = t \implies 1 + t > 0$
$(1) \iff t^2 - 4t + m =0 \implies 4-m > 0 \land t_1, t_2 > 0 \iff m < 4 \land 4 > 0 \land m>0 \implies ...$

ại sao khi một thành viên nào đó có $n$ bài viết mà các thành viên khác lại không thể tìm kiếm được tất cả $n$ bài viết đó nhỉ?
Rất mong BQT có thể thêm chức năng tìm kiếm tất cả các bài viết như trên .

Mình không nghĩ đây là ý hay, ảnh hưởng đến 'performance' của server/database, với lại mình cũng không thích người khác bới móc hết bài viết của mình
-------------------
Bạn có thể làm điều này bằng cách dùng Google Custom search mà
-------------------

Mặc dù em dùng internet ở dạng Advanced  nhưng chưa giờ mới biết nút này;
Nhưng nút chức năng tìm kiếm của diễn đàn không bắt nhập Captcha, hacker vào (D)DoS thì có sao không ạ

Có thể tìm được mọi thứ chứ không chỉ bài viết. Bạn vào trang cá nhân của thành viên cần tìm, phía tay phải có ba nút: Thêm bạn, Gửi tin nhắn và Tìm kiếm. Bấm vào nút Tìm kiếm là có tất.


Nhân đây nhắc với tất cả các bạn khác luôn, có nhiều chức năng diễn đàn có mà các bạn không biết, cho nên đừng ngại đặt câu hỏi trong box Hướng dẫn - Trợ giúp.  

Xin chào các bạn,

 

Diễn đàn vừa được nâng cấp lên phiên bản mới nên có thể chưa hoạt động được ổn định. Xin các bạn vui lòng thông báo lỗi cho BQT ở topic này. 

 

Sẽ sớm có topic giới thiệu các chức năng mới.

 

Cảm ơn các bạn.

 

 

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

Phần trích dẫn có vấn đề ạ, nó không đóng khu hết

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

MrMathCSKH0110 said: Latex mất ạ

    Re: Nút $fx$ ngày mai sẽ thêm vào, các bạn thông cảm ! (Nesbit)

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

Lỗi ô trích dẫn chỉ bị ở "Orginal theme" còn IP.Board theme không bị

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

Không biết diễn đàn có đủ kinh phí để mua theme này không nhỉ: