Thành viên:Cumeo89/Đề thi Olympic tin học sinh viên ĐH Bách Khoa HN 2009
Bài 1. Biển số may mắn[sửa]
Biển số xe máy của thành phố X là dãy gồm 6 chữ số. Cư dân thành phố này có quan niệm rất lạ về biển số xe may mắn. Đầu tiên người ta chọn một số k, sau đó tìm cách tạo một số mới từ biển số theo quy tắc sau:
- Đầu tiên từ dãy chữ số của biển số ta tách ra các chữ số, tiếp đến từ các chữ số viết liền nhau trên biển ta lập thành các số.
- Giữa các số thu được ta đặt các dấu ngoặc và các phép toán cộng, trừ, nhân, chia theo quy tắc tính toán biểu thức số học.
- Không được đổi chỗ các số
- Nếu có thể thiết lập biểu thức mà kết quả tính toán cho ta số k thì biển số được gọi là may mắn.
Phép chia chỉ được sử dụng trong trường hợp kết quả cho ta thương số là số nguyên.
Ví dụ: Xét biển số 182836. Chọn k=840. Tách ra thành 4 số: 1, 8, 2, 836. Số k có thể nhận được như là kết quả của biểu thức 1*(8/2+836)=840. Vậy 182836 là biển số may mắn.
Yêu cầu: Cho biển số và số k, hãy xác định xem đó có là biển số may mắn hay không.
Dữ liệu: Vào từ file văn bản LUCKY.INP gồm một dòng chứa hai số k và biển số. Chú ý biển số có thể bắt đầu bởi chữ số 0.
Kết quả: Ghi ra file văn bản LUCKY.OUT thông báo 'YES' nếu biển số là may mắn vào 'NO' nếu trái lại.
Ví dụ:
|
|
Bài 2. Chuyển quà[sửa]
Tuần vừa qua thành phố X được đón tiếp ngài Bill. Vì ngài Bill là nhân vật quan trọng nên khi ông ta đi qua đoạn đường nào thì cảnh sát ngăn không cho bất cứ phuơng tiện giao thông nào đi vào đoạn đường đó, tuy nhiên những xe đã đi vào đoạn phố đó từ trước khi xe của ngài Bill vào sẽ vẫn được tiếp tục hành trình. Ngày mà ngài Bill thăm thành phố, bưu tá Ban lại nhận nhiệm vụ chuyển quà. Vì có nhiều phố không thể đi vào nên Ban có thể không thực hiện việc chuyển quà đúng hẹn. Mặc dù vậy Ban là một bưu tá rất có trách nhiệm, anh ta muốn tìm cách chuyển quà đến địa chỉ sớm nhất có thể được. Bạn biết các đoạn đường phố mà ngài Bill đi qua. Sơ đồ giao thông của thành phố bao gồm các nút giao thông và các đoạn đường phố hai chiều nối các cặp nút giao thông. Với mỗi đoạn đường phố Ban biết thời gian cần thiết để vượt qua (ngài Bill cũng mất cùng một khoảng thời gian như vậy).
Ví dụ, nếu ngài Bill bắt đầu vào phố ở thời điểm phút thứ 10 và mất 5 phút để đi qua thì đoạn phố này sẽ không được đi vào các thời điểm 10, 11, 12, 13, 14. Ban có thể đi vào phố này ở phút thứ 9 và những thời điểm sớm hơn hoặc phút thứ 15 và các thời điểm muộn hơn.
Yêu cầu: Xác định xem Ban mất ít nhất bao nhiêu thời gian để đến đích, nếu biết rằng anh ta xuất phát muộn hơn ngài Bill K phút.
Dữ liệu: Vào từ file văn bản BILL.INP:
- Dòng đầu tiên chứa hai số nguyên N và M (2 ≤ N ≤ 1000, 2 ≤ M ≤ 10 000). là số nút giao thông và số đoạn đường phố. Các nút giao thông được đánh số từ 1 đến N.
- Dòng thứ hai chứa bốn số nguyên A, B, K và G (1 ≤ A, B ≤ N, 0 ≤ K ≤ 1000, 0 ≤ G ≤ 1000), trong đó A là vị trí xuất phát của Ban, B là vị trí Ban muốn đến, K - độ trễ (Ban xuất phát ở nút giao thông A đúng K phút sau khi ngài Bill khởi hành), G - số lượng nút giao thông trên hành trình của ngài Bill.
- Dòng thứ ba chứa dãy G số nguyên là dãy chỉ số của các nút giao thông trên hành trình của ngài Bill. Mỗi cặp số liền kề cho ta một đoạn đường phố mà ngài Bill sẽ đi qua. Các đoạn đường phố như vậy là tồn tại và ngài Bill không lặp lại bất cứ đoạn đường phố nào.
- Mỗi dòng trong số M dòng tiếp theo chứa ba số nguyên U, V, L, cho biết có đoạn đường phố nối nút U với nút V và thời gian cần thiết đi qua nó là L (1 ≤ L ≤ 1000).
Kết quả: Ghi ra file BILL.OUT lượng thời gian (tính bằng phút) ít nhất cần thiết để Ban chuyển quà đến đích.
Ví dụ:
|
|
