Thay mặt ban thư kí admin vnoi (thực ra có mỗi mình em nhưng các bác cứ để e atsm tí :D ), chúc mọi người ngày mai bình tĩnh tự tin và đạt kết quả tốt nhất, nhưng cao vừa vừa thôi cho đội e còn giải nữa :v :v
PS: bác nào rảnh lên 903 ae "xã giao" tí
Đóng góp: 122
Ngày sinh: 29/05/1997
Đăng ký: 05/07/2015
Lần đăng nhập cuối: 20/10/2016
VOJ: Chưa kết nối
Đăng lúc 8 năm, 8 tháng trước
Thay mặt ban thư kí admin vnoi (thực ra có mỗi mình em nhưng các bác cứ để e atsm tí :D ), chúc mọi người ngày mai bình tĩnh tự tin và đạt kết quả tốt nhất, nhưng cao vừa vừa thôi cho đội e còn giải nữa :v :v
PS: bác nào rảnh lên 903 ae "xã giao" tí
Đăng lúc 8 năm, 8 tháng trước
Nếu có một bức tranh về tuổi 17 thì đó hẳn là một bức tranh mang vẻ đẹp hiền dịu, nhẹ nhàng, chứa đựng cả những giấc có thực. Tôi của tuổi 17 cũng như bức tranh đó, hồn nhiên, trong sách, ngây thơ một cách khó đỡ (hồi đấy chưa có dâm dê bẩn bựa như bây giờ nhé ), lúc nào cũng ấp ủ ước mơ được đi thi quốc gia cùng các bạn chuyên. Và rồi, thần may mắn đã mỉm cười với tôi, cái ngày mà tôi nhận được tin mình được đi thi quốc gia, ngày hôm đó, cứ ngỡ như mới là ngày hôm qua thôi :3. Ngày đó, cả sáng xuống chuyên thi, sau tự bắt xe buýt về, có chút mệt mỏi. Về đến nhà lăn ra ngủ (theo lời bố mẹ là trông như thằng chết trôi >< ), cơ mà mệt thì mệt, càng nằm càng không ngủ được, có lẽ vì lo lắng cho cái kết quả. 1h, 2h, 3h, mắt mở như cái đèn pha ô tô, 3h5 phút thì chả hiểu thế nào, ngủ lim dim, 5 phút sau, 3h10, thầy gọi điện bảo được đi quốc gia. Lúc đấy tôi khóc tiếng mán luôn, ngồi hóng kết quả, mãi chả thấy đến, lúc không hóng nữa thì nó lại đến :3. Vài ngày trước khi xuống chuyên, hỏi thăm anh em tứ phương, phải chuẩn bị những gì khi xuống (liệu có phải mang dầu ăn theo cùng không), bla bla đủ thứ trời ơi đất hỡi. Hôm trước khi đi, chia tay lớp cũng vui, được mọi người viết thư chúc mừng, thư chúc may mắn đủ kiểu. Tiếc là hồi đấy không có gan nói với bạn mình thích: “Cậu ơi, tớ mà có giải quốc gia thì bọn mình yêu nhau luôn nhé :v”. Nghĩ lại thấy tiếc, hồi đấy mà dũng cảm hơn tí không khéo giờ tôi đã có gấu cmnr mọi người ạ =))))).
Ngày đầu xuống chuyên, quá nhiều cảm xúc có trong mình,vui buồn lẫn lộn. Vui, vì được đi thi quốc gia, có cơ hội chứng tỏ khả năng của mình, có cơ hội thoát khỏi câu “cóc ghẻ đòi xơi thịt thiên nga :v “. Bỡ ngỡ cũng chả kém, vì phải học tập trong một môi trường mới, bạn bè mới, thầy cô mới, những điều kiện học tập hoàn toàn mới. Buồn, vì nghe thiên hạ đồn đại hot girl chuyên vĩnh phúc toàn là hoa đã có chủ, tôi mà ấp ủng tán chúng nó là sẽ được vô nhà thương. Xuống chuyên, nhiều bạn mới, nhưng phải công nhận là cái số mình nó may, trước khi xuống đã kịp có một thằng bạn thân chí cốt. Nói qua về thằng bạn tốt này, nói chung là đẹp trai hơn mình, học giỏi hơn mình, tốt bụng hơn mình, điềm tĩnh hơn mình (chắc hết rồi, những cái còn lại chắc nó không hơn đâu :3 ) . Nói về độ thân của hai thằng, thì có thể miêu tả ngắn gọn qua 9 từ ” ăn cùng mâm, đắp cùng chăn, ngủ cùng giường”. Thực ra ban đầu giường của các thành viên đội tin cách khá xa nhau, nhưng các anh bảo kê lại ngủ cạnh nhau cho nó…… máu. Cái hôm kê giường nó cạnh giường tôi, nó cũng có bảo với mình: “Ờ nhà tao hay ngủ với thằng em, đêm toàn ôm nó nên nếu anh ôm chú thì chịu khó nhé”. Tôi thì cũng chỉ ậm ờ cho qua chuyện, vì nghĩ, người mình đủ 36 cái xương sườn, nó mà ôm thì gãy cmn tay chứ chả đùa, chắc nó sẽ chừa mình ra. Nhưng đời không ai tưởng được chữ ngờ, có hôm đang ngủ ngon, tự nhiên thấy người mình âm ấm, nóng nóng (tôi không có tè dầm đâu nha các bác), bỏ chăn ra, quay sang nhìn thì thấy nó đang ôm chặt mình, chả hiểu nghĩ thế nào, mình tung chăn ra, đạp nó một phát khá mạnh, miệng lèm bèm: “ĐM bố *éo bị gay =))))))))”. Khổ, đạp nó hơi quá, làm nó lăn quay mấy vòng, tí nữa thì lăn xuống đất để ngủ. Bây giờ nghĩ lại thấy ân hận vô cùng, tại hồi đấy lơ tơ mơ nên không biết tôi đạp vào chỗ nào của nó, nhỡ đạp nhầm vào chỗ hiểm, sau này nó vcmn sinh, mình bị bắt đền thì……….nhục. Về mặt cơ bản, có thằng bạn thân, rồi nó còn nằm ngủ cạnh mình thì sướng lắm mọi người ạ, khi nào buồn bực thiếu việc thì nó sẽ thành cái bao cát cho mình luyện tay (nó rất là hiền nhé :D ), hoặc nếu hôm nào trời quá lạnh thì ôm nó rất chi là ấm (nhưng nó mà ôm tôi là bị mình song phi củ hành ngay). Mấy ngày đầu trôi qua, rất chi là hạnh phúc, ngày thì chống đẩy ba bốn chục phát vì tội không làm đủ bài tập thầy giao, đêm thì thức đến 2h để ngồi dịch đề tiếng anh ( mà cái trình tiếng anh của mình thì, dịch xong tự đọc lại không hiểu mình vừa viết cái gì). Đúng là thức đêm mới biết đêm dài, sau thời gian ban đầu hạnh phúc thì cũng có chuyện :v , ngủ cạnh nó nhiều mới thấy hai đứa dở hơi y như nhau. Chả là dạo đấy nó cuồng Số đỏ của ông Vũ Trọng Phụng, ngày nào cũng bật cái video có người đọc hẳn hoi, cho loa to hết cỡ rồi củ hành tất cả những đứa còn lại trong đội tuyển. Tại cái vụ đấy mà em mất ăn mất ngủ mấy hôm liền, về sau nó xem chán thì lại cuồng cái câu của ông bố trong tác phầm đấy (em chưa học chưa đọc nên cũng chả biết ông ấy tên gì =))))), dạo đó mình nói cái gì nó cũng :”Biết rồi khổ lắm nói mãi”, mà thực ra tôi đã kịp nói cái gì đâu, nó toàn ừ rồi……….không làm việc tôi nhờ.
Đấy, thằng bạn thân dở hơi của em thế đấy, có nói xấu về nó thì có nói vài ngày cũng chả hết , nhưng mà không có nó để chém gió cùng thì hẳn là buồn đi rất nhiều.
Lại nói về thân thiết, ngoài thằng bạn dở hơi ra em còn khá thân với một anh 96 các bác ạ. Anh này thì tốt bụng cực kì, học cũng rất là giỏi, ý chí thì ngang ngửa sắt đá, lại thêm cái khoản đẹp trai nhất nhì đội nữa (thế mà vẫn ế giống mình, ha ha ). Nói về độ tốt bụng của anh này thì có nhiều chuyện lắm :D :D, chả là trước khi em xuống chuyên, lo lắng cũng nhiều, không biết phải mang theo những gì, toàn những cái nhỏ nhặt nhưng nhiều quá lại thành cái lớn. May được ông này giúp, trước khi xuống chuyên, ông này có dặn em: “cứ mang ít đồ cá nhân thôi, mới cả 2h chiều mai họp đội tuyển , e nhớ xuống sớm”. Mình tin lời ông ý, vác xác xuống chuyên từ tận………..1h, trời nắng chang chang, đi nửa tiếng thì đến, ngồi chờ các ông để “họp đội tuyển”. 2h, 3h, 4h mãi chả thấy ông ấy đâu, lòng đau như cắt, nước mắt đầm đìa vì ăn lừa =)))))). Đã thế lúc đi vì vội, bố em phóng khá nhanh, hậu quả là ngã xe, bố em không sao, xe không sao, cái gì cũng không sao, riêng em thì có sao các bác ạ >< (rách quần và mất tí huyết trên đường). Tốt bụng là thế, nhưng cái em khâm phục anh nhất là ý chí sắt đá, dám theo đuổi ước mơ và quan trọng nhất là dám thực hiện (mà cái này cũng gây ra họa được mới sợ chứ :v ). Tất nhiên, ai cũng có điểm tốt điểm xấu các bác ạ, điểm xấu nhất của ông này chắc là hay quên và có thể cười tươi trong mọi hoàn cảnh (sao không truyền cái đấy lại cho em :3). Cười tươi thì không nói làm gì, ông ý mà cười thì khối cô xin chết luôn, còn riêng cái khoản hay quên thì nó là thảm họa, và em lại là thằng dính phốt nhiều nhất. Chả là hôm đó trời lạnh, giữa mùa đông, trước khi đi tắm dặn đi dặn lại là 5 phút nữa mang nước nóng vào tiếp cho em (do bình nước nóng khá nhỏ). Đại ka gật như thật, mình cũng ngây thơ tin vào sự tốt bụng của đại ka. Ai ngờ, 5 phút, 10 phút, 20 phút sau mãi chả thấy nước đâu (mãi sau bắt khai mới biết đại ka đang bận chat với gấu =))))))) ) lạnh sun cả ……..da, nghĩ lại đến giờ vẫn thấy sợ, may mà hôm đấy mình kịp gội đầu rồi, không thì miễn ra khỏi đấy luôn. Kì thi quốc gia đến, cảm thấy quá tiếc nuối cho anh, học rất giỏi, chăm không thua thằng nào trong đội, đùng một phát, đứng cuối đội, mất cơ hội tuyển thằng đại học, phải quay lại ôn thi đại học từ đầu. Nhưng thật may, trời vẫn thương người hiền, đại ka vẫn vượt vũ môn một cách ngoạn mục, được tiếp tục theo con đường mà ổng đã chọn, và quan trọng là có gấu rõ xinh. Hy vọng một ngày nào đó, e sẽ học giỏi được như anh yêu, và quan trọng nhất là có gấu xinh hơn gấu của anh yêu.
Đăng lúc 8 năm, 8 tháng trước
“C++ được đánh giá là ngôn ngữ mạnh vì tính mềm dẻo, gần gũi với ngôn ngữ máy. Ngoài ra, với khả năng lập trình theo mẫu ( template ), C++ đã khiến ngôn ngữ lập trình trở thành khái quát, không cụ thể và chi tiết như nhiều ngôn ngữ khác. Sức mạnh của C++ đến từ STL, viết tắt của Standard Template Library - một thư viện template cho C++ với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của C. Với khái niệm template, những người lập trình đã đề ra khái niệm lập trình khái lược (generic programming), C++ được cung cấp kèm với bộ thư viện chuẩn STL.
Bộ thư viện này thực hiện toàn bộ các công việc vào ra dữ liệu (iostream), quản lý mảng (vector), thực hiện hầu hết các tính năng của các cấu trúc dữ liệu cơ bản (stack, queue, map, set...). Ngoài ra, STL còn bao gồm các thuật toán cơ bản: tìm min, max, tính tổng, sắp xếp (với nhiều thuật toán khác nhau), thay thế các phần tử, tìm kiếm (tìm kiếm thường và tìm kiếm nhị phân), trộn. Toàn bộ các tính năng nêu trên đều được cung cấp dưới dạng template nên việc lập trình luôn thể hiện tính khái quát hóa cao. Nhờ vậy, STL làm cho ngôn ngữ C++ trở nên trong sáng hơn nhiều.”
Trích “Tổng quan về thư viện chuẩn STL”
Stack
Queue
Priority_queue
Associative containers
Set
Multiset
Map
Multimap
Bitset
#include <iostream>
#include <stack> //khai báo sử dụng container stack
#define n 100
using namespace std; //khai báo sử dụng STL
main() {
....
}
Tất cả các container ở 2 loại: Sequence container và Associative container đều hỗ trợ các iterator như sau (ví dụ với vector, những loại khác có chức năng cũng vậy).
/*khai báo iterator “it”*/
vector <int> :: iterator it;
/* trỏ đến vị trí phần tử đầu tiên của vector */
it=vector.begin();
/*trỏ đến vị trí kết thúc (không phải phần tử cuối cùng nhé) của vector) */
it=vector.end();
/* khai báo iterator ngược “rit” */
vector <int> :: reverse_iterator rit; rit = vector.rbegin();
/* trỏ đến vị trí kết thúc của vector theo chiều ngược (không phải phần tử đầu tiên nhé*/
rit = vector.rend();
Tất cả các hàm iterator này đều có độ phức tạp O(1)
Khai báo vector:
#include <vector>
...
/* Vector 1 chiều */
/* tạo vector rỗng kiểu dữ liệu int */
vector <int> first;
//tạo vector với 4 phần tử là 100
vector <int> second (4,100);
// lấy từ đầu đến cuối vector second
vector <int> third (second.begin(),second.end())
//copy từ vector third
vector <int> four (third)
/* Vector 2 chiều*/
/* Tạo vector 2 chiều rỗng */
vector < vector <int> > v;
/* khai báo vector 5×10 */
vector < vector <int> > v (5, 10);
/* khai báo 5 vector 1 chiều rỗng */
vector < vector <int> > v (5);
//khai báo vector 5*10 với các phần tử khởi tạo giá trị là 1
vector < vector <int> > v (5, vector <int> (10,1));
Các bạn chú ý, trước C++11, 2 dấu “ngoặc” không được viết liền nhau, ví dụ như sau là sai:
/*Khai báo vector 2 chiều SAI*/
vector <vector <int>> v;
Các hàm thành viên: Capacity:
Truy cập tới phần tử:
Chỉnh sửa:
Nhận xét:
Sử dụng vector sẽ tốt khi:
Vector làm việc giống như một “mảng động”.
Ví dụ 1: Ví dụ này chủ yếu để làm quen sử dụng các hàm chứ không có đề bài cụ thể.
#include <iostream>
#include <vector>
using namespace std;
vector <int> v; // Khai báo vector
vector <int>::iterator it; // Khai báo iterator
vector <int>::reverse_iterator rit; // Khai báo iterator ngược
int i;
main() {
for (i=1;i<=5;i++) v.push_back(i); // v={1,2,3,4,5}
cout << v.front() << endl; // In ra 1
cout << v.back() << endl; // In ra 5
cout << v.size() << endl; // In ra 5
v.push_back(9); // v={1,2,3,4,5,9}
cout << v.size() << endl; // In ra 6
v.clear(); // v={}
cout << v.empty() << endl; // In ra 1 (vector rỗng)
for (i=1;i<=5;i++) v.push_back(i); // v={1,2,3,4,5}
v.pop_back(); // v={1,2,3,4}
cout << v.size() << endl; // In ra 4
v.erase(v.begin()+1); // Xóa ptử thứ 1 v={1,3,4}
v.erase(v.begin(),v.begin()+2); // v={4}
v.insert(v.begin(),100); // v={100,4}
v.insert(v.end(),5); // v={100,4,5}
/*Duyệt theo chỉ số phần tử*/
for (i=0;i<v.size();i++)
cout << v[i] << " "; // 100 4 5
cout << endl;
/*
Chú ý: Không nên viết
for (i=0;i<=v.size()-1;i++) ...
Vì nếu vector v rỗng, v.size() là kiểu unsigned int, nên v.size()-1 sẽ bằng 2^32-1
*/
/*Duyệt theo iterator*/
for (it=v.begin();it!=v.end();it++)
cout << *it << " " ; // In ra giá trị ma iterator đang trỏ tới "100 4 5"
cout << endl;
/*Duyệt iterator ngược*/
for (rit=v.rbegin();rit!=v.rend();rit++)
cout << *rit << " "; // 5 4 100
cout << endl;
system("pause");
}
.....
Bài viết của anh Mạnh hơi dài nên mình chỉ up đến đây thôi nhé, phần còn lại mọi người download theo đường link:
http://www.mediafire.com/download/5o1gllos4gjkz3k/STL.pdf
Cảm ơn vì đã đọc và xin lỗi vì sự bất tiện này ^_^
Đăng lúc 8 năm, 8 tháng trước
Một số A gọi là có bậc K đối với cơ số B nếu như : A = Bx1 + Bx2 + … + Bxk (trong đó \(x_1 \neq x_2 \neq x_3 \neq ... \neq x_k\))
Ví dụ :
Yêu cầu : Cho trước 1 đoạn [X,Y] . Hãy xác định xem trong đoạn này có bao nhiêu số có bậc K đối với cơ số B.
Giới hạn :
Input
Gồm 4 số nguyên X, Y, K và B
Output
Gồm 1 số duy nhất là kết quả tìm được .
Ví dụ
Input
15 20 2 2
Output
3
Giải thích : Đó là các số
Thuật giải :
Ta sẽ đưa bài toán này về một bài toán nhỏ hơn đó là cho biết trong đoạn [1,A] có bao nhiêu số có bậc K đối với cơ số B.
Với mỗi giá trị A ta đều xác định được Bn sao cho Bn+1 > A . Áp dụng tính chất: Bn > Bn-1 + Bn-2 + … B0 → A > Bn-1 + Bn-2 + … B0.
Như vậy bài toán đã được giải quyết. Nói tóm lại đây là một bài khá đặc trưng cho QHĐ = Đệ quy với công thức truy hồi đơn giản :
Cal(A,K,B) = Tổ hợp chập K của N + Cal(A-Bn,K-1,B).
Nikifor có một số X nhưng đó không phải là con số mà anh ta cần. Anh ta muốn đổi con số X này lấy con số Y mà anh ta thích. Để đổi được con số Y này anh ta phải chọn ra một cơ số K sao cho ta có thể đạt được số Y bằng cách xoá đi một vài chữ số của số X trong biểu diễn của hệ cơ số K .
Ví dụ : X = 19 , Y = 4 , K = 3.
Vậy ta có thể đạt được số Y bằng cách xoá đi số 0 trong biểu diễn của số X .
Yêu cầu : Hãy tìm cơ số K nhỏ nhất có thể được .
Giới hạn
Input
Gồm hai số nguyên X và Y
Output
Nếu tồn tại K thì ghi ra K nhỏ nhất , nếu không tồn tại thì ghi ra “No Solution”.
( Lưu ý số K có thể \(\geq\) 10 , không nhất thiết là nhỏ hơn 10 )
Ví dụ
Input
19 4
Output
2
Thuật giải :
Ta duyệt tất cả các số K từ 2 -> Y . Tuy nhiên điều muốn nói ở đây là làm cách nào để có thể kiểm tra xem với một cơ số K có đáp ứng được yêu cầu hay không một cách nhanh nhất ! Nếu như làm bình thường thì ta sẽ xây dựng được biểu diễn của X, của Y .Nếu xâu con chung dài nhất của X và Y = Y -> Đáp ứng yêu cầu ! Hoặc một cách cải tiến khác cũng đưa về xâu dựa trên nhận xét : xâu con chung dài nhất của X , Y = Y tương đương với các phần tử của Y xuất hiện đúng theo thứ tự này trong xâu X , tức là xâu con chung dài nhất Y = Xi1Xi2…Xik thì i1 < i2 < … < ik . -> Ta có thể sủ dụng thuật toán được mô tả sau đây : ( Cải tiến 1 )
Ok := True ;
While Y <> Ø do Begin
While X[1] <> Y[1] do Begin
Delete(X,1,1) ;
If X = Ø then Begin
Ok := False ; Exit ;
End ;
End ;
Delete(X,1,1) ; Delete(Y,1,1) ;
End ;
Tuy có cải tiến như vậy nhưng về cơ bản cấp độ của thuật toán là khá cao ( + thời gian tạo xâu ) và không thể chấp nhận được trong thời gian giới hạn là 1 s. Vì vậy ta cần có một thuật toán kiểm tra tốt hơn là đưa về xâu ! Ý tưởng của thuật toán là thay vì đổi ra xâu ta sử dụng phép div , nếu như trong hệ cơ số K ta sử dụng phép div K thì cũng giống như ta sử dụng phép shr trong hệ nhị phân ! Nó sẽ dịch chuyển số X về bên phải một chữ số ! Ta áp dụng cải tiến 1 trong trường hợp này là so sánh chữ số cuối cùng chứ không phải chữ số đầu tiên nữa ! Và chữ số cuối cùng của X = X mod K , chữ số cuối cùng của Y = Y mod K . Thủ tục Delete sẽ được thay bằng X = X div K . Như vậy thuật toán với 2 cải tiến này sẽ giảm được rất nhiều thời gian lãng phí do phải tạo xâu, sinh luỹ thừa ! Về mặt thời gian là chạy khá tốt !
Ngoài ra còn một thuật toán có cấp độ O( (logY)3 ) mà ta không đề cập tới ở đây mà sẽ nhắc tới ở một chương khác. Mặc dù vậy với X , Y \(\leq\) 106 thì ta có thể yên tâm là thuật toán này chạy chậm gấp 2,5 lần thuật toán duyệt với 2 cải tiến ở trên !
Trong một trường đại học có một hệ thống N lò sưởi được đánh số từ 1-> N ! N lò sưởi này được điều khiển bởi N kỹ sư được đánh số từ 1 -> N ! Mỗi lò sưởi chỉ có 1 công tắc là tắt/bật lò sưởi mà thôi ! Tuy nhiên oái oăm thay là mỗi kỹ sư lại điều khiển 1 vài lò sưởi chứ không phải chỉ 1 lò sưởi! Và khi họ đi làm thì nếu như được chỉ định là trực ở lò sưởi thì họ sẽ đi thay đổi công tắc ở tất cả các lò sưởi mà họ điều khiển, nếu đang bật -> tắt và tắt -> bật. Kỹ sư thứ i sẽ tới vào trường vào lúc i giờ. Ban giám hiệu trường muốn đảm bảo sức khoẻ cho sinh viên nên phải phân công kỹ sư trực sao cho đến giờ thứ N+1 thì tất cả lò sưởi đều đang ở trạng thái bật !
Yêu cầu : Bạn được thuê giúp đỡ Ban Giám Hiệu của trường ! Hãy chỉ ra xem những kỹ sư phải được chỉ định là trực để đáp ứng yêu cầu của ban giám hiệu là những kỹ sư nào ! Nếu có nhiều phương án thì cho biết phương án mà số kỹ sư bị chỉ định là ít nhất.
Giới hạn :
Input
Output
Ví dụ :
Input
4
2 1 2
3 2 3 4
1 2
1 4
Output
3
1 2 3
Thuật giải :
Đây là một bài giải hệ phương trình nhị phân khá đơn giản. Ta có thể sử dụng khử Gauss để giải hệ . Nghiệm có số phần tử bằng = 1 ít nhất chính là phương án sử dụng ít kỹ sư nhất ! Cấp độ của khử Gauss vào khoảng O(N3) là chấp nhận được.
Có một dãy số thực gồm N+2 phần tử A0 , A1, … , An+1. Dãy này có tính chất đặc biệt là A[i] = ( A[i-1] + A[i+1] ) / 2 – C[i] với i = 1,2,3…,n.
Yêu cầu : Cho dãy C và A0 , An+1. Hãy tính A1.
Giới hạn :
Input
N
A0 An+1
C1
C2
…
Cn
Output
A1 ( Ghi chính xác đến 2 chữ số sau dấu phẩy ) .
Ví dụ :
Input
1
50.50 25.50
10.15
Output
27.85
Thuật giải :
Ta có A(1) = ( A(0) + A(2) ) / 2 – C(1)
A(2) = ( A(1) + A(3) ) / 2 – C(2)
….
A(n) = ( A(n-1) + A(n+1) ) / 2 – C(n)
→ A(1) + A(2) + … A(n) = ( A(0) + A(n+1) + A(1) + A(n) ) / 2 + A(2) + A(3) + …+A(n-1) – ( C(1) + C(2) + C(3) +…+C(n) ) .
⇔ A(1) + A(n) = A(0) + A(n+1) – 2*( C(1) + C(2) + C(3) +…+C(n) ) .
Tương tự ta có : A(1) + A(n-1) = A(0) + A(n) – 2*( C(1) + C(2) + C(3) +…+C(n-1) ) .
………..
A(1) + A(1) = A(0) + A(2) – 2* C(1) .
⇒ A(1) * (n+1) = A(0) * n + A(n+1) – 2 *( C(1) + C(2) + C(3) +…+C(n) )
- 2*( C(1) + C(2) + C(3) +…+C(n-1) ) – …- 2*C(1).
⇒ Ta tính được A(1). Cấp độ thuật toán O(n). Cũng với phương pháp này ta có thể tính được tất cả các phần tử của dãy A cũng chỉ với cấp độ O(n).
Nikifor có một số tự nhiên N. Anh ta là một người rất yêu thích con số 7 ( giống mình ). Bởi vậy con số của anh ta phải là một con số chia hết cho 7. Nhưng rất tiếc con số N của anh ta lại chưa phải là bội của 7 . Bây giờ anh ta muốn đổi vị trí của các chữ số của số N sao cho tạo được một số mới mà số này chia hết cho 7. Vì Nikifor là một người rất đặc biệt nên con số N của anh ta cũng rất đặc biệt. Số N này luôn có đủ 4 chữ số 1 , 2 , 3 4 trong biểu diễn thập phân của mình ! Hơn nữa nếu số N này đã là bội của 7 rồi thì anh ta vẫn muốn biến đổi để ra được 1 số mới khác cũng chia hết cho 7.
Yêu cầu : Hãy giúp Nikifor đổi vị trí của các chữ số trong số N sao cho được số mới chia hết cho 7.
Giới hạn :
Input
Output
N dòng ghi ra kết quả của từng test , nếu test nào vô nghiệm thì ghi ra “No solution” ngược lại ghi ra số N sau khi biến đổi .
Ví dụ :
Input
2
10234
531234
Output
32410
353241
Thuật giải :
Nhận thấy số N luôn có đủ 4 chữ số 1,2,3,4 . Với 4 số này ta có thể tạo thành bất kỳ số dư nào trong các số dư từ 0->6 :
Ví dụ : 1234 mod 7 = 2 , 3241 mod 7 = 0 …
Như vậy ta có một cách làm rất hay cho bài này đó là : đặt tuỳ ý các chữ số # 0 vào đầu sao cho còn dư lại 4 chữ số 1 , 2 , 3 , 4 . Với 4 chữ số này ta sẽ đặt vào tiếp theo , sau cùng mới đặt các chữ số 0. 4 chữ số 1,2,3,4 cuối ta sẽ duyệt hoán vị của nó xem hoán vị nào của nó thì số N tạo được sẽ chia hết cho 7. Vì với mỗi số dư R đều có ít nhất 2 hoán vị nên dù N cũng có dạng như trên thì cũng có ít nhất 1 số khác cũng cùng dạng này nữa -> Bài toán không bao giờ vô nghiệm ! Vì 4! = 24 -> Chạy rất nhanh !
Cha của Pinocchio muốn làm lại cho Pinocchio một cái mũi mới . Ông có N thanh gỗ , mỗi thanh gỗ có độ dài Ai. Là người yêu thích toán học ông ta đưa ra một giải thuật sau để lấy ra thanh gỗ có độ dài cần thiết :
Quay lại bước 1.
Yêu cầu : Hãy tính xem độ dài mà thanh gỗ ông ta nhận được sẽ là bao nhiêu.
Giới hạn :
Input
N
A1
A2
…
An
Output
Gồm 1 số duy nhất X là độ dài thanh gỗ đạt được.
Ví dụ:
Input
3
2
3
4
Output
1
Thuật giải :
Dễ dàng CM được đó chính là ước chung lớn nhất của N số . Ta có thể dùng thuật toán Oclit. Cấp độ tính toán của bài này là O(n).
Trong đại hội thể thao Olympic năm 3000, người ta quyết định đưa môn bốc sỏi vào thi đấu. Trận đấu sẽ gồm 2 người thi đấu và có K viên sỏi , đến lượt người nào chơi thì được bốc không quá L viên ! Ai đến lượt mình mà không còn gì để bốc nữa thì sẽ thua ! Đấu thủ thứ nhất được quyền chọn xem số K sẽ là bao nhiêu ! Còn đấu thủ thứ 2 được quyền chọn xem số L sẽ là bao nhiêu ! Giả sử đã biết được người thứ nhất chọn số K là bao nhiêu ,bạn hãy giúp người thứ 2 chọn ra số L nhỏ nhất sao cho người thứ 2 chắc chắn giành phần thắng và số L > 1.
Giới hạn :
Input
K
Output
L
Ví dụ :
Input
6
Output
2
Thuật giải :
Đây là một bài toán trò chơi cổ điển, 1 số L để người 2 chắc chắn thắng thì K phải chia hết cho (L+1). Vậy thì đó sẽ là ước nhỏ nhất của K ( mà > 2 ) – 1. Khi tìm ước cần chú ý đến 1 số trường hợp đặc biệt là 14 chẳng hạn , kết quả trả ra sẽ là 6 nhưng mà do không cẩn thận ( có thể là do tìm ước = hàm kiểm tra nguyên tố lấy Sqrt trong khi Sqrt(14) = 3.7416 nên sẽ dẫn tới sai xót ! ).
Yêu cầu : Rất đơn giản ! Hãy tính xem C có bao nhiêu ước nguyên tố với C được tính = CT :
\(C=\frac{n!}{m!(n-m)!} \)
Tất nhiên ở đây N và M là 2 số cho trước .
Giới hạn :
Input
N M
Output
Gồm 1 số duy nhất là số ước của C.
Ví dụ :
Input
7 3
Output
2
( Giải thích : C = 35 = 5*7 ).
Thuật giải :
Ta phân tích N! , M! thành tích của các số nguyên tố .
→ N! = 2x1 * 3x2 * …
M! = 2y1 * 3y2 * …
(N-M)!= 2z1 * 3z2*…
→ C = 2x1-y1-z1 * 3x2-y2-z2 * ….
Ta chỉ việc đếm thôi , với xi-yi-zi > 0 thì ta tăng số phần tử tìm thấy lên 1. Thuật toán hoàn toàn rất đơn giản. Tuy nhiên để thuật toán chạy nhanh ta nên áp dụng công thức Lagrăng như sau :
Số mũ của số nguyên tố P trong N! = [N/P] + [N/(P2)] + … [N/(Pk)].
với [q] = phần nguyên của số q.
Có một dãy số dài vô hạn thoả mãn tính chất Fibonacci .
Đó là : F[i] = F[i-1] + F[i-2]. ( Với mọi i thuộc Z ).
Yêu cầu : Cho biết F[i] và F[j] . Hãy tính F[n].
Giới hạn :
Input
Gồm các số nguyên i, F[i], j, F[j] và n
Output
F[n]
Ví dụ :
Input
3 5 –1 4 5
Output
12
Thuật giải :
Đối với bài này có 2 cách làm . Giả sử i < j .
Cách 1 : Duyệt nhị phân giá trị của F[i+1] . Với mỗi giá trị của F[i+1] ta sẽ kiểm tra xem số F[j] có đúng với đề bài không ! Nếu đúng thì dừng lại và sinh F[n]. Biết F[i] , F[i+1] thì rõ ràng ta có thể tính được toàn bộ phần tử thuộc dãy.
Cách 2 : Dựa vào CT :
F[i+1] = 1 * F[i-1] + 1 * F[i] ;
F[i+2] = 1 * F[i-1] + 2 * F[i] ;
F[i+3] = 2 * F[i-1] + 3 * F[i] ;
F[i+4] = 3 * F[i-1] + 5 * F[i] ;
F[i+5] = 5 * F[i-1] + 8 * F[i] ;
…
F[j] = x * F[i-1] + y * F[i].
Nếu để ý ta sẽ thấy hệ số của F[i-1] , F[i] chính là một dãy Fibonacci . Vậy thì ở đây công việc còn lại sẽ rất đơn giản. Ta chỉ việc tính xem x , y là bao nhiêu nữa là xong ! Chú ý một chút nho nhỏ nếu dùng Cách 2 đó là x, y có thể là rất lớn nên khai báo kiểu Extended là tốt nhất.
SKBJunk 307 là rô bốt đời mới nhất của trung tâm nghiên cứu vũ trụ VNSC ( Viet Nam Space Center ) . Nó được trang bị khả năng tính toán siêu việt. An là một người thích nổi tiếng, để cho mọi người thấy SKBJunk 307 tính toán còn chậm hơn cả một máy tính thông thường, anh ta đã thách đấu với nó. Nội dung của cuộc thi là tính xem 1N + 2N + 3N + 4N có bao nhiêu chữ số 0 ở cuối cùng. An biết chắc là sẽ thua nên đã thuê bạn giúp anh ta.
Yêu cầu : Hãy lập trình tính xem 1N + 2N + 3N + 4N có bao nhiêu chữ số 0 ở cuối cùng.
Giới hạn :
Input
N
Output
Gồm 1 số X duy nhất là kết quả tính được.
Ví dụ:
Input
1
Output
1
Thuật giải :
Dễ thấy kết quả trả ra luôn chỉ có thể là 1 trong 3 số : 0 , 1 , 2.
Kết quả của bài toán này đã được CM bởi Euler đó là :
X(N) = X(N mod 2000).
Bởi vậy thay vì tính số mũ từ 1-> N ta chỉ phải tính số mũ từ 1-> N mod 2000 mà thôi. Tuy nhiên trong thực tế ( với N <= 300000) thì ta chỉ cần tính số mũ từ 1 -> N mod 100 mà thôi.
Đăng lúc 8 năm, 8 tháng trước
Bài viết đầu tiên, tôi sẽ viết về những kỉ niệm đáng nhớ của mình trong suốt 5 năm học tuyển tin của mình. Tôi đến với môn tin một cách đầy tình cờ và cũng rất bất ngờ. Hồi cuối năm lớp 7, trường tôi có luật là ai ko học đội tuyển lớp 8 sẽ phải xuống a3 học (mà a3 thì toàn bọn hay bắt nạt mình) nên mình cũng quyết tâm theo đội tuyển. Nhưng rồi lại nảy ra câu hỏi, theo đội gì bây giờ, ban đầu trẻ trâu theo đội…..sử, tại mấy bạn trong đội sử rất chi là xinh và ngoan (hồi đấy dại gái và bây giờ vẫn thế =))) ).
Nhưng vào được mấy hôm, thấy chúng nó học quá là trâu bò, tài liệu dày từng tập như cuốn truyện, mình không tài nào nhồi nó vào đầu được, quyết định khó khăn: ra khỏi đội tuyển sử. May thay, có lẽ ông trời sắp đặt sẵn :v, lớp tôi được học ngay cạnh phòng học của đội tuyển tin. Mỗi lần đi giặt dẻ lau, wc :v , qua phòng đội tuyển tin, thấy mấy ông chả học mà suốt ngày zingme, dota với cả lang thang lên mạng chơi, hồi đấy trẻ trâu cứ ngỡ đội tuyển tin là toàn chơi điện tử (vào rồi mới thấy, đúng thế thật :v ), xin luôn cô phụ trách đội để vào. Thấy mình hăng hái và có tinh thần, cô đồng ý ngay và gửi mình(cùng một thằng nữa) học với mấy ông lớp 9, do một thầy khác phụ trách. Cơ mà vào mới biết, học thì ít mà …….chơi thì nhiều. Cứ khi nào ra chơi là kêu gào ầm ĩ, hoan hô đủ kiểu, thầy chưa nói gì cả đội đã đòi chơi, mà khổ, thầy cũng hiền, thế là cả bọn half life, dota đủ trò luôn (hồi đấy ngu đánh toàn thua các anh :3). Có hôm, thầy đi vắng, trước khi đi còn dọa” học đi nhé, tí nữa có cô lên kiểm tra đấy”. Thầy đi được 5 phút, cả bọn lao vào chơi điện tử, chờ mãi chả thấy có cô nào lên kiểm tra, khổ, hôm đấy chơi game nhiều quá, tay đau ê ẩm, than vãn quá trời, từ dạo ấy sợ chơi game hơn cả sợ ma. Cơ mà cái số mình nó may, bao lần chơi game bao lần thoát (thực ra là ít dám chơi, toàn nhìn người khác chơi rồi cổ vũ, chứ hiếm khi chơi trực tiếp, sợ thầy tóm được khéo ăn đuổi thì nhục). Hôm đi thi, mình và 1 thằng nữa tiếc là ko mang theo cái gối, đọc đề mà như ru ngủ học sinh (bây giờ đọc lại thấy đề dễ bỏ mịa, ko hiểu sao hồi đấy ko làm được). Cả đội tạch te tua, cuối năm cũng vì giải thấp quá mà bị cắt mất liên hoan :v.
Cái năm lớp 8 trẻ trâu đi qua, sang đến năm lớp 9, mơ mộng lắm, hi vọng nhiều nên lúc được giải khuyến khích cũng thấy nhọ. Chả là cái đề rất chi là bình thường, nhưng do hôm thi mắt mình để nhầm lên đầu, đọc lộn dữ liệu, cài rất chi là hổ báo, hơn 100 dòng (lớp 9 cài thế là kinh rồi) cuối cùng sai te tua mà sửa không nổi. 3 bài thi tỉnh, nộp 2 thì cả hai bài đều sai quá nửa, lòng đau như cắt, nước mắt đầm đìa, năm cuối chia tay đời học sinh cấp 2 nó nhọ như con mực, đã thế cuối năm còn không được học sinh giỏi :v.
Đến năm lớp 10, có lẽ kỉ niệm đáng nhớ nhất là của mình là buổi học cuối cùng trước khi tin học trẻ cấp tỉnh. Khổ, từ khi biết cvp không tham dự, team mình thì có ông quốc gia, chả ngán đội nào nữa, ăn chơi thả ga. Thấy thầy chưa đến, half life chia đội bắn nhau chí chóe, kêu gào đủ kiểu. Thầy ra chết cả đám, ăn mắng te tua, cả hội hối lỗi vô cùng. Sau đó, thầy về, và 10 phút sau, cả đội lại lập team bắn điện tử tiếp =)))))))).
Sau năm lớp 10, cái ước mơ trẻ con là một lần nhất tỉnh đã hoàn thành, tiến tới ước mơ xa vời hơn: thi học sinh giỏi quốc gia cùng mấy bạn cvp. Ban đầu thấy mình cứ mơ mộng rõ lắm, cuối cùng may mắn ăn rùa vào được đội quốc gia. Nhiều kỉ niệm đẹp, nhưng cái mình nhớ nhất là về mấy đứa bạn tốt ở trường. Bạn bè tốt kinh, mình đi học chưa đầy một tuần, chúng nó phao tin loạn xạ “Bạn Việt cố đi thi quốc gia vì muốn “người khác” để ý” (người khác là tên người hẳn hoi nhé, nhưng ko tiện nói ra :D ). Đến giờ vẫn thấy mình quá là may, lúc nhận được cái tin nhắn đó đang học với mấy bạn chuyên, không có ăn uống gì chứ lúc đó mà đang ăn hay uống thì chắc phun thẳng vào cái màn hình máy tính rồi. 20-11 về trường, bạn bè chả thèm hỏi thăm mình sức khỏe thế nào, hỏi luôn câu kia làm mình khóc dở mếu dở, muốn thanh minh mà không được. May là cuối năm mình bị vu yêu một đứa khác, cái tin đấy nó cũng dần biến mất.
Kỉ niệm về đội tuyển tin với riêng cá nhân tôi, có lẽ nó nhiều như bão trên sa mạc hay nước trong đại dương (chắc tại mình yêu đội tuyển hơn yêu lớp), kỉ niệm về những lần trốn tiết trên lớp đi học đội tuyển hay những kỉ niệm khi học quốc gia, có kể vài ngày, vài tháng cũng chẳng hết. Nhưng thôi, tôi sẽ dừng bài viết đầu tiên của mình ở đây, dành thời gian dể viết những bài viết khác. Hy vọng sẽ sớm được gặp lại mọi người ở những bài viết tiếp theo.
© VNOI Team 2015