JOI 2010 - Commuting Routes
Xem PDFThành phố ở Canada nơi JOI sinh sống được chia thành các ô bàn cờ bởi \(w\) con đường thẳng chạy theo hướng bắc–nam và \(h\) con đường thẳng chạy theo hướng đông–tây.
Các con đường theo hướng bắc–nam được đánh số \(1,2,\ldots,w\) từ tây sang đông. Các con đường theo hướng đông–tây được đánh số \(1,2,\ldots,h\) từ nam lên bắc. Ký hiệu \((i,j)\) là giao lộ giữa con đường bắc–nam thứ \(i\) tính từ phía tây và con đường đông–tây thứ \(j\) tính từ phía nam.
JOI sống gần giao lộ \((1,1)\) và lái xe đến công ty gần giao lộ \((w,h)\). Xe chỉ có thể di chuyển dọc theo các con đường. Để rút ngắn thời gian đi làm, JOI chỉ đi về phía đông hoặc phía bắc.
Để giảm tai nạn giao thông, thành phố có quy định sau:
- Xe đã rẽ tại một giao lộ không được rẽ tại giao lộ ngay kế tiếp.
Nói cách khác, sau khi rẽ tại một giao lộ, xe không được chỉ đi thêm một đoạn đường giữa hai giao lộ liên tiếp rồi lại rẽ. Với quy định này, JOI có bao nhiêu đường đi làm khác nhau?
Yêu cầu
Cho \(w\) và \(h\). Hãy viết chương trình in ra số dư khi chia số đường đi làm của JOI cho \(100\,000\).
Dữ liệu vào
Dữ liệu vào gồm một dòng chứa hai số nguyên \(w,h\), cách nhau bởi một dấu cách. \(w\) là số con đường theo hướng bắc–nam và \(h\) là số con đường theo hướng đông–tây.
Dữ liệu ra
In ra một dòng chỉ chứa số dư khi chia số đường đi làm của JOI cho \(100\,000\).
Ràng buộc
- \(2\le w\le 100\).
- \(2\le h\le 100\).
Ví dụ
Ví dụ 1
Input
3 4
Output
5
Ví dụ 2
Input
15 15
Output
43688
Giải thích
JOI có \(143\,688\) đường đi làm. Vì vậy, in ra \(43\,688\), là số dư khi chia \(143\,688\) cho \(100\,000\).
Kỳ thi:
- JOI 2009/2010 - Vòng sơ khảo (1 Tháng 1., 2016)

Bình luận