So sánh x1 x2 và số bất lò
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. Show 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). Bài 2 : Nikifor – 2Nikifor 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 ! Bài 3 : Central HeatingTrong 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. Bài 4 : Simple CalculationsCó 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). Bài 5 : Nikifor – 3Nikifor 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 ! Bài 6 : PinocchioCha 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). Bài 7 : ButtonTrong đạ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 ! ). Bài 8 : CombinationsYê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. Bài 9 : Fibonacci sequenceCó 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. Bài 10 : SKBJunk 307SKBJunk 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. |