Một người làm việc ở một ngân hàng ngoại tệ theo dõi tỉ giá hối đoái phát hiện ra là: Nếu khôn khéo, thì từ một lượng ngoại tệ ban đầu, nhờ chuyển đổi sang các loại ngoại tệ khác, anh ta có thể thu được lợi nhuận đáng kể.
Ví dụ: Nếu anh ta có 1 USD và tỉ giá hối đoái giữa các ngoại tệ như sau:
Khi đó với 1 USD anh ta có thể mua được 0.7 * 9.5 * 0.16 = 1.064 USD nhờ việc chuyển đổi tiền qua bảng Anh, rồi từ bảng Anh sang Franc Pháp, và cuối cùng lại quay về USD. Nhờ đó mỗi USD đã đem lại cho anh ta lợi nhuận là 0.064USD.
Giả sử trong nhà băng quản lý n loại ngoại tệ đánh số 1, 2, ..., n. Biết bảng tỉ giá hối đoái R[i, j] (1 <= i, j <= n). (Tức là 1 đơn vị ngoại hối i mua được R[i, j] đơn vị ngoại hối j).
Cần xác định xem có cách đổi tiền đem lại lợi nhuận hay không ?
Dữ liệu: Vào từ file văn bản MONEY2.INP
Kết quả: Ghi ra file văn bản MONEY2.OUT
Dòng đầu tiên ghi YES hoặc NO tương ứng với việc có hoặc không có cách đổi tiền sinh lợi nhuận
Nếu dòng đầu tiên là YES thì dòng thứ hai ghi s là lợi nhuận lớn nhất thu được nhờ cách đổi 1 đơn vị tiền u. Dòng thứ ba ghi trình tự cần tiến hành đổi tiền để thu lại được lợi nhuận bắt đầu từ loại tiền xuất phát u.
Các số trên một dòng của Input/Output File được ghi cách nhau ít nhất một dấu cách
Lợi nhuận (nếu có) trong Output File có thể chỉ cần làm tròn giữ lại 4 chữ số sau dấu chấm thập phân.
Ví dụ:
MONEY2.INP |
|
MONEY2.OUT |
5 1.00 1.10 0.83 0.81 0.85 0.83 1.00 0.86 1.09 0.81 0.89 0.84 1.00 0.83 1.02 0.84 0.83 1.01 1.00 0.84 1.09 0.84 0.87 0.90 1.00
|
|
YES 0.3464 1 2 4 3 5 1
|