Bai on luyen 3

Bài 1 -  Cắt hình chữ nhật (6 điểm)   Cho một một hình chữ nhật có kích thước MxN. Hãy tìm cách chia hình chữ nhật này thành các hình vuông sao cho số hình vuông là ít nhất Dữ liệu vào cho trong file CAT.INP gồm một dòng ghi hai số nguyên M,N ( 1£  M,N £ 10000) chỉ kích thước của hình chữ nhật Dữ liệu ra ghi ra file CAT.OUT gồm một số duy nhất là số hình vuông trong cách cắt ít hình vuông nhất Ví dụ :
CAT.INP
CAT.OUT

100 25
4

  Bài 2 -  Giao điểm các đường thẳng  – (7 điểm) Trên mặt phẳng cho trước n đường thẳng trong đó không có hai đường thẳng nào trùng nhau (2<= n <= 100). Hãy tính số giao điểm của các đường thẳng này. Yêu cầu tính càng chính xác càng tốt (qui ước rằng: hai số thực x, y được xem là bằng nhau khi  
 ). Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình: Ax + By + C = 0, trong đó A2 + B2 ≠ 0. Dữ liệu vào cho trong file văn bản GDIEM.INP có dạng như sau: - Dòng đầu tiên ghi số n - n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách. Dữ liệu ra ghi trong file GDIEM.OUT gồm 1 dòng là số giao điểm của n đường thẳng. Ví dụ:
GDIEM.INP
GDIEM.OUT

5 -1 1 -2 1 1 4 0 1 -4 1 0 -1 0 1 6
So giao diem la: 9

  Bài 3 – Chèn xâu   – (7 điểm) Cho xâu S = ’123456789’ hãy tìm cách chèn vào S các dấu `+` hoặc `-` để thu được biểu thức có giá trị bằng số nguyên M cho trước (nếu có thể). Dữ liệu vào trong file CHENXAU.INP gồm một số nguyên M. Dữ liệu ra ghi vào file văn bản CHENXAU.OUT tất cả các phương án chèn (nếu có) và ghiKhong co nếu như không thể thu được M từ cách làm trên. Ví dụ:  
CHENXAU.INP
CHENXAU.OUT

500
1-234-56+789 1-2+345+67+89 -12+34+567-89

1000
Khong co