Phân tích

Cách tự nhiên nhất là mô phỏng quá trình: theo dõi các chữ số Bleatrix đã thấy, rồi liên tục sinh và kiểm tra những số cô đọc cho đến khi đã thấy đủ 0–9. Nhưng ngoài \(N=0\), có trường hợp nào khác chạy vô hạn hoặc mất thời gian không chấp nhận được không?

Một cách trả lời trong phạm vi bài toán là kiểm tra trước mọi trường hợp từ 0 đến \(10^6\) trước khi tải Test Set lớn. Với chương trình viết tốt trên máy đủ nhanh, việc này chỉ mất vài giây.

Tổng quát hơn, có thể chứng minh rằng với mọi \(N>0\), cô cừu không phải đọc quá nhiều số:

• Chữ số 0: số thứ mười Bleatrix đọc là \(10N\), nên chắc chắn kết thúc bằng 0.
• Các chữ số 1–9: xét lũy thừa 10 nhỏ nhất lớn hơn \(N\), gọi là \(P\). Khi quá trình đạt một số ít nhất bằng \(P\), chữ số ngoài cùng bên trái sẽ nhận mọi giá trị từ 1 đến 9 khi số tăng đến (hoặc vượt) \(9P\). Không thể bỏ qua một chữ số, vì như vậy bước nhảy giữa hai số liên tiếp — bằng \(N\) — phải lớn hơn \(P\); nhưng theo cách chọn \(P\), ta biết \(N<P\).

Theo định nghĩa của \(P\), \(10N\ge P\), nên ta đạt một số lớn hơn \(P\) sau nhiều nhất 10 số được đọc và đạt một số lớn hơn \(9P\) sau nhiều nhất 90 số. Vì vậy, sau khi xử lý riêng \(N=0\), có thể mô phỏng mà không sợ chạy vô hạn, chạy quá lâu đến hết giờ hay tràn cả số nguyên 32 bit.

Trong giới hạn của Test Set nhỏ và lớn, trường hợp tệ nhất hóa ra là 125 theo sau bởi một số lượng bất kỳ chữ số 0. Với các trường hợp ấy, Bleatrix đọc 72 số trước khi ngủ.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - Qualification Round - Counting Sheep, kho Google Coding Competitions (Apache-2.0).