Thợ săn x Liên lạc
Đề bài
Mô tả
Sau khi vượt qua Kỳ thi Thợ săn, Gon giờ đã chính thức là một Thợ săn! Gon đang chia tay người bạn thân nhất, Killua, vì Gon muốn về thăm nhà ở "Đảo While".
Gon và Killua định dùng ứng dụng nhắn tin trực tuyến Olaz để giữ liên lạc. Tuy nhiên, họ không tin tưởng lắm vào độ bảo mật của Olaz: kẻ mạo danh có thể đăng nhập vào tài khoản của Gon và gửi tin nhắn cho Killua! Để ngăn chặn điều này, họ quyết định dùng cách sau:
- Trước khi bắt đầu một cuộc trò chuyện, Gon phải gửi cho Killua một số có đúng chữ số.
- Killua phải trả lời bằng một số nguyên có đúng chữ số, sao cho và tạo thành một cặp bạn thân.
- Mỗi lần bắt đầu một cuộc trò chuyện, họ phải dùng một cặp bạn thân khác. Điều này giúp tránh việc kẻ mạo danh dùng lại các cặp bạn thân trước đó.
Để định nghĩa cặp bạn thân, trước hết ta định nghĩa một thao tác thân thiện trên số như sau:
- Chọn hai chữ số kề nhau của .
- Hoặc cộng vào cả hai chữ số, hoặc trừ khỏi cả hai chữ số.
- Không được cộng vào chữ số , hay trừ khỏi chữ số .
- Cũng không được trừ khỏi chữ số đầu tiên của nếu chữ số đầu tiên đó là .
Hai điều kiện cuối đảm bảo số mới hợp lệ và không có chữ số ở đầu. Số mới và số cũ cũng có cùng độ dài.
Hai số và không có chữ số ở đầu được gọi là bạn thân nếu ta có thể thu được từ sau một số hữu hạn thao tác thân thiện. Lưu ý mỗi số là bạn thân của chính nó.
Ví dụ, và là bạn thân vì ta có thể thực hiện các thao tác:
Gon muốn biết họ có thể trò chuyện bao nhiêu lần trước khi dùng hết các cặp bạn thân.
Dữ liệu vào
Dữ liệu vào gồm đúng một số nguyên ().
Dữ liệu ra
In ra đúng một số nguyên là số cặp số bạn thân có đúng chữ số, lấy phần dư khi chia cho .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 | 10 | Có số có một chữ số ( đến ) và không thể thực hiện thao tác nào, nên mỗi số chỉ là bạn thân của chính nó. |
| 2 | 570 | Chẳng hạn là một cặp bạn thân vì . |
Bình luận