JOI 2010 - Commuting Routes

Xem PDF



Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Thà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\)\(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
Giải thích

JOI có \(5\) đường đi làm như trong hình. Vì vậy, in ra \(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\).

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: