Chia kẹo
Đề bài
Mô tả
Anh là học sinh lớp bốn với ước mơ được thi ICPC World Finals. Hôm nay Anh học phép chia, và để việc học thử thách hơn, Anh muốn đổi mọi số sang các hệ cơ số khác nhau trước khi thực hiện phép chia.
Anh có viên kẹo xếp thành một vòng tròn, viên thứ có độ ngon là số nguyên dương , và một cơ số nguyên dương . Để việc ăn kẹo vui hơn, Anh chơi một trò chơi. Anh đổi mỗi số sang hệ cơ số , được biểu diễn ( và là cùng một số, chỉ khác cách viết). Trò chơi diễn ra như sau:
- Anh chọn và ăn một viên kẹo trong vòng tròn.
- Sau khi ăn, Anh xác định hai viên kẹo kề với nó, gọi là và , có biểu diễn cơ số là và .
- Anh tính tổng hai phân số , viết tổng này dưới dạng số thập phân trong hệ cơ số và đếm số chữ số ở phần sau dấu phẩy (gồm các chữ số không tuần hoàn và các chữ số của một chu kỳ tuần hoàn). Ví dụ trong hệ cơ số : , Anh viết chữ số không tuần hoàn và chữ số tuần hoàn, tổng cộng chữ số; có chữ số; có chữ số. Trong hệ cơ số : có chữ số.
- Sau khi tính xong và ăn viên kẹo , Anh xếp hai viên kẹo và (vốn kề với ) kề nhau, giữ nguyên vòng tròn. Mỗi bước số viên kẹo giảm đi một.
- Anh lặp lại quá trình ăn kẹo cho đến khi chỉ còn hai viên.
- Với hai viên kẹo cuối cùng, Anh cũng tính tổng phân số như trên cho hai viên đó và đếm số chữ số ở phần sau dấu phẩy, rồi ăn nốt hai viên và kết thúc trò chơi.
Trò chơi lúc đầu thì vui, nhưng Anh nhanh chóng thấy mệt vì phải viết quá nhiều chữ số, nên Anh muốn ăn hết số kẹo mà viết ít chữ số nhất. Hãy giúp Anh xác định tổng số chữ số nhỏ nhất cần viết trong suốt quá trình ăn hết viên kẹo.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (, ).
- Dòng tiếp theo chứa số nguyên (), theo thứ tự trên vòng tròn.
Dữ liệu ra
In ra một số nguyên: tổng số chữ số nhỏ nhất Anh cần viết.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 10 1 5 7 3 |
4 | Ăn viên thứ (độ ngon ): , viết chữ số. Còn ; ăn viên độ ngon : , viết chữ số. Còn : viết thêm chữ số. Tổng . |
| 2 10 14 5 |
7 | . |
| 5 2 4 7 5 11 6 |
17 | Trong hệ cơ số : ăn viên độ ngon (, chữ số), rồi viên (, chữ số), rồi viên (, chữ số), hai viên cuối và ( chữ số). Tổng . |
| 5 104 654074 236092 654237 254045 253310 |
4605392 |
Bình luận