Chuyen de BD HSG 2

150 bài tập tin học
 
Bài số 1:
  Cho số tự nhiên n (1 <= n <= 106), hãy tìm chữ số cuối cùng khác 0 của n!.
 Input
  N
Output
  Số cuối cùng khác 0 cần tìm.
 Thuật toán :
   Bằng công thức La grăng, ta có thể dễ dàng tính được bậc của luỹ thừa 2, 5 trong n!
   Như vậy bài toán tương đương với tìm chữ số cuối cùng của số M bằng cách bỏ tất cả luỹ thừa của 10 trong n!. Rõ ràng trong M chỉ còn lại luỹ thừa của 2, không còn luỹ thừa của 5. 
   M = f(1)*f(2)*f(3f(n)*luỹ thừa còn lại của 2.
  Trong đó f(k) là số tự nhiên nhận được từ k bằng loại bỏ hết các luỹ thừa của 2, 5.
Mặt khác vì chỉ quan tâm đến chữ số cuối cùng của M nên trong các thừa số tạo nên M ta chỉ quan tâm đến chữ số cuối cùng của các thừa số, tức là số lần các chữ số 1, 3, 7, 9
là số cuối cùng của một số nào đó. Việc đếm số lần xuất hiện của 1, 3, 7,  9 có thể đếm được dễ dàng bằng phân lớp các số từ 1 đến n thành các lớp có cùng luỹ thừa 2, 5. Trong mỗi lớp k = 2^x*5^y, ta chia mỗi số p cho k, tức là sẽ nhận được f(p). d•y f(p) nhận được là d•y liên tục từ 1 đến n div k , bỏ đi các số có tận cùng 2, 4, 5, 6, 8
 ( Tức là  1, 3, 7, 9, 11,1 3, 17, 19 Từ đó ta có thể dễ dàng tìm được chữ số cuối cùng của M bằng lấy tích của các luỹ thừa  tìm 1, 3, 7, 9, 2  chia dư cho 10.
 Chú ý : ta không tính trực tiếp luỹ thừa của 3, 7, 9, mà chỉ lấy với số mũ là số mũ tìm được chia dư cho 4. (vì 3^4, 7^4, 9^4  có tận cùng là 1).
 
Mở rộng     :
  Bài toán có thể mở rồng tìm  hai chữ số cuối cùng trong đó chữ số sau khác 0 của n!
 
Bài số 2     :
  Có n người, n việc (1 < n <= 200). Người thứ i thực hiện công viêc j  mất C[i,j] đn vị thời gian. Gi sử tất cả bắt đầu vào thời điểm 0, hãy tìm cách bố trí mỗi cồng việc cho mỗi ngưòi sao cho thời điểm hoàn thành công việc là sớm nhất có thể.
  Input
    N
   Ma trận chi phí C[i,j]
  Output
    Thời điểm sớm nhát có thể.
     N số, số thứ i là tên công việc được giao cho người i.  
 
Thuật toán :
   Bài toán có thể đưa về bài toán tìm cặp ghép cực đại trên đồ thị hai phía.
    Bằng chia nhị phân ta thử với mỗi T xem có tồn tại cách xếp việc sao cho mọi công việc được giao đều hoàn thành không muộn hơn thời điểm T hay không.
   L = 0;
   R = Giới hạn các C[i,j]
   For (l < r)
    {
    T = (l + r) / 2;
    if CóCặpGhépĐầyĐủ(T) then r = T
    Else l = T+1;
}
   
Bài số 3   :
  Mạng lưới giao thông gồm có n nút, giữa các nút có thể có đường nối hai chiều và không có hai đường  cùng nối hai  nút. Có tất cả m đường , mỗi đường thuộc môt trong  ba loại đánh số 1, 2, 3. Người số 1 chỉ có thể đi trên đường 1, 3; người số hai chỉ có thể đi  trên 2,3. 
  Hệ thống giao thông đảm bảo cho cả người 1 lẫn 2 đều có thể đi từ một nút đến mọt nút bất kì.
 Hãy tìm cách bỏ đi một số nhiều nhất các đường nối sao cho tính chất liên thông trên vẫn được đảm bảo.
  Input :
   n, m  (n <= 500 ; m <= 10000)
   m dòng tiếp theo, mỗi dòng ghi  ba số u v k  cho biết có đường nối u với v, thuộc loại k.
  Output
    P là số đường  nhiều nhất có thể loại.
   P dòng tiếp theo, mỗi dòng cho biết một đường bị loại ra  gồm  một số là số thứ tự của đường trong Input.
 
Thuật toán :
   Ta tiến hành loang đề tìm các thành phần liên thông chỉ