PreVOI 2023 - Phú Thọ - Phân số
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho phân số ~\frac{P}{Q}~, tiến hành biểu diễn phân số trong hệ cơ số thập phân, sau khi loại bỏ dấu chấm thập phân (dấu ngăn cách giữa phần nguyên và phần thực) ta nhận được một xâu số ~S~ có độ dài vô hạn. Đánh số các kí tự của xâu ~S~ bắt đầu từ ~1~, để khảo sát phân số, với một xâu mẫu ~X~ người ta muốn tìm vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~.
Yêu cầu: Cho ~P, Q, k~ và xâu ~X~, hãy xác định vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~, trong đó ~S~ là biểu diễn của phân số ~\frac{P}{Q}~ trong hệ cơ số thập phân sau khi loại bỏ dấu chấm ngăn cách giữa phần nguyên và phần thực.
Input
Dòng đầu tiên chứa ba số nguyên dương ~P, Q, k~ ~(0 < P, Q, k \le 10^6)~;
Dòng thứ hai chứa một xâu số ~X~ có độ dài không vượt quá ~10^5~.
Output
Ghi ra một số là vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~, nếu không tồn tại ghi số 0.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~40\%~ | độ dài xâu ~X~ bằng ~1~; |
| 2 | ~40\%~ | ~k = 1~; |
| 3 | ~20\%~ | Không có giới hạn gì thêm |
Sample Input 1
3 7 2
2
Sample Output 1
8
Sample Input 2
3 5 2
00
Sample Output 2
3
Bình luận